Appearance
栈与队列
概念
栈（stack，栈）和队列（queue，队列）都是操作受限的线性表——元素之间的逻辑关系仍然是"一对一"，但插入和删除只能在规定的端点进行。
- 栈：只允许在栈顶（top）一端插入和删除，特点是后进先出（LIFO, Last In First Out）。
- 队列：只允许在队尾（rear）插入、在队头（front）删除，特点是先进先出（FIFO, First In First Out）。
一句话区分：栈是"叠盘子"，只能从最上面拿；队列是"排队打饭"，先来的先走。
限制操作不是为了麻烦，而是为了把"最近/最早"这个语义固化进结构里：凡是遇到"最近相关"（括号匹配、函数调用）就用栈，凡是遇到"按序处理"（打印队列、BFS）就用队列。
原理
栈：一个指针就够
栈只需要跟踪栈顶位置。顺序栈用一个数组 data[] 加一个整型 top：
- 初始化：
top = -1（也有教材用top = 0，指栈顶元素的下一个位置，两种约定都要认得） - 入栈：
data[++top] = x - 出栈：
x = data[top--] - 栈空：
top == -1；栈满：top == MaxSize - 1
top = -1 的约定下，栈顶指针指向栈顶元素本身；top = 0 的约定下指向下一个可放位置。做题时先看清是哪一种，二者差 1，是选择填空的常设陷阱。
共享栈（两栈共享一片存储空间）是 408 考过的小知识点：两个栈的栈底分别设在数组两端，栈顶向中间生长，栈满的条件是 top1 + 1 == top2。它提高了空间利用率，且两个栈的总量可以互补。
队列：为什么必须循环
顺序队列若简单地让 front、rear 单调后移，会出现假溢出——数组尾部满了但头部还有空位。解法是把数组看成首尾相接的环，即循环队列（circular queue）。
循环队列的核心操作是取模：
- 入队：
rear = (rear + 1) % MaxSize - 出队：
front = (front + 1) % MaxSize
但取模带来一个副作用：rear == front 时，队空和队满的判据撞车了。三种主流解法必须会：
| 解法 | 做法 | 队空条件 | 队满条件 | 代价 |
|---|---|---|---|---|
| 牺牲一个单元 | 约定队头前留一个空位 | front == rear | (rear + 1) % MaxSize == front | 浪费一个存储单元 |
| 增设计数器 | 记 count | count == 0 | count == MaxSize | 多一个变量 |
| 增设标志位 | 记 flag（上次是入还是出） | front==rear && flag==0 | front==rear && flag==1 | 多一个变量 |
元素个数（牺牲单元法）：(rear - front + MaxSize) % MaxSize。
双端队列（deque）允许两端都进出。它的两个受限变种要认得：输入受限（只能一端插、两端删）和输出受限（两端插、一端删），选择题常问"某输出序列能否由某种双端队列得到"。
栈的经典应用
- 括号匹配：遇左括号入栈，遇右括号弹出栈顶比对。
- 表达式求值：中缀转后缀（逆波兰式），再用栈求值。
- 递归：函数调用栈保存返回地址、局部变量、参数。递归本质就是栈。
- 进制转换：除基取余，余数入栈后倒序输出。
示例
C 语言：顺序栈与括号匹配
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} SqStack;
void init(SqStack *S) { S->top = -1; }
int isEmpty(SqStack *S) { return S->top == -1; }
int push(SqStack *S, char c) {
if (S->top == MAXSIZE - 1) return 0;
S->data[++S->top] = c;
return 1;
}
int pop(SqStack *S, char *c) {
if (isEmpty(S)) return 0;
*c = S->data[S->top--];
return 1;
}
/* 只处理一种括号，返回 1 表示匹配 */
int match(const char *str) {
SqStack S; init(&S);
for (int i = 0; str[i]; i++) {
if (str[i] == '(') push(&S, '(');
else if (str[i] == ')') {
char c;
if (!pop(&S, &c)) return 0; /* 栈空却有右括号 */
}
}
return isEmpty(&S); /* 栈必须恰好为空 */
}
int main(void) {
printf("%d\n", match("(()())")); /* 1 */
printf("%d\n", match("(()")); /* 0 */
printf("%d\n", match("())")); /* 0 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
C 语言：循环队列（牺牲一个单元）
#include <stdio.h>
#define MAXSIZE 6 /* 实际最多存 5 个元素 */
typedef struct {
int data[MAXSIZE];
int front, rear;
} SqQueue;
void init(SqQueue *Q) { Q->front = Q->rear = 0; }
int isEmpty(SqQueue *Q) { return Q->front == Q->rear; }
int isFull(SqQueue *Q) { return (Q->rear + 1) % MAXSIZE == Q->front; }
int size(SqQueue *Q) { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; }
int enqueue(SqQueue *Q, int x) {
if (isFull(Q)) return 0;
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}
int dequeue(SqQueue *Q, int *x) {
if (isEmpty(Q)) return 0;
*x = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}
int main(void) {
SqQueue Q; init(&Q);
for (int i = 1; i <= 5; i++) enqueue(&Q, i * 10);
printf("full=%d size=%d\n", isFull(&Q), size(&Q)); /* full=1 size=5 */
int x; dequeue(&Q, &x); dequeue(&Q, &x);
enqueue(&Q, 60);
printf("size=%d\n", size(&Q)); /* 4 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
例：中缀转后缀的完整过程
把中缀表达式
A + B * C - D / E转为后缀表达式。
规则：数字/变量直接输出；运算符与栈顶比较，优先级高于栈顶才入栈，否则先弹出栈顶；左括号无条件入栈，遇右括号一直弹到左括号。
| 读到 | 动作 | 运算符栈（底→顶） | 输出 |
|---|---|---|---|
| A | 输出 A | 空 | A |
| + | 栈空，入栈 | + | A |
| B | 输出 B | + | A B |
| * | 优先级高于 +，入栈 | + * | A B |
| C | 输出 C | + * | A B C |
| - | 优先级低于 *，弹 *；再低于 +，弹 +；入栈 | - | A B C * + |
| D | 输出 D | - | A B C * + D |
| / | 优先级高于 -，入栈 | - / | A B C * + D |
| E | 输出 E | - / | A B C * + D E |
| 结束 | 依次弹出 | 空 | A B C * + D E / - |
结论：后缀式为 A B C * + D E / -。注意减号 - 弹出了两个运算符——同级运算符左结合，后来者要挤走先来者。
C 语言：后缀表达式求值
#include <stdio.h>
#include <ctype.h>
/* 求后缀表达式（空格分隔，只含一位数和 + - * /） */
int evalPostfix(const char *s) {
int st[100], top = -1;
for (int i = 0; s[i]; i++) {
if (isdigit((unsigned char)s[i])) {
st[++top] = s[i] - '0';
} else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
int b = st[top--], a = st[top--]; /* 注意顺序：先弹的是右操作数 */
if (s[i] == '+') st[++top] = a + b;
else if (s[i] == '-') st[++top] = a - b;
else if (s[i] == '*') st[++top] = a * b;
else st[++top] = a / b;
}
}
return st[top];
}
int main(void) {
printf("%d\n", evalPostfix("23*4+")); /* 2*3+4 = 10 */
printf("%d\n", evalPostfix("52-3*")); /* (5-2)*3 = 9 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
# 栈：Python 的 list 直接当栈用
st = []
for ch in "(()())":
if ch == '(':
st.append(ch)
elif ch == ')':
if not st:
break
st.pop()
print("match:", len(st) == 0) # True
# 队列：collections.deque 是双端队列，popleft 是 O(1)
from collections import deque
q = deque()
for i in range(1, 6):
q.append(i * 10)
print(len(q), q[0]) # 5 10
q.popleft(); q.popleft()
q.append(60)
print(list(q)) # [30, 40, 50, 60]
# 后缀求值
def eval_postfix(tokens):
st = []
for t in tokens:
if t.isdigit():
st.append(int(t))
else:
b, a = st.pop(), st.pop() # 先弹右操作数
st.append({'+': a + b, '-': a - b, '*': a * b, '/': a // b}[t])
return st[-1]
print(eval_postfix(list("234+*"))) # 2 (3+4) * = 14
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 里
list.pop(0)是 O(n)，队列一定要用deque.popleft()，这是实际写代码的常识点。
考点
考点
1. 栈的合法输出序列（年年考）
n 个不同元素依次入栈，出栈序列总数 = 第 n 个卡特兰数：
n = 3 时为 5 种，n = 4 时为 14 种。
判断某个序列是否合法，用模拟法最稳：按目标序列依次出栈，若栈顶不是当前要出的元素，就继续把未入栈的元素按顺序压入；若全压完了栈顶仍不匹配，则该序列非法。
2. 循环队列的判空判满（必背）
- 牺牲单元法：空 =
front == rear，满 =(rear+1) % M == front - 元素个数 =
(rear - front + M) % M - 队头指针指向队头元素，队尾指针指向队尾元素的下一个位置（牺牲单元法下的通用约定）
3. 易错点
top = -1与top = 0两种初始化差一位，入栈是++top还是top++也随之变。- 中缀转后缀时，括号内的运算符不参与与括号外运算符的比较——左括号入栈后相当于一道墙。
- 后缀求值弹出两个操作数时，先弹的是右操作数，减法除法因此有方向，弄反就错。
- 递归转非递归要用栈，但栈模拟递归不等于消除递归的空间开销，空间复杂度仍是 O(递归深度)。
- 栈和队列都能用顺序或链式存储；链式队列（带头结点）通常不存在假溢出，也不需要循环。
小结
- 栈 = 只在栈顶操作的线性表（LIFO），队列 = 尾进头出的线性表（FIFO）。
- 顺序栈只需一个
top；循环队列靠取模消除假溢出，代价是要额外信息区分空与满。 - 表达式求值（中缀转后缀 + 后缀求值）是栈最经典的综合应用，转换表要能手推。
- 递归的底层就是栈，理解这一点，后面学函数调用与中断现场保存会一通百通。
下一篇：数组与特殊矩阵压缩
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。