当前位置：首页 > news >正文

数据结构：（二）逻辑之门——栈与队列

news 2026/5/11 16:50:51

一、栈 (Stack)：最后进，最先出

栈是仅限在栈顶（Top）进行插入或删除操作的线性表。其核心特性是LIFO (Last In First Out)。

1. 顺序栈的指针含义

在 C 语言实现中，top指针的定义至关重要。

习惯定义：top指向栈顶元素的下一个位置。
空栈条件：S.top == S.base。
满栈条件：S.top - S.base >= S.stacksize。

2. 核心算法：入栈与出栈

// 入栈 (Push) Status Push(SqStack &S, ElemType e) { if (S.top - S.base >= S.stacksize) return ERROR; // 满栈 *S.top++ = e; // 先把 e 放入 top 指向的位置，然后 top 指针自增 1 return OK; } // 出栈 (Pop) Status Pop(SqStack &S, ElemType &e) { if (S.top == S.base) return ERROR; // 空栈 e = *--S.top; // top 先减 1 指向栈顶元素，再取出赋值给 e return OK; }

二、栈的顶级应用：括号匹配 (Parenthesis Matching)

这是一个典型的“后进先出”场景：最后出现的左括号，必须最先被匹配掉。

算法精髓：

遇到左括号：它是期待被匹配的，先“存”起来 ——压栈。
遇到右括号：它来寻找匹配对象，找谁？找最近出现的那个左括号 ——弹出栈顶检查。
匹配失败的三种情况：
- 遇到右括号但栈已空（右括号多余）。
- 弹出的左括号与当前右括号不匹配（如[与)）。
- 遍历结束但栈不为空（左括号多余）。

三、队列 (Queue)：先进先出，公平至上

队列是只允许在队尾 (Rear)插入、队头 (Front)删除的线性表。其特性是FIFO (First In First Out)。

1. 循环队列 (Circular Queue)：解决“假溢出”

在顺序存储下，随着出队入队，指针会一直向后移动直到超出界限。为了重复利用空间，我们将数组想象成一个“环”。

核心公式：利用模运算%。
指针后移：i = (i + 1) % MAXSIZE;

2. 难点：如何区分队空还是队满？

当front == rear时，队列可能空也可能满。

严版教材方案：牺牲一个单元。

队空：Q.front == Q.rear。
队满：(Q.rear + 1) % MAXSIZE == Q.front。
队列长度计算（高频考点）：(Q.rear - Q.front + MAXSIZE) % MAXSIZE。

四、深度复盘：递归与栈的灵魂绑定

很多初学者不理解为什么递归需要栈。

详细注释：
当一个函数（调用者）调用另一个函数（被调用者）时，系统必须保存调用者的“断点”信息（局部变量、返回地址等）。这些信息被压入系统栈。被调用者执行完后，从栈顶弹出信息恢复调用者。
递归就是一种特殊的嵌套调用，它不断地把每一层的信息压栈。如果递归没有出口，栈就会被撑爆，产生著名的Stack Overflow错误。

五、今日对比小结

结构	逻辑规则	插入/删除位置	典型应用
栈	LIFO	都在栈顶	括号匹配、表达式求值、递归
队列	FIFO	队尾入、队头出	打印机任务、缓冲区、BFS(广搜)