队列的基本概念

队列的定义

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作的特性是先进先出（First In First Out，FIFO）。

  • 队头（Front）：允许删除的一端，又称队首。
  • 队尾（Rear）：允许插入的一端。
  • 空队列：不含任何元素的空表。

队列常见的基本操作

  • InitQueue(&Q)：初始化队列，构造一个空队列 Q。
  • QueueEmpty(Q)：判队列空，若队列 Q 为空返回 true，否则返回 false。
  • EnQueue(&Q,x)：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾。
  • DeQueue (&Q, &X)：出队，若队列 Q 非空，删除队头元素，并用 x 返回。
  • GetHead(Q,&x)：读队头元素，若队列 Q 非空，则将队头元素赋值给 x。

队列的顺序存储结构

队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置（不同教材对 front 和 rear 的定义可能不同，例如，可以让 rear 指向队尾元素、front 指向队头元素。对于不同的定义，出队入队的操作是不同的）。队列的顺序存储类型可描述为：

  1. #define MaxSize 10
  2. typedef struct {
  3.     int data[MaxSize];
  4.     int front,rear;
  5. } SqQueue;
  • 初始状态（队空条件）：Q.front==Q.rear==0。
  • 进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1。
  • 出队操作：队不空时，先取队头元素值，再将队头指针加 1。

这样的顺序存储只能进行一次的排满队和出队的操作。

循环队列

这里引出循环队列的概念将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针 Q. front=MaxSize-1 后，再前进一个位置就自动到 0，这可以利用除法取余运算来实现。

  • 初始时：Q.front=Q.rear=0
  • 队首指针进 1：Q.front=(Q.front+1)%MaxSize
  • 队尾指针进 1：Q.rear=(Q.rear+1)%MaxSize
  • 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

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

  1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是较为普遍的做法约定以“队头指针在队尾指针的下一位置作为队满的标志”。
    • 队满条件：(Q.rear+1)%MaxSize==Q.front
    • 队空条件：Q.front==Q.rear
    • 队中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize
  2. 类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0；队满的条件为 Q.size==MaxSize。这两种情况都有Q.front==Q.rear。
  3. 类型中增设 tag 数据成员，以区分是队满还是队空。每次删除操作成功，都令tag=0；每次插入操作成功时，都令tag=1。
    • tag 等于 0 时，若因删除导致Q.front==Q.rear，则为队空；
    • tag 等于 1 时，若因插入导致Q.front==Q.rear，则为队满。

循环队列的操作

  1. // 判断队列是否为空
  2. bool QueueEmpty(SqQueue Q){
  3.     if(Q.rear==Q.front){
  4.         return true;
  5.     } else {
  6.         return false;
  7.     }
  8. }
  10. // 入队
  11. bool EnQueue(SqQueue &Q,int x){
  12.     if((Q.rear+1)%MaxSize==Q.front){
  13.         return false;
  14.     }
  15.     Q.data[Q.rear]=x;
  16.     Q.rear=(Q.rear+1)%MaxSize;
  17.     return true;
  18. }
  20. // 出队
  21. bool DeQueue(SqQueue &Q,int &x){
  22.     if(Q.rear==Q.front){
  23.         return false;
  24.     }
  25.     x = Q.data[Q.front];
  26.     Q.front = (Q.front+1)%MaxSize;
  27.     return true;
  28. }
  30. // 获得队头值
  31. bool GetHeaf(SqQueue &Q,int &x){
  32.     if(Q.rear==Q.front){
  33.         return false;
  34.     }
  35.     x = Q.data[Q.front];
  36.     return true;
  37. }

队列的链式存储结构

队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）。队列的链式存储类型可以描述为：

typedef struct LinkNode {  // 链式队列结点
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct {  // 链式队列
    LinkNode *front, *rear;
} LinkQueue;

带头结点链式队列的基本操作

#include <cstdlib>
// 初始化（带头结点）
void InitQueue(LinkQueue &Q) {
    // 初始时 front、rear 都指向头节点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 判断队列是否为空
bool IsEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

// 入队
void EnQueue(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

// 出队
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == Q.rear) {
        return false;  // 空队列
    }
    LinkNode *p = Q.front->next;
    x = p->data;              // 变量x返回队头元素
    Q.front->next = p->next;  // 修改头结点的next指针
    if (Q.rear == p) {     // 如果删除的是队列中的最后一个结点
        Q.rear = Q.front;  // 设置队列为空
    }
    free(p);
    return true;
}

// QueueByChain.cpp

不带头结点链式队列的基本操作

// 初始化（不带头结点）
void InitQueue(LinkQueue &Q){
    Q.front = NULL;
    Q.rear = NULL;
}

// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL){
        return true;
    } else {
        return false;
    }
}

// 入队
void EnQueue(LinkQueue &Q,int x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if(Q.front == NULL){
        Q.front = s;
        Q.rear = s;
    } else {
        Q.rear->next = s;
        Q.rear = s
    }
}

// 出队
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == nullptr) {
        return false;  // 空队列
    }
    LinkNode *p = Q.front;
    x = p->data;            // 变量x返回队头元素
    Q.front = p->next;      // 修改头结点的next指针
    if (Q.rear == p) {      // 如果删除的是队列中的最后一个结点
        Q.front = nullptr;  // 设置队列为空
        Q.rear = nullptr;
    }
    free(p);
    return true;
}
// QueueByChainWithoutHead.cpp

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

  • 栈：只允许从一端插入和删除的线性表
  • 队列：只允许从一端插入、另一端删除的线性表
  • 双端队列：只允许从两端插入、两端删除的线性表
  • 输入受限的双端队列：只允许从一端插入、 两端删除的线性表
  • 输出受限的双端队列：只允许从两端插入、一端删除的线性表