📚 Stacks and Queues: IB WJEC Computer Science Exam Revision | 栈与队列考点精讲
A stack and a queue are two of the most fundamental abstract data types (ADTs) in computer science. They represent ordered collections of elements with restricted access patterns, and mastering them is essential for IB and WJEC examinations. This revision guide walks through every key concept, implementation detail, application area, and common examination pitfall to ensure you can confidently answer any stack or queue question.
栈和队列是计算机科学中最基本的两种抽象数据类型(ADT)。它们是有序元素集合，但访问模式受限，掌握它们对于 IB 和 WJEC 考试至关重要。本复习指南将梳理每一个关键概念、实现细节、应用领域以及常见的考试易错点，确保你能自信地回答任何关于栈和队列的题目。
1. Data Structures and Abstract Data Types (ADTs) | 数据结构与抽象数据类型简介
A data structure is a concrete implementation of how data is organised in memory, while an abstract data type (ADT) specifies what data is stored and what operations can be performed, without dictating how those operations are implemented. Stacks and queues are classic ADTs: we define their behaviour (push/pop for stacks, enqueue/dequeue for queues) independently of whether we use arrays or linked lists to realise them.
数据结构是数据在内存中组织方式的具体实现，而抽象数据类型(ADT)规定了存储何种数据以及能够执行哪些操作，但不规定这些操作如何实现。栈和队列是典型的 ADT：我们定义它们的行为（栈的 push/pop，队列的 enqueue/dequeue），而不用管底层是用数组还是链表实现的。
The separation of interface from implementation allows programmers to use stacks and queues without worrying about internal details. In IB and WJEC exams, you may be asked to identify the difference between an ADT and its implementation, or to justify why a particular implementation is more suitable for a given scenario.
接口与实现的分离使程序员无需关心内部细节就能使用栈和队列。在 IB 和 WJEC 考试中，你可能会被要求区分 ADT 与其实现，或者论证为什么某种实现方式更适合某个特定场景。
2. Understanding Stacks: Definition and Operations | 理解栈：定义与操作
A stack is a last-in, first-out (LIFO) structure. The only accessible element is the one most recently added, typically called the ‘top’. The fundamental operations are push(item) which adds an item to the top, pop() which removes and returns the top item, and peek() or top() which returns the top item without removing it. An additional operation, isEmpty(), checks whether the stack contains any elements.
栈是一种后进先出(LIFO)的结构。唯一可访问的元素是最近添加的元素，通常称为“栈顶”。基本操作包括 push(item)——将一个元素添加到栈顶，pop()——移除并返回栈顶元素，以及 peek() 或 top()——返回栈顶元素但不将其移除。还有一个附加操作 isEmpty()，用于检查栈是否包含任何元素。
Stack operations must handle two error conditions: underflow, which occurs when pop() is called on an empty stack, and overflow, which can occur when pushing onto a fixed-size array implementation that has reached its capacity. Dynamically linked implementations generally avoid overflow but still need underflow checking.
栈操作必须处理两种错误情况：下溢，即对空栈调用 pop()；溢出，当向固定大小的数组实现的栈中 push 元素且容量已满时可能发生。动态链表实现通常可以避免溢出，但仍需进行下溢检查。
In IB and WJEC pseudocode, you will often see a stack represented as an abstract object with methods. For example: myStack.push(5), value = myStack.pop(). The exam expects you to trace through such operations and show the state of the stack at each step.
在 IB 和 WJEC 的伪代码中，你经常会看到栈被表示为一个抽象对象并带有方法。例如：myStack.push(5), value = myStack.pop()。考试要求你能够追踪这些操作，并在每一步展示栈的状态。
3. Stack Implementation: Arrays vs Linked Lists | 栈的实现：数组与链表
A stack can be implemented using a static array with a top-of-stack pointer (an integer index) that tracks the next free position. Pushing increments this pointer and stores the item; popping decrements it. Time complexity for both operations is O(1), but the maximum size is fixed. Overflow must be detected by comparing the pointer against the array length.
栈可以使用静态数组和一个栈顶指针（一个整数索引）来实现，该指针跟踪下一个空闲位置。压栈操作递增指针并存储元素；弹栈操作递减指针。两种操作的时间复杂度均为 O(1)，但最大容量是固定的。必须通过将指针与数组长度进行比较来检测溢出。
Using a singly linked list, 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. Memory is allocated dynamically, so stack size is limited only by available heap memory. The trade-off is the extra memory overhead for storing node references.
使用单向链表实现时，栈顶对应链表的头节点。压栈在头部插入新节点，弹栈移除头节点。内存动态分配，因此栈的大小仅受可用堆内存的限制。代价是需要为存储节点引用付出额外的内存开销。
Examination questions may ask you to draw diagrams of array-based stacks after a series of operations, or to write code/pseudocode for push and pop for a linked-list-based stack. Be precise about pointer updates: for linked list pop, you need a temporary pointer to the old head to avoid memory leaks (in languages like C++).
考试题目可能要求你在完成一系列操作后画出基于数组的栈的示意图，或者为基于链表的栈编写 push 和 pop 的代码/伪代码。准确地更新指针非常重要：对于链表的弹栈操作，需要用一个临时指针指向旧的头节点以避免内存泄漏（如在 C++ 等语言中）。
4. Applications of Stacks | 栈的应用
Stacks are used wherever a LIFO order naturally arises. The most prominent examples include function call management (call stack), expression evaluation and syntax parsing, undo mechanisms in editors, and backtracking algorithms such as maze solving. Understanding these applications helps in recognising when to choose a stack in algorithm design.
栈被应用在所有自然产生 LIFO 顺序的场景中。最突出的例子包括函数调用管理（调用栈）、表达式求值和语法解析、编辑器中的撤销操作以及迷宫求解等回溯算法。理解这些应用有助于在算法设计时判断何时应该选用栈。
In the call stack, each function invocation creates a stack frame containing local variables, parameters, and the return address. When a function calls another, a new frame is pushed; when a function returns, its frame is popped. This is why infinite recursion causes a stack overflow error. IB and WJEC may ask you to explain this mechanism.
在调用栈中，每次函数调用都会创建一个栈帧，其中包含局部变量、参数和返回地址。当一个函数调用另一个函数时，新的栈帧被压入；当函数返回时，其栈帧被弹出。这就是无限递归导致栈溢出错误的原因。IB 和 WJEC 可能会要求你解释这一机制。
For expression evaluation, stacks convert infix expressions (e.g., 3 + 4 × 2) to postfix (3 4 2 × +) and then evaluate them. This is a classic exam question: trace the state of the operator stack during conversion. Another common task is checking balanced parentheses using a stack, where each ‘(‘ pushes onto the stack and each ‘)’ pops.
在表达式求值中，栈将中缀表达式（如 3 + 4 × 2）转换为后缀表达式（3 4 2 × +）然后再求值。这是一类经典的考试题目：追踪转换过程中运算符栈的状态。另一个常见任务是使用栈检查括号匹配，每次遇到 ‘(‘ 时压栈，每次遇到 ‘)’ 时弹栈。
5. Understanding Queues: Definition and Operations | 理解队列：定义与操作
A queue is a first-in, first-out (FIFO) data structure. The first element added is the first one to be removed. Operations include enqueue(item) which adds an item to the rear of the queue, dequeue() which removes and returns the front element, and peek() which inspects the front without removal. An isEmpty() check is essential for avoiding underflow.
队列是一种先进先出(FIFO)的数据结构。最先添加的元素将最先被移除。操作包括 enqueue(item)——将一个元素添加到队尾，dequeue()——移除并返回队首元素，以及 peek()——查看队首元素但不将其移除。isEmpty() 检查对于避免下溢至关重要。
Queues model real-world waiting lines, such as print jobs sent to a printer, requests to a web server, or processes in a CPU scheduler. The strict FIFO discipline ensures fairness: no item can ‘jump the queue’. In examinations, tracing queue states after a sequence of enqueue and dequeue operations is fundamental.
队列用来对现实世界的排队进行建模，例如发送到打印机的打印作业、对 Web 服务器的请求或 CPU 调度器中的进程。严格的 FIFO 规则确保了公平性：没有任何元素可以“插队”。在考试中，追踪一系列入队和出队操作后的队列状态是一项基本技能。
Just like stacks, queues can suffer from underflow when dequeuing from an empty queue. Overflow can also occur in array-based implementations when the rear index reaches the end of the array, even if space is available at the front. This leads to the need for a circular queue design.
和栈一样，当从空队列中出队时会发生下溢。在基于数组的实现中，即使队首还有可用空间，如果队尾索引到达数组末尾，也可能发生溢出。这就引出了循环队列的设计需求。
6. Queue Implementation: Linear and Circular | 队列的实现：线性与循环
A linear array-based queue uses a ‘front’ index pointing to the next item to be removed and a ‘rear’ index pointing to the next empty slot. Initially both are 0. Enqueue places an item at the rear and increments the rear index; dequeue reads from the front and increments the front index. However, as the front moves forward, unused spaces accumulate at the beginning, leading to false overflow.
基于数组的线性队列使用一个“队首”索引指向下一个将被移除的元素，以及一个“队尾”索引指向下一个空位。初始时两者均为 0。入队将元素放入队尾并递增队尾索引；出队从队首读取并递增队首索引。但是，随着队首向前移动，数组开头会积累未使用的空间，导致假溢出。
To solve this, a circular queue treats the array as if it were a circle. When the rear index reaches the end, it wraps around to 0 if space is available. The number of elements is tracked, or a condition is used to distinguish between empty and full states. A common convention is to keep one slot empty to differentiate full (rear next equals front) from empty (front equals rear).
为了解决这个问题，循环队列将数组视为一个环形。当队尾索引到达末尾时，如果有可用空间，它就会回绕到 0。通过跟踪元素数量，或使用一种条件来区分空和满的状态。一种常见的约定是保留一个空槽，以区分满（队尾的下一个等于队首）和空（队首等于队尾）。
WJEC often requires calculations involving the modulo operator (%) when incrementing indices in a circular queue. For example, rear = (rear + 1) % size. Familiarity with these formulas and being able to trace circular queue states is vital for the exam.
WJEC 经常要求在循环队列中递增索引时使用取模运算符 (%) 进行计算。例如，rear = (rear + 1) % size。熟悉这些公式并能够追踪循环队列的状态对考试至关重要。
A linked-list implementation of a queue uses two pointers: front (head) and rear (tail). Enqueue appends to the tail, and dequeue removes from the head. All operations are O(1), and no size limit exists (apart from memory). The exam may ask you to compare array and linked-list implementations, considering memory usage and speed.
队列的链表实现使用两个指针：队首（头）和队尾（尾）。入队操作在尾部追加，出队操作从头部移除。所有操作均为 O(1)，且没有大小限制（除内存外）。考试可能会要求你比较数组和链表实现，并考虑内存使用和速度。
7. Priority Queues and Their Use | 优先级队列及其应用
A priority queue is an ADT where each element has an associated priority. Elements are removed based on their priority rather than their arrival order: the highest (or lowest) priority element is dequeued first. This is not a simple FIFO structure and is typically implemented using a data structure called a binary heap.
优先级队列是一种 ADT，其中每个元素都有一个关联的优先级。元素基于其优先级而非到达顺序被移除：具有最高（或最低）优先级的元素最先出队。这并非简单的 FIFO 结构，通常使用一种名为二叉堆的数据结构来实现。
Common applications include task scheduling where certain processes are more urgent, Dijkstra’s shortest path algorithm, and hospital emergency rooms where patients are treated by severity. In WJEC and IB, you might be asked to contrast a standard queue with a priority queue, or to trace a simple priority queue using an ordered list implementation.
常见的应用包括某些进程更为紧急的任务调度、Dijkstra 最短路径算法以及按病情严重程度接诊的急诊室。在 WJEC 和 IB 考试中，你可能会被要求对比标准队列和优先级队列，或者追踪使用有序列表实现的简单优先级队列。
While a priority queue is often built on a heap for O(log n) insertion and O(1) peek-max, a naive implementation could use an unsorted or sorted array. An unsorted array gives O(1) enqueue but O(n) dequeue (to search for the highest priority), while a sorted array gives O(n) enqueue (to shift elements) but O(1) dequeue. The exam expects you to understand these trade-offs.
虽然优先级队列通常基于堆构建，以实现 O(log n) 的插入和 O(1) 的查看最大值，但一种简单的实现也可以使用未排序或已排序的数组。未排序数组入队为 O(1)，但出队为 O(n)（用于搜索最高优先级），而已排序数组入队为 O(n)（用于移动元素），但出队为 O(1)。考试要求你理解这些权衡。
8. Comparing Stacks and Queues | 栈与队列的比较
Stacks and queues differ fundamentally in their removal order: LIFO vs FIFO. This single difference leads to completely distinct usage patterns. Stacks are ideal for reversing, tracking state in recursive calls, and depth-first search; queues enable breadth-first search, buffering, and sequential processing.
栈和队列在移除顺序上有着根本性区别：LIFO 与 FIFO。这一区别导致了完全不同的使用模式。栈非常适合反转、跟踪递归调用中的状态以及深度优先搜索；队列则适用于广度优先搜索、缓冲和顺序处理。
Below is a concise comparison table that captures the essential distinctions examiners expect you to know.
下面是一个简洁的比较表，包含了考官期望你掌握的关键区别。
| Feature / 特性 | Stack | Queue |
|---|---|---|
| Order / 顺序 | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Insertion / 插入 | push (add to top) | enqueue (add to rear) |
| Removal / 移除 | pop (remove from top) | dequeue (remove from front) |
| Key Example / 关键示例 | Undo, call stack, expression evaluation | Print queue, keyboard buffer, BFS |
| Array Implementation / 数组实现 | Single pointer (top) | Two pointers (front and rear); often circular |
Examiners frequently ask ‘Justify why a stack/queue is appropriate’ for a given scenario. Be ready to refer to the required access order: if the most recently seen item must be processed first, choose a stack; if items must be processed in the order they arrived, choose a queue.
考官经常要求“证明栈/队列适用于某个给定场景”。要准备好论及所需的访问顺序：如果最近看到的项必须被最先处理，则选择栈；如果项必须按其到达的顺序处理，则选择队列。
9. Common Exam Questions and Pitfalls | 常见考题与易错点
Typical exam tasks include: tracing a series of push/pop or enqueue/dequeue operations and drawing the resulting state; writing pseudocode for implementing a stack or queue using arrays or linked lists; converting algorithms from iterative to recursive using stacks; and diagnosing overflow/underflow scenarios. Make sure you practise these step-by-step to avoid losing marks.
典型的考试任务包括：追踪一系列 push/pop 或 enqueue/dequeue 操作并画出结果状态；为使用数组或链表实现栈或队列编写伪代码；使用栈将算法从迭代转换为递归；以及诊断溢出/下溢情况。确保你逐步练习这些，以避免丢分。
A frequent pitfall is incorrectly updating pointers in linked-list implementations. When popping from a stack, the ‘top’ must be moved to top.next before the old node is deleted. In a queue, you must handle the special case of a single-element queue carefully so that ‘rear’ is set to null when the queue becomes empty.
一个常见的易错点是在链表实现中错误地更新指针。在栈的出栈操作中，必须先将“栈顶”移动到 top.next，然后再删除旧节点。在队列中，必须小心处理只有一个元素的特殊情况，以便在队列变空时将“队尾”设置为 null。
For circular queues, students often miscompute the condition for full vs empty. Remember: if you reserve one slot, the queue is full when (rear + 1) % size == front, and empty when front == rear. In WJEC pseudocode questions, you are expected to include these checks explicitly. Also, be careful with tracing: dequeue should return the front element and then advance front, not the other way round.
对于循环队列，学生经常错误地判断满和空的条件。请记住：如果保留一个空槽，当 (rear + 1) % size == front 时队列为满，当 front == rear 时队列为空。在 WJEC 伪代码题中，要求你明确地包含这些检查。同时，小心追踪：出队操作应先返回队首元素，再移动队首指针，而不是反过来。
10. Summary and Revision Tips | 总结与复习技巧
Stacks and queues are simple yet powerful ADTs that appear throughout computer science. Focus on understanding their behaviour at a conceptual level, being able to trace operations and state, and knowing the performance implications of different implementations. For the exam, always justify your choice of data structure by referring to the access pattern required.
栈和队列是简单而强大的 ADT，贯穿于整个计算机科学领域。重点是在概念层面上理解它们的行为，能够追踪操作和状态，并了解不同实现方式的性能影响。在考试中，始终要根据所需的访问模式来证明你对数据结构的选择。
Regularly practise drawing stack frames during recursive calls and circular queue diagrams with wrap-around indices. Use past papers to become comfortable with the style of pseudocode expected. Pay attention to vocabulary: ‘top’ for stacks, ‘front’ and ‘rear’ for queues; ‘overflow’ and ‘underflow’ for error conditions. Finally, remember that IB and WJEC value clarity and precision: label your diagrams, show your index updates, and write clean pseudocode.
经常练习绘制递归调用期间的栈帧以及带有回绕索引的循环队列图。利用历年真题来熟悉所要求的伪代码风格。注意术语：栈用“top”，队列用“front”和“rear”；错误情况用“overflow”和“underflow”。最后，请记住 IB 和 WJEC 考试重视清晰度和准确性：为你的图表打上标签，展示索引更新过程，并书写干净的伪代码。
A strong grasp of stacks and queues will not only secure marks on direct questions but also strengthen your ability to tackle more complex topics like trees, graphs, and algorithmic problem-solving. Think of them as the fundamental building blocks of controlled data flow.
牢固掌握栈和队列不仅能在直接相关的问题上得分，还能增强你应对树、图以及算法解决问题等更复杂专题的能力。将它们视为受控数据流的基本构建块。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply