考研笔记

板子：顺序栈与循环队列

两种写法：做算法题时直接开数组当工具（后面的层序遍历、BFS、拓扑排序都用这种）；题目要求实现栈或队列操作时，用教材的封装写法。

工具写法（算法题里临时用）

// 速记：直接开数组，不封装
int st[MaxSize], top = -1;             // 栈：top 指向栈顶元素，top == -1 表示空
st[++top] = x;                         // 入栈：先 ++ 再放（top 原来指着旧的栈顶）
x = st[top--];                         // 出栈：先取再 --（只读栈顶用 st[top]）
 
int q[MaxSize], front = 0, rear = 0;   // 队列：front 指向队头元素，rear 指向队尾的下一个位置
q[rear++] = x;                         // 入队：先放再 ++
x = q[front++];                        // 出队：先取再 ++；front == rear 表示队空

层序遍历和 BFS 里每个元素只进队一次，数组开到元素个数就够了，不用写成循环队列。

教材写法（题目要求实现操作时）

// 顺序栈
typedef struct {
    int data[MaxSize];
    int top;                            // 栈顶元素的下标，空栈为 -1
} SqStack;
 
void InitStack(SqStack &S) { S.top = -1; }
bool StackEmpty(SqStack S) { return S.top == -1; }
bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) return false;      // 栈满：下标最大只能到 MaxSize-1
    S.data[++S.top] = x;
    return true;
}
bool Pop(SqStack &S, int &x) {
    if (S.top == -1) return false;               // 栈空
    x = S.data[S.top--];
    return true;
}
 
// 循环队列（牺牲一个单元来区分空和满）
typedef struct {
    int data[MaxSize];
    int front, rear;                    // front 指向队头元素，rear 指向队尾元素的下一个位置
} SqQueue;
 
void InitQueue(SqQueue &Q) { Q.front = Q.rear = 0; }
bool QueueEmpty(SqQueue Q) { return Q.front == Q.rear; }
bool EnQueue(SqQueue &Q, int x) {
    if ((Q.rear + 1) % MaxSize == Q.front) return false;   // 队满：rear 再走一步就撞上 front
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;                       // 后移一格，走到末尾就绕回 0
    return true;
}
bool DeQueue(SqQueue &Q, int &x) {
    if (Q.front == Q.rear) return false;                   // 队空：front 追上 rear
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}
// 队列长度：(Q.rear - Q.front + MaxSize) % MaxSize，加 MaxSize 是为了 rear < front 时不出负数

复杂度：每个操作都是 。

易错点

  • 栈顶指针有两种约定：top 初值为 时指向栈顶元素，入栈写 ++top；top 初值为 时指向栈顶的下一个位置，入栈写 top++。选择题常考，题目用哪种就按哪种算。
  • 循环队列的每一次移动都要 % MaxSize，漏一个就不再是循环队列。
  • 「队满」有三种判法（牺牲一个单元、设 size、设 tag），这里用的是第一种，最多只能存 MaxSize - 1 个元素。另外两种见下面的速查表。
  • 出栈、出队的结果要通过 int &x 带回来，别忘了写 &。

链接

反向链接