队列（从数据结构的三要素出发）

文章目录

• 存储结构
• 物理结构
• • 顺序队列
  • 循环队列
  • 链式队列
  • 双端队列
  • 数据的操作
  • • 顺序队列的基本操作
    • 循环队列的基本操作
    • 链式队列的基本操作
    • 双端队列的基本操作
    • 数据结构的应用
    • • 队列在层次遍历中的应用
      • 队列在计算机系统中的应用（OS）

        存储结构

        队列是只允许在一端进行插入，在另一端进行删除操作的线性表。

        物理结构

        顺序队列

        利用静态数组实现，并需要记录队头和队尾指针，且队列的大小不可改变。

        typedef struct {int data;// 数据域int front, rear;// 队头队尾指针域} SqQueue;

        在图d队列中，仅有一个元素。这时入队出现“上溢出”,但这种溢出并不是真正的溢出，在data 数组中依然存在可以存放元素的空位置，所以是一种 “假溢出”，极大的浪费了存储空间以及大小不可扩充的问题 。

        循环队列

        为了解决 “假溢出” 的问题，我们引入循环队列。将顺序队列想象成一个环状的空间，将存储队列从逻辑上视为一个环，称之为循环队列。

        定义与顺序队列一样，区别在于判满和判空的逻辑不同。解决了“假溢出”的问题，但是没有解决队列不可扩充的问题。

        链式队列

        利用单链表实现，需要头指针和队尾指针，解决了顺序队列中队列的大小不可扩充的问题。

        定义结点

        typedef struct LinkNode {int data;// 数据域struct LinkNode *next;// 指针域} LinkNode;

        定义队列

        typedef struct {LinkNode *front, *rear;// 定义队头队尾指针} LinkQueue;

        双端队列

        双端队列是指允许两端都可以进行插入和删除操作的线性表，双端队列两端的地位是平等的，为了方便理解，将左端也视为前端，右端也视为后端。

        链式存储

        typedef struct DequeNode {// 定义双端队列结点int data;// 数据域struct DequeNode *pre, *next;// 前后指针域} DequeNode;typedef struct {// 定义双端队列DequeNode *front, *rear;// 头尾指针域} Deque;

        数据的操作

        顺序队列的基本操作

        初始化

        void InitQueue(SqQueue &q){q.front = q.rear = 0;}

        判断队列为空

        bool isEmpty(SqQueue q){if (q.front == q.rear) return true;return false;}

        判断队列为满

        bool isFull(SqQueue q) {if (q.rear == Maxsize) return true;return false;}

        入队列

        bool EnQueue(SqQueue &q, int &x){if (!isFull(q)){q.data[q.rear ++ ] = x;return true;}return false;}

        出队列

        bool DeQueue(SqQueue &q, int &x){if (!isEmpty(q)){x = q.data[q.front ++ ];return true;}return false;}

        循环队列的基本操作

        初始化

        void InitQueue(SqQueue &q){q.rear = q.front = 0;}

        判空/判满/入队/出队（三种处理方式）

        若用循环队列的话，判断队空的条件是Q.front==Q.rear，判断队满的条件也是Q.front==Q.rear。这就会区分不出来到底是队空还是队满。

        为了区分是队空还是队满的情况，有三种处理方式：

        • 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以“队头指针在队尾指针的下一位置作为队满的标志”。

          bool isEmpty(SqQueue q){if (q.rear == q.front) return true;return false;} bool isFull(SqQueue q){if ((q.rear + 1) % Maxsize == q.front) return true;return false;}bool EnQueue(SqQueue &q, int x){if (!isFull(q)){q.data[q.rear] = x;q.rear = (q.rear + 1) % Maxsize;return true;}return false;}bool DeQueue(SqQueue &q, int &x){if (!isEmpty(q)){x = q.data[q.front];q.front = (q.front + 1) % Maxsize;return true;}return false;}

          • 类型中增设size数据成员，表示元素个数。

            typedef struct {int data[Maxsize];// 数据域int front, rear;// 队头队尾指针域int size;// 队中元素个数} SqQueue;void InitQueue(SqQueue &q){q.front = q.rear = 0;q.size = 0;}bool isEmpty(SqQueue q){if (q.size == Maxsize) return true;return false;}bool isFull(SqQueue q){if (q.size == 0) return true;return false;}bool EnQueue(SqQueue &q, int x){if (!isFull(q)){q.data[q.rear] = x;q.rear = (q.rear + 1) % Maxsize;q.size ++ ;return true;}return false;}bool DeQueue(SqQueue &q, int &x){if (!isFull(q)){x = q.data[q.front];q.front = (q.front + 1) % Maxsize;q.size -- ;return true;}return false;}

            • 类型中增设 tag 数据成员，以区分是队满还是队空。删除成功置 tag=0,插入成功置 tag=1。只有删除操作才能使得队空，只有插入操作才能使得队满。

              typedef struct {int data[Maxsize];// 数据域int front, rear;// 队头队尾指针int tag;// 标志域} SqQueue;void InitQueue(SqQueue &q){q.front = q.rear = 0;q.tag = 0;}bool isEmpty(SqQueue q){if (q.rear == q.front && tag == 0) return true;return false;}bool isFull(SqQueue q){if (q.rear == q.front && tag == 1) return true;return false;}bool EnQueue(SqQueue &q, int x){if (!isFull(q, x)){q.data[q.rear] = x;q.rear = (q.rear + 1) % Maxsize;q.tag = 1;return true;}return false;}bool DeQueue(SqQueue &q, int &x){if (!isEmpty(q)){x = q.data[q.front];q.front = (q.front + 1) % Maxsize;q.tag = 0;return true;}return false;}

              链式队列的基本操作

              初始化

              void InitQueue(LinkQueue &q){q.rear = q.front = (LinkNode *) malloc (sizeof(LinkNode));q.front->next = NULL;}

              判空

              bool isEmpty(LinkQueue q){if (q.front == q.rear) return true;return false;}

              入队

              bool EnQueue(LinkQueue &q, int x){LinkNode *t = (LinkNode *) malloc (sizeof(LinkNode));t->data = x;t->next = NULL;q.rear->next = t;q.rear = t;return true;}

              出队

              bool DeQueue(LinkQueue &q, int &x){if (!isEmpty(q)){LinkNode *t = q.front->next;x = t->data;q.front->next = t->next;if (q.rear == t) // 若只有一个结点，删除后使其变为空队列q.rear = q.front;free(t);return true;}return false;}

              双端队列的基本操作

              初始化

              void InitQueue(Deque &q){q.front = q.rear = NULL;}

              判空

              bool isEmpty(Deque q){if (q.front == NULL && q.rear == NULL) return true;    return false;}

              队头插入

              bool InsertFront(Deque &q, int x){DequeNode *newNode = (DequeNode *) malloc(sizeof(DequeNode));newNode->data = x;    newNode->pre = NULL;    newNode->next = q->front;if (isEmpty(q))         q->rear = newNode;    else        q->front->pre = newNode;      q->front = newNode;    return true;}

              队尾插入

              bool InsertRear(Deque &q, int x){DequeNode *newNode = (DequeNode *) malloc(sizeof(DequeNode));newNode->data = x;    newNode->next = NULL;    newNode->pre = q->rear;if (isEmpty(q))         q->front = newNode;    else         q->rear->next = newNode;       q->rear = newNode;    return true;}

              队头删除

              bool DeleteFront(Deque &q, int &x){if (isEmpty(q)) return false;DequeNode *temp = q->front;    x = temp->data;    q->front = q->front->next;if (q->front)// 如果队列不为空，更新新的队首节点的 prev 指针        q->front->prev = NULL;    else// 如果删除后队列为空，更新队尾指针        q->rear = NULL;       free(temp);    return true;}

              队尾删除

              bool DeleteRear(Deque &q, int &x){if (isEmpty(q)) return false;    DequeNode *temp = q->rear;    x = temp->data;    q->rear = q->rear->prev;    if (q->rear)       // 如果队列不为空，更新新的队尾节点的 next 指针        q->rear->next = NULL;    else // 如果删除后队列为空，更新队首指针        q->front = NULL;       free(temp);    return true;}

              数据结构的应用

              队列在层次遍历中的应用

              队列适用于逐层或逐行处理，使用队列是为了保存下一步的处理顺序。下面用二叉树(见图 3.17)层次遍历的例子，说明队列的应用。

              该过程的简单描述如下：

              ① 根结点入队，

              ② 若队空(所有结点都已处理完毕),则结束遍历；否则重复③操作。

              ③队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。

              void InverLevel(BiTree T){SqQueue q, InitQueue(q);BiTNode *p = T;// 遍历指针EnQueue(q, p);while (!isEmpty(q)){DeQueue(q, p);visit(p);if (p->lchild) Enqueue(q, p->lchild);if (p->rchild) Enqueue(q, p->rchild);}}

              队列在计算机系统中的应用（OS）

              缓冲区的逻辑结构：

              主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机打印，则显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

              队列出队入队操作的应用：

              CPU资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU能够正常运行。