📚 Stack and Queue Essentials | 栈与队列考点精讲
In IB and AQA Computer Science, stacks and queues are fundamental abstract data types (ADTs) that underpin many algorithms and system processes. A solid grasp of their structure, operations, and real-world applications is crucial for tackling topics like recursion, scheduling, and memory management. This revision guide covers key concepts, implementation strategies, complexity analysis, and exam-style tips to help you master these data structures.
在IB与AQA计算机科学中，栈与队列是支撑众多算法和系统进程的基础抽象数据类型。透彻理解它们的结构、操作和实际应用，是攻克递归、调度、内存管理等主题的关键。本复习指南涵盖核心概念、实现策略、复杂度分析及应试技巧，助你全面掌握这两种数据结构。
1. Introduction to Stacks and Queues | 栈与队列简介
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle: the last element added is the first one to be removed. Think of a stack of plates in a cafeteria – you can only take the top plate, and you add new plates on top. In contrast, a queue follows First-In-First-Out (FIFO): the first element added is the first to be removed, just like a line of customers waiting at a checkout.
栈是一种遵循后进先出（LIFO）原则的线性数据结构：最后加入的元素最先被移除。想象自助餐厅里的一摞盘子——你只能取最上面的盘子，也只能把新盘子放在顶部。而队列则遵循先进先出（FIFO）原则：最先加入的元素最先被移除，就像在收银台排队等候的顾客一样。
Both are abstract data types, meaning they define the operations allowed (such as push, pop, enqueue, dequeue) without specifying how these operations are implemented. The implementation can be array-based or linked-list-based, each with its own trade-offs in terms of time complexity and memory usage.
两者都是抽象数据类型，这意味着它们定义了允许的操作（如压入、弹出、入队、出队），但不规定这些操作如何实现。实现方式可以是基于数组或基于链表，两者在时间复杂度和内存使用上各有优劣。
2. Stack Operations | 栈的操作
A stack typically supports the following core operations:
栈通常支持以下核心操作：
- push(item) – add an item to the top of the stack. If the stack is full (in an array implementation with a fixed capacity), an overflow error occurs.
- push(item) – 将一个元素添加到栈顶。如果栈已满（在固定容量的数组实现中），则发生上溢错误。
- pop() – remove and return the top item. If the stack is empty, an underflow error occurs.
- pop() – 移除并返回栈顶元素。如果栈为空，则发生下溢错误。
- peek() or top() – return the top item without removing it. Does not modify the stack.
- peek() 或 top() – 返回栈顶元素但不移除它。不修改栈。
- isEmpty() – check whether the stack contains any elements.
- isEmpty() – 检查栈是否为空。
- isFull() – (primarily for array-based stacks) check if the stack has reached its maximum capacity.
- isFull() – （主要用于数组实现）检查栈是否达到最大容量。
For IB/AQA exams, you should be able to trace these operations on a diagram and write pseudocode for them under different implementations.
在IB/AQA考试中，你需要能够在图上追踪这些操作，并能针对不同实现方式写出伪代码。
3. Array-Based Stack Implementation | 数组实现栈
An array-based stack uses a fixed-size array to store elements and an integer variable (often called top) to track the index of the topmost element. Initially, top is set to -1 (empty stack). The push operation increments top and writes the new element at that index; pop returns the element at top and decrements top. The key limitation is a static capacity, which can lead to overflow if not checked. All basic operations run in O(1) time.
基于数组的栈使用固定大小的数组存储元素，并用一个整型变量（通常称为 top）跟踪栈顶元素的索引。初始时 top 设为 -1（空栈）。压入操作将 top 加 1 并在该索引处写入新元素；弹出操作返回 top 索引处的元素并将 top 减 1。这种实现的主要局限是容量固定，若不加检查可能导致溢出。所有基本操作的时间复杂度均为 O(1)。
Example pseudocode for push and pop:
推送与弹出操作的示例伪代码：
procedure push(item)
if top = MAX_SIZE - 1 then
output "Stack overflow"
else
top ← top + 1
stack[top] ← item
end if
end procedure
procedure push(item)
if top = MAX_SIZE - 1 then
输出 "Stack overflow"
else
top ← top + 1
stack[top] ← item
end if
end procedure
4. Linked-List-Based Stack Implementation | 链表实现栈
When a stack is implemented with a singly linked list, no predefined capacity is needed. The top of the stack corresponds to the head of the list. Push inserts a new node at the head, and pop removes the head node. This dynamic allocation avoids overflow issues (except when system memory is exhausted) and still guarantees O(1) time for push and pop. Each node requires extra memory for the pointer, but the stack can grow as needed.
使用单链表实现栈时，无需预设容量。栈顶对应链表的头节点。压入操作在链表头部插入新节点，弹出操作则移除头节点。这种动态分配避免了溢出问题（除非系统内存耗尽），并且同样保证了压入和弹出的 O(1) 时间复杂度。每个节点需要额外的指针内存，但栈可按需增长。
Students should be able to compare the two implementations, especially in terms of space overhead and the impossibility of overflow in linked stacks. IB exam questions may ask for a diagram showing the state of the stack after a series of operations.
学生应能够比较两种实现方式，尤其是空间开销和链表栈无溢出的特性。IB 考试中可能会要求画出经过一系列操作后栈的状态图。
5. Key Applications of Stacks | 栈的主要应用
Stacks appear in many areas of computer science:
栈在计算机科学的许多领域中都有应用：
- Function call management: When a function is called, its local variables and return address are pushed onto the call stack. When the function returns, its frame is popped. This is essential for recursion.
- 函数调用管理：每当调用一个函数，其局部变量和返回地址被压入调用栈。函数返回时，其栈帧被弹出。这是递归运行的基础。
- Undo/redo features: Each action is pushed onto a stack. Undo pops the last action; redo typically uses a second stack.
- 撤销/重做功能：每执行一个操作便压入栈中。撤销操作弹出最近的动作；重做通常借助第二个栈实现。
- Expression evaluation: Stacks are used to convert infix expressions to postfix (Reverse Polish Notation) and to evaluate postfix or prefix expressions.
- 表达式求值：栈用于将中缀表达式转换为后缀（逆波兰表示法）以及计算后缀或前缀表达式。
- Bracket matching: Compilers use a stack to check whether parentheses, braces, and brackets are properly nested and balanced.
- 括号匹配：编译器利用栈检查圆括号、花括号和方括号是否正确嵌套与平衡。
Understanding these applications helps you answer scenario-based questions that require you to identify the appropriate data structure.
理解这些应用能帮助你在情景题中选出合适的数据结构。
6. Queue Operations | 队列的操作
A queue primarily supports two operations: enqueue (add an element to the rear) and dequeue (remove an element from the front). Additional helper operations include peek (view the front element without removing it), isEmpty, and isFull. All core operations should be performed in constant time O(1) for an efficient queue implementation.
队列主要支持两种操作：enqueue（将元素加入队尾）和 dequeue（从队头移除元素）。辅助操作包括 peek（查看队头元素但不移除）、isEmpty 和 isFull。一个高效的队列实现应保证所有核心操作的时间复杂度为 O(1)。
In a queue, both the front and rear are required. The front points to the first element for removal, while the rear points to the last element added. When dequeue is called, the front advances; when enqueue is called, the rear advances. This is straightforward in a linked-list implementation but needs careful handling in arrays to avoid wasted space.
在队列中，需要同时维护队头（front）和队尾（rear）。队头指向将要移除的第一个元素，队尾指向最后一个加入的元素。调用 dequeue 时队头前移；调用 enqueue 时队尾前移。这在链表实现中很简单，但在数组实现中需要谨慎处理以避免空间浪费。
7. Array-Based Queue and the Circular Solution | 数组实现队列与循环方案
A naive array-based queue uses a linear array where elements are added at the rear and removed from the front. However, after several enqueue and dequeue operations, the front of the array becomes empty but cannot be reused, leading to a "false overflow" situation. The solution is a circular queue, where the array is treated as circular: the rear pointer wraps around to the beginning of the array when it reaches the end. The modulo operator is used to calculate the new index: rear ← (rear + 1) mod MAX.
简单的数组队列使用线性数组，元素被加入队尾，从队头移除。然而，经过多次入队和出队操作后，数组前部会变空却无法重用，导致“假溢出”。解决方法是循环队列，即将数组视为环形：当队尾指针到达数组末尾时会绕回到开头。新索引用取模运算计算：rear ← (rear + 1) mod MAX。
front = -1 initially). These conditions must be clearly understood for tracing exercises.
在循环队列中，一种常见的设计是预留一个空位来区分满队列与空队列：当 (rear + 1) mod MAX = front 时队列满，当 front = rear（或初始时 front = -1）时队列空。在追踪练习中必须清楚掌握这些条件。
8. Linked-List-Based Queue Implementation | 链表实现队列
A queue implemented with a singly linked list maintains two external pointers: front points to the first node (to be dequeued), and rear points to the last node (where enqueue occurs). Enqueue creates a new node and attaches it after rear, then updates rear. Dequeue removes the node at front and advances front. Both operations are O(1). The list can grow dynamically, so no overflow occurs until memory is exhausted.
用单链表实现队列时，维护两个外部指针：front 指向第一个节点（待出队），rear 指向最后一个节点（入队位置）。入队操作创建新节点并将其链接到 rear 之后，然后更新 rear。出队操作移除 front 节点并前移 front。两个操作的时间复杂度都是 O(1)。链表可动态增长，因此在内存耗尽之前不会发生溢出。
In exam diagrams, you should show how the front and rear pointers move. A common mistake is forgetting to update rear when dequeuing from a single-element queue, which would leave rear pointing to a removed node.
在考试图示中，你需要展示 front 和 rear 指针如何移动。一个常见的错误是当队列只有一个元素时，出队后忘记更新 rear，导致 rear 指向已被移除的节点。
9. Circular Queue Advantages | 循环队列的优点
The circular queue eliminates the problem of wasted space found in a linear array queue. Since enqueue and dequeue operations only move the front and rear pointers without shifting elements, they remain O(1). The fixed size of the array means the maximum number of elements that can be stored is MAX-1 (if one slot is used for the full/empty check). In real-time systems and buffering (e.g., keyboard buffer or streaming data), circular queues provide constant-time performance with predictable memory usage.
循环队列消除了线性数组队列中空间浪费的问题。由于入队和出队操作仅移动 front 与 rear 指针，不涉及元素移位，因此保持 O(1) 时间。数组的固定容量意味着可存储的最大元素数为 MAX-1（若保留一个槽位用于判断满/空）。在实时系统和缓冲应用中（如键盘缓冲区或流式数据），循环队列以可预测的内存使用提供恒定时间性能。
When tracing circular queues, always compute the indices using modulo arithmetic and keep track of the number of elements visually; this helps avoid off-by-one errors that are frequently tested in multiple-choice questions.
追踪循环队列时，务必使用取模运算计算索引，并从图中跟踪元素个数；这有助于避免多项选择题中经常出现的“差一”错误。
10. Priority Queues | 优先队列
A priority queue is an extension where each element has an associated priority, and elements are removed in order of highest priority rather than simple FIFO. It is an abstract data type; typical implementations use a heap data structure for efficient O(log n) insertion and removal. However, simpler (but less efficient) implementations can use an unordered array (O(1) enqueue, O(n) dequeue) or a sorted array (O(n) enqueue, O(1) dequeue). Priority queues are essential in algorithms like Dijkstra’s shortest path and in operating system process scheduling.
优先队列是队列的一种扩展：每个元素都关联一个优先级，元素按照优先级最高的顺序被移除，而非简单的 FIFO。它是一种抽象数据类型；典型的实现使用堆数据结构，以 O(log n) 的高效时间完成插入和移除。不过，更简单的（但效率较差的）实现可以使用无序数组（入队 O(1)，出队 O(n)）或有序数组（入队 O(n)，出队 O(1)）。优先队列在 Dijkstra 最短路径算法和操作系统的进程调度等场景中至关重要。
For IB/AQA, you are expected to describe the concept and behavior of a priority queue, give examples of its use, and possibly compare the performance of different underlying data structures. You do not need to implement heap operations from scratch unless specifically required by your syllabus.
在 IB/AQA 考试中，你需要描述优先队列的概念和行为，举例说明其用途，并可能比较不同底层数据结构的性能。除非考纲明确要求，你不必从头实现堆操作。
11. Complexity Analysis (Big O) | 复杂度分析（大 O）
Understanding the time complexity of stack and queue operations is essential for selecting the right implementation. The table below summarizes the typical complexities for the core operations:
理解栈和队列各项操作的时间复杂度对于选择正确的实现方式至关重要。下表总结了核心操作的典型复杂度：
| Operation | Array Stack | Linked Stack | Circular Queue | Linked Queue |
|---|---|---|---|---|
| Push / Enqueue | O(1) | O(1) | O(1) | O(1) |
| Pop / Dequeue | O(1) | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) | O(1) |
| isEmpty | O(1) | O(1) | O(1) | O(1) |
| Space | O(n), fixed | O(n), dynamic + pointer overhead | O(n), fixed | O(n), dynamic + pointer overhead |
Note that all basic operations are constant time; the main differences lie in memory flexibility and the risk of overflow. Priority queues differ: depending on implementation, insertion and removal range from O(n) to O(log n).
请注意，所有基本操作都是常数时间；主要区别在于内存的灵活性以及溢出的风险。优先队列有所不同：取决于实现方式，插入和移除操作的时间复杂度从 O(n) 到 O(log n) 不等。
12. Comparison and Exam Tips | 对比与应试技巧
Key differences: A stack restricts access to one end (top) and follows LIFO, making it ideal for reversing sequences and tracking state in recursive algorithms. A queue provides access at both ends (front and rear) and follows FIFO, making it suitable for scheduling and buffering tasks in the order they arrive.
关键区别：栈仅允许在一端（栈顶）操作，遵循 LIFO，非常适合逆转顺序和跟踪递归算法中的状态。队列允许在两端（队头和队尾）操作，遵循 FIFO，适合按到达顺序进行调度和缓冲任务。
Exam tips for IB/AQA:
IB/AQA 应试技巧：
- Be prepared to trace a sequence of operations on a stack or queue diagram. Show the state of the structure step by step.
- 做好准备，在栈或队列图示上追踪一系列操作。逐步展示结构的状态。
- Know the conditions for overflow and underflow in each implementation, and be able to propose error-handling mechanisms.
- 了解每种实现中发生溢出和下溢的条件，并能够提出错误处理机制。
- For circular queues, master the modulo arithmetic and the empty/full detection logic; it is a favorite topic for multiple-choice questions.
- 对于循环队列，务必掌握取模运算和空/满检测逻辑；这是多项选择题的常考内容。
- Link the data structures to real scenarios: call stack, undo history, printer spooler, CPU scheduling. This will help you justify your design choices in long-answer questions.
- 将数据结构与实际场景联系起来：调用栈、撤销历史、打印后台处理、CPU 调度。这有助于在长篇答题中证明你的设计选择。
- Do not confuse stack overflow with the Stack Overflow website! In computing, it means trying to push onto a full stack, while queue overflow means enqueuing into a full linear queue.
- 不要混淆栈溢出（stack overflow）与 Stack Overflow 网站！在计算中，它指尝试向已满栈压入元素；而队列溢出指向已满线性队列入队。
By mastering both the abstract behavior and concrete implementations, you will be well equipped to answer any exam question on stacks and queues with confidence.
通过掌握抽象行为和具体实现，你将能够自信地回答考试中任何关于栈与队列的问题。
Published by TutorHao | IB Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图