Okay, three, two, one, let's jam

301 栈和队列

8 min read

栈和队列

队列

队列的基本概念

定义

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。

  • 队头（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 均初始化为 0。
  • 判空条件：front == rear。
  • 入队操作：将元素放入 rear 所指位置，并将 rear 后移。
  • 出队操作：取出 front 所指元素，并将 front 后移。
  • 队列长度：(rear - front + MaxSize) % MaxSize。

数据结构定义：

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front;
    int rear;
} SqQueue;

注意：

  • 顺序队列可能存在假溢出现象（即 rear 到达数组末尾但队列未满），可通过循环队列解决。

循环队列

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

基本操作：

  • 初始化队列：Q.front = Q.rear = 0
  • 队首指针进 1：Q.front = (Q.front + 1) % MaxSize
  • 队尾指针进 1：Q.rear = (Q.rear + 1) % MaxSize
  • 队列长度：(Q.rear - Q.front + MaxSize) % MaxSize
  • 判空条件：Q.front == Q.rear （无法区分队空和队满）
  • 判满条件：Q.front == Q.rear （无法区分队空和队满）

为了区分队空和队满，有三种处理方式：

  • 牺牲一个单元来区分队空和队满，入队时少用一个队列单元。
    • 队满条件：(Q.rear + 1) % MaxSize == Q.front
    • 队空条件：Q.front == Q.rear
    • 队列长度：(Q.rear - Q.front + MaxSize) % MaxSize
  • 使用表示队列长度的变量 size 来判断队列满的条件。
    • 队满条件：size == MaxSize
    • 队空条件：size == 0
    • 此时队空和队满时，front 和 rear 的值是相同的。
  • 使用一个布尔变量 tag 来标识队列满的情况。
    • 入队时，令 tag = 1 （因入队导致，则队满）
    • 出队时，令 tag = 0 （因出队导致，则队空）
    • 队满条件：Q.front == Q.rear && tag == 1
    • 队空条件：Q.front == Q.rear && tag == 0

代码实现：

初始化：

void InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0; // 初始化队首和队尾指针
}

判空：

bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear; // 队空条件
}

入队：

bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满
    Q.data[Q.rear] = x; // 插入元素
    Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针后移
    return true;
}

出队：

bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false; // 队空
    x = Q.data[Q.front]; // 取出元素
    Q.front = (Q.front + 1) % MaxSize; // 队首指针后移
    return true;
}

链式存储

队列的链式存储结构简称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

如图所示：

graph LR
    front(front) --> a1["a₁"]
    a1 --> a2["a₂"]
    a2 --> dots["..."]
    dots --> an["aₙ"]
    rear(rear) --> an

数据结构定义：

typedef struct LinkNode { // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
 
typedef struct {     // 链式队列
    LinkNode *front; // 队头指针
    LinkNode *rear;  // 队尾指针
} LinkQueue;

通常将链式队列设计成一个带头结点的单链表。这样插入和删除操作更方便。

（不需要在插入或删除时，单独处理“空队”以及“在表头插入”的情况， 所有操作都可以假设前驱结点存在，从而统一到“在某节点后插入或删除”的情况）

基本操作：

  • 初始化队列：将 front 和 rear 均初始化为头结点。
  • 判空条件：Q.front == Q.rear。
  • 入队操作：创建新结点并赋值，插入到队尾。
  • 出队操作：删除队头元素。

代码实现：

初始化：

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

判空：

bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

入队：

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

出队：

bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front; // 若队列中只有一个元素，则删除后队列变空
    free(p);
    return true;
}

双端队列

双端队列（Deque）是指允许两端都可以进行入队和出队操作的队列。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。

在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。

输出受限的双端队列

允许在一端进行入队和出队，但在另一端只允许进行出队操作。

输入受限的双端队列

允许在一端进行入队和出队，但在另一端只允许进行入队操作。

若限制双端队列从某个端点插入元素，只能从该端点出队，则该双端队列等价于两个栈底相邻的栈。

Graph View

Backlinks