考研笔记

速查：栈与队列的判空判满

C 档速查表：第 3 章的判空判满结论收在这里。循环队列的三种判空判满方案是本表的核心（2014 直接考过）。

栈的另外两块单独成页：出栈序列的判定与计数见 3.1.1 出栈序列与卡特兰数， 括号匹配 / 表达式求值 / 递归见 3.3 栈和队列的应用。

顺序栈

约定初始判空判满入栈出栈
top 指向栈顶元素top = -1top == -1top == MaxSize-1S.data[++S.top]=xx=S.data[S.top--]
top 指向栈顶元素的下一位置top = 0top == 0top == MaxSizeS.data[S.top++]=xx=S.data[--S.top]

两种约定的入栈/出栈语句里 ++/-- 的位置正好相反，这是最容易写反的一处。题目不说明时按第一种（top=-1）。

共享栈：两个栈共享一片空间，top0=-1、top1=MaxSize，栈满条件是 top1 - top0 == 1。

顺序队列的假溢出

front 指向队头元素、rear 指向队尾元素的下一个位置时，rear 走到 MaxSize 就再也入不了队，但 data 数组中依然存在可以存放元素的空位置——教材称之为**「假溢出」**。

循环队列就是为解决假溢出而生的：把存储队列元素的表从逻辑上视为一个环，front 走到 MaxSize-1 后再前进一个位置就自动到 0，利用除法取模运算（%）来实现。

循环队列的基本运算（3.2.2）

项式子
初始时Q.front = Q.rear = 0
队首指针进 1Q.front = (Q.front+1) % MaxSize
队尾指针进 1Q.rear = (Q.rear+1) % MaxSize
队列长度(Q.rear + MaxSize - Q.front) % MaxSize
出入队时指针都按顺时针方向进 1

问题：队空是 Q.front == Q.rear；但若入队快于出队，队尾指针会赶上队首指针，队满时也有 Q.front == Q.rear——两者无法区分。

三种处理方式（教材原文）

1）牺牲一个单元来区分队空和队满

入队时少用一个队列单元，这是一种较为普遍的做法，约定以「队首指针在队尾指针的下一位置作为队满的标志」。

条件
队满(Q.rear+1) % MaxSize == Q.front
队空Q.front == Q.rear
元素个数(Q.rear - Q.front + MaxSize) % MaxSize

2）类型中增设 size 数据成员

表示元素个数。若删除成功，则 size 减 1；若插入成功，则 size 加 1。

条件
队空Q.size == 0
队满Q.size == MaxSize
共同点两种情况都有 Q.front == Q.rear

3）类型中增设 tag 数据成员

以区分是队满还是队空。删除成功置 tag=0，若导致 Q.front == Q.rear，则为队空；插入成功置 tag=1，若导致 Q.front == Q.rear，则为队满。

三种方案的区别一句话：方案 1 牺牲空间，方案 2 和 3 牺牲一个额外的数据成员。只有方案 1 会让循环队列最多存 MaxSize-1 个元素。

循环队列的操作代码（方案 1）

void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;                        //初始化队首、队尾指针
}
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;           //队空条件
    else                  return false;
}
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;               //队尾指针加 1 取模
    return true;
}
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front) return false;          //队空则报错
    x = Q.data[Q.front];
    Q.front = (Q.front+1) % MaxSize;             //队首指针加 1 取模
    return true;
}

链式队列

队列的链式表示称为链式队列，它实际上是一个同时有队首指针和队尾指针的单链表。 队首指针指向队头结点，队尾指针指向队尾结点，即单链表的最后一个结点。

不带头结点带头结点
判空front == NULLfront == rear（都指向头结点）
入队/出队特判需要单独处理空队的情形不需要，代码更简洁

高频边界

说法判断说明
「假溢出是真的溢出」❌数组中依然存在可存放元素的空位置
「循环队列队空队满都是 front==rear」⚠️方案 2、3 是；方案 1 不是（方案 1 队满是 (rear+1)%MaxSize==front）
「循环队列能存 MaxSize 个元素」⚠️方案 1 只能存 MaxSize-1 个；方案 2、3 可以存满
「队列长度 = rear - front」❌是 (rear - front + MaxSize) % MaxSize
「顺序栈 top 一定指向栈顶元素」❌两种约定都有，判空判满条件不同
「共享栈满是 top0 == top1」❌是 top1 - top0 == 1
「链式队列的 rear 指向最后一个结点的下一位置」❌指向队尾结点本身
「链式队列不会满」⚠️逻辑上不会，除非内存耗尽

链接

反向链接