📚 Stack and Queue: Key Points for A-Level WJEC Computer Science | A-Level WJEC 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) that appear throughout the WJEC A-Level Computer Science specification. Mastering their principles, operations, implementations, and applications is essential for both the theoretical paper and any practical programming tasks. This revision guide breaks down every key concept, provides clear examples, and highlights common pitfalls to ensure you are fully prepared for your exam.
栈和队列是 WJEC A-Level 计算机科学大纲中贯穿始终的基础抽象数据类型。掌握它们的原理、操作、实现方法和应用场景，对于理论考试和实践编程任务都至关重要。本复习指南将拆解每一个核心概念，配以清晰的示例，并强调常见的易错点，帮助你在考试中万无一失。
1. Understanding Stacks | 理解栈
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you can only add a new plate to the top, and you can only remove the topmost plate. The last item placed onto the stack is always the first one to be taken off. This restricted access makes stacks predictable and efficient for certain types of problems.
栈是一种遵循后进先出 (LIFO) 原则的线性数据结构。想象一叠盘子：你只能在顶部添加新盘子，也只能移除最顶部的盘子。最后放入栈中的元素总是第一个被取出。这种受限的存取方式使栈在处理某类问题时既可控又高效。
In the WJEC specification, a stack is defined as an ADT that supports at least the following core operations: push (to add an item), pop (to remove and return the top item), and often peek (or top) to inspect the top item without removing it. Auxiliary operations such as checking whether the stack is empty (isEmpty) or full (isFull) are also important, particularly when implementing the stack with a static array.
在 WJEC 考纲中，栈被定义为一种至少支持以下核心操作的抽象数据类型：push（入栈，添加元素）、pop（出栈，移除并返回栈顶元素），通常还有 peek（或 top）用来查看栈顶元素而不移除它。辅助操作如检查栈是否为空 (isEmpty) 或已满 (isFull) 同样重要，尤其是在使用静态数组实现栈时。
2. Core Stack Operations | 栈的核心操作
1. Push(item): Places the given item onto the top of the stack. If the stack has a fixed capacity and is already full, a stack overflow error occurs, and the push operation is rejected.
1. 入栈 Push(元素)：将给定元素放到栈顶。如果栈具有固定容量且已满，将发生栈上溢错误，入栈操作被拒绝。
2. Pop(): Removes the top item from the stack and returns it. If the stack is empty, attempting to pop triggers a stack underflow error. The popped element is no longer stored in the stack.
2. 出栈 Pop()：从栈中移除顶部元素并返回它。如果栈为空，尝试出栈将触发栈下溢错误。出栈的元素不再存储在栈中。
3. Peek() or Top(): Returns the value of the top element without altering the stack. This is used when you need to check what is on top without modifying the stack's content. Underflow conditions still apply.
3. 查看栈顶 Peek() 或 Top()：返回栈顶元素的值而不改变栈。当你需要查看栈顶内容而不修改栈时使用。下溢条件依然适用。
4. isEmpty(): Returns true if the stack contains no elements; otherwise returns false. This is vital to prevent underflow.
4. 判空 isEmpty()：若栈中无元素则返回真；否则返回假。这对于防止下溢至关重要。
5. isFull(): Relevant only for fixed-size implementations. Returns true if the stack reaches its maximum capacity. Overflow can be avoided by checking isFull() before a push.
5. 判满 isFull()：仅与固定大小的实现有关。若栈达到最大容量则返回真。通过在执行入栈前检查 isFull() 可避免上溢。
All these operations run in constant time, O(1), provided the stack is implemented efficiently. This efficiency is one reason stacks are so widely used, especially in system-level programming.
如果栈实现得当，所有这些操作的时间复杂度均为常数级 O(1)。这种高效性是栈被广泛使用的原因之一，尤其是在系统级编程中。
3. Implementing Stacks | 栈的实现方法
Array-based implementation: A static array is allocated with a fixed size, and a variable (often called top) keeps track of the index of the last inserted element. Initially, top is set to -1 (empty stack). When pushing, top is incremented, and the new item is stored at data[top]. When popping, the item at data[top] is returned, and top is decremented. The stack is full when top equals the maximum index. This approach is memory efficient but fixed in size, which can lead to overflow if capacity is not carefully chosen.
基于数组的实现：分配一个固定大小的静态数组，并用一个变量（通常称为 top）跟踪最后一个插入元素的索引。初始时 top 设为 -1（空栈）。入栈时，top 加 1，新元素存入 data[top]。出栈时，返回 data[top] 处的元素，并将 top 减 1。当 top 等于最大索引时栈满。这种方法内存效率高，但大小固定，若容量选择不当可能导致溢出。
Linked list-based implementation: A dynamic structure where each node holds a data item and a pointer to the next node. The top of the stack is the head of the list. Pushing involves creating a new node, linking it to the current head, and updating the head pointer. Popping returns the head node's data and advances the head pointer to the next node. This method never suffers from overflow (memory permitting) and can grow or shrink as needed. However, memory overhead increases due to pointers.
基于链表的实现：一种动态结构，其中每个节点包含一个数据项和一个指向下一个节点的指针。栈顶即为链表的头节点。入栈时创建新节点，将其链接到当前头节点，并更新头指针。出栈时返回头节点的数据，并将头指针前移至下一个节点。此方法（在内存允许时）不会发生溢出，并能根据需要伸缩。但指针会带来额外的内存开销。
WJEC exam questions often ask you to draw diagrams showing the state of an array or linked list after a sequence of operations. You must clearly label the top pointer and show any unused cells or nodes. Tracing exercises are very common.
WJEC 考题经常要求你绘制序列操作后数组或链表状态的示意图。你必须清楚地标注 top 指针，并标出未使用的单元或节点。跟踪练习非常普遍。
4. Applications of Stacks | 栈的实际应用
Function call management (call stack): When a program calls a function, the return address, parameters, and local variables are pushed onto the call stack. When the function ends, this frame is popped, and execution resumes at the return address. This stack enables recursion and nested function calls. A stack overflow occurs if recursion goes too deep without base case, recalling the stack overflow error from implementation.
函数调用管理（调用栈）：当程序调用一个函数时，返回地址、参数和局部变量被压入调用栈。函数结束时，这一帧被弹出，程序从返回地址继续执行。这个栈使递归和嵌套函数调用成为可能。如果递归过深而没有基准情形，就会发生栈溢出，这与实现中的栈上溢错误相呼应。
Expression evaluation (Reverse Polish Notation): Stacks are used to evaluate postfix expressions. Operands are pushed onto the stack; when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back. For infix-to-postfix conversion, an operator stack is used to reorder symbols based on precedence.
表达式求值（逆波兰表示法）：栈用于计算后缀表达式。操作数被压入栈；遇到运算符时，弹出所需数量的操作数，执行运算，并将结果压回栈中。在中缀转后缀的转换中，使用运算符栈根据优先级重新排列符号。
Balanced parentheses checking: A stack can validate whether brackets, braces, and parentheses are correctly matched. Every opening symbol is pushed; for each closing symbol, the stack is popped and checked for a matching type. If the stack is empty at a pop attempt or is not empty at the end, the expression is malformed. This is a classic exam programming task.
括号匹配检查：栈可以验证圆括号、花括号和方括号是否正确匹配。每遇到一个开符号就压入栈；每遇到一个闭符号，就从栈中弹出并检查类型是否匹配。如果弹出时栈已空，或最终栈不为空，则表达式格式错误。这是经典的考试编程任务。
Undo functionality: Many applications implement an undo stack. Each user action is pushed onto the stack. When the user triggers undo, the most recent action is popped and reversed. This directly mirrors the LIFO nature of stacks.
撤销功能：许多应用程序通过撤销栈来实现该功能。每次用户操作都被压入栈。当用户触发撤销时，最近的操作被弹出并逆转。这直接反映了栈的后进先出特性。
5. Introduction to Queues | 队列简介
A queue is a linear data structure that operates on the First In, First Out (FIFO) principle. Items are added at the rear (also called the tail) and removed from the front (head), just like a line of people waiting: the person who has been waiting the longest is served first. This contrasts sharply with the LIFO behaviour of a stack.
队列是一种遵循先进先出 (FIFO) 原则的线性数据结构。元素在队尾（也称尾部）加入，从队首（头部）移除，就像排队等候的人群：等待时间最长的人最先得到服务。这与栈的后进先出行为形成鲜明对比。
Queues are also ADTs with a defined set of operations. The WJEC specification expects you to know enqueue (add to rear), dequeue (remove from front), and the associated checks for empty and full states. In many contexts, a peek at the front element is allowed.
队列同样是具有一组特定操作的抽象数据类型。WJEC 考纲要求你掌握入队（enqueue，在队尾添加）、出队（dequeue，从队首移除），以及相关的空和满状态检查。在许多情况下，允许查看队首元素。
6. Core Queue Operations | 队列的核心操作
1. Enqueue(item): Inserts the given item at the rear of the queue. If the queue has a fixed capacity and is already full, an overflow error occurs.
1. 入队 Enqueue(元素)：将给定元素插入到队尾。若队列容量固定且已满，则发生溢出错误。
2. Dequeue(): Removes and returns the item at the front of the queue. If the queue is empty, dequeuing causes an underflow error. The front item is no longer held in the queue.
2. 出队 Dequeue()：移除并返回队首元素。若队列为空，出队将引发下溢错误。队首元素不再保留在队列中。
3. Peek() or Front(): Returns the front element without removing it. It is useful to inspect the next item to be processed. Underflow applies if the queue is empty.
3. 查看队首 Peek() 或 Front()：返回队首元素而不移除它。可用于查看下一个待处理的元素。若队列为空则发生下溢。
4. isEmpty(): Returns true when the queue contains no elements. Always used before a dequeue to prevent underflow.
4. 判空 isEmpty()：当队列无元素时返回真。始终在出队前调用以防止下溢。
5. isFull(): Returns true when the queue cannot accept any more items. Relevant for bounded queues implemented with arrays.
5. 判满 isFull()：当队列无法再容纳更多元素时返回真。与数组实现的有界队列有关。
7. Implementing Queues | 队列的实现
Linear array implementation: A naive approach uses an array and two indices, front and rear. Initially, both are set to -1 (or 0, depending on convention). Enqueue increments rear and stores the item; dequeue increments front. The problem is that after several dequeue operations, the front of the queue moves forward, leaving wasted space at the array's beginning that cannot be reused. This leads to the "false overflow" situation where the queue appears full even though free space exists at the lower indices.
线性数组实现：一种简单的方法使用一个数组和两个索引：front（队首）和 rear（队尾）。初始时两者均设为 -1（或 0，取决于约定）。入队时 rear 递增并存储元素；出队时 front 递增。问题在于，经过多次出队操作后，队首前移，导致数组起始部分的空闲空间无法重用。这会造成“假溢出”，即低索引处明明有空间，队列却看似已满。
Circular queue implementation: To overcome false overflow, we treat the array as circular. When the rear index reaches the end of the array, it wraps around to the beginning if space is available. This is achieved using modular arithmetic. For an array of size n, the next rear position is (rear + 1) mod n, and similarly for front. A circular queue uses a fixed-length array very efficiently, but special care is needed to distinguish between the full and empty conditions.
循环队列实现：为克服假溢出，我们将数组视为循环的。当队尾索引到达数组末尾时，如果有空间，它会绕回到开头。这通过模运算实现。对于大小为 n 的数组，下一个队尾位置为 (rear + 1) mod n，队首类似。循环队列非常高效地利用固定长度数组，但需要特别注意区分满和空的状态。
Linked list implementation: A queue can be built with a singly linked list where two external pointers are kept: one to the head node (front) and one to the tail node (rear). Enqueue adds a new node at the tail and updates the rear pointer. Dequeue removes the head node and updates the front pointer. This avoids all overflow problems except system memory limits and does not require resizing logic. The trade-off is pointer overhead.
链表实现：可以使用单链表构建队列，并保持两个外部指针：一个指向头节点（队首），一个指向尾节点（队尾）。入队时在尾部添加新节点并更新 rear 指针。出队时移除头节点并更新 front 指针。这避免了除系统内存限制外的所有溢出问题，且不需要扩容逻辑。代价是指针开销。
8. Circular Queues in Depth | 深入理解循环队列
In a circular queue, the array is regarded as a circle. Valid index values range from 0 to (size - 1), and moving from the last index to the first is handled by modulo. A common WJEC exam technique is to reserve one empty slot to differentiate between full and empty. With this convention:
在循环队列中，数组被视为一个环。有效索引范围为 0 到 (size - 1)，从最后一个索引移动到第一个索引通过取模处理。WJEC 考试中常见的做法是预留一个空槽以区分满和空。遵循此约定：
- Empty condition: front == rear
- 空条件：front == rear
- Full condition: (rear + 1) mod size == front
- 满条件：(rear + 1) mod size == front
- Enqueue algorithm:
if (rear + 1) mod maxSize != front:
rear = (rear + 1) mod maxSize
queue[rear] = item
else: queue is full - 入队算法：
若 (rear + 1) mod maxSize != front：
rear = (rear + 1) mod maxSize
queue[rear] = 元素
否则：队列已满 - Dequeue algorithm:
if front != rear:
front = (front + 1) mod maxSize
return queue[front]
else: queue is empty - 出队算法：
若 front != rear：
front = (front + 1) mod maxSize
返回 queue[front]
否则：队列为空
Note that the front index initially points to the slot before the first element. When the queue is empty, both front and rear are set to the same value, often 0. Careful tracing of these indices is frequently examined. Students often lose marks by forgetting the modulo wrap-around or by misidentifying the empty/full condition.
注意，队首索引最初指向第一个元素之前的槽位。当队列为空时，front 和 rear 设为相同值，通常为 0。考试中经常要求仔细跟踪这些索引。学生常因忘记模回绕或混淆空/满条件而失分。
9. Priority Queues | 优先级队列
A priority queue is a variant where each element has an associated priority. Dequeue does not always remove the oldest element; instead, it removes the element with the highest priority. If multiple elements share the same priority, they are typically processed in FIFO order among themselves. The WJEC specification may require you to understand the concept and possibly implement a simple priority queue.
优先级队列是一种变体，其中每个元素都有一个关联的优先级。出队并不总是移除最早的元素，而是移除优先级最高的元素。如果多个元素优先级相同，通常在它们之间按 FIFO 顺序处理。WJEC 考纲可能要求你理解这一概念，并可能实现一个简单的优先级队列。
Simple implementations include an unordered list (enqueue is O(1), dequeue requires searching for the highest priority, O(n)) or an ordered list kept sorted by priority (enqueue is O(n) as insertion position must be found, dequeue is O(1)). A more advanced structure, like a binary heap, offers O(log n) for both operations, but for WJEC you mainly need to reason about the list-based approaches.
简单的实现包括无序列表（入队 O(1)，出队需搜索最高优先级，O(n)）或按优先级排序的有序列表（入队需寻找插入位置，O(n)；出队 O(1)）。更高级的结构如二叉堆，两种操作均为 O(log n)，但在 WJEC 中你主要需要分析基于列表的方法。
10. Applications of Queues | 队列的实际应用
Print spooling: Print jobs are placed in a queue. The printer processes them in the order they were received, ensuring fairness and avoiding conflicts. New jobs are enqueued, and the printer dequeues the next job when ready.
打印池：打印作业被放入队列。打印机按接收顺序处理它们，确保公平并避免冲突。新作业入队，打印机就绪时出队下一个作业。
Process scheduling: Operating systems often maintain a ready queue of processes waiting for the CPU. A simple round-robin scheduler uses a circular queue: the currently running process is preempted and placed at the rear, and the next process at the front is dispatched.
进程调度：操作系统常维护一个等待 CPU 的就绪队列。简单的轮转调度程序使用循环队列：当前运行进程被抢占后放入队尾，队首的下一个进程被派发。
Keyboard buffer: Key presses are stored in a queue as they are typed, even if the application is momentarily busy. This ensures no keystrokes are lost and they are handled in the order pressed. Without a queue, quick successive keystrokes might be processed out of order.
键盘缓冲区：按键被键入时存储在队列中，即使应用程序暂时忙碌。这确保不会丢失按键，并且按键顺序得到保持。若无队列，快速连续按键的处理可能乱序。
Breadth-first search (BFS): In graph traversal, a queue is used to process nodes level by level. The starting node is enqueued; nodes are dequeued one by one, and their unvisited neighbours are enqueued. This guarantees that nodes closer to the start are visited first.
广度优先搜索 (BFS)：在图遍历中，使用队列按层处理节点。起始节点入队；节点逐一出队，其未访问邻居入队。这样保证离起点更近的节点先被访问。
11. Comparison of Stacks and Queues | 栈与队列对比
| Feature | 特征 | Stack | 栈 | Queue | 队列 |
|---|---|---|
| Ordering principle | 排序原则 | LIFO (Last In, First Out) | 后进先出 | FIFO (First In, First Out) | 先进先出 |
| Primary insert operation | 主要插入操作 | Push (adds to top) | Push（添加到栈顶） | Enqueue (adds to rear) | Enqueue（添加到队尾） |
| Primary remove operation | 主要移除操作 | Pop (removes from top) | Pop（从栈顶移除） | Dequeue (removes from front) | Dequeue（从队首移除） |
| Access point(s) | 访问点 | Only the top | 仅栈顶 | Front (for removal), rear (for insertion) | 队首（移除），队尾（插入） |
| Typical applications | 典型应用 | Function call stack, undo, expression parsing | 函数调用栈、撤销、表达式解析 | Print spooler, task scheduling, BFS | 打印池、任务调度、广度优先搜索 |
| Array implementation pointers | 数组实现指针 | A single 'top' index | 一个 'top' 索引 | 'front' and 'rear' indices; often circular | 'front' 和 'rear' 索引；常为循环 |
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
Always check boundary conditions: Before any push or pop, verify whether the stack is full or empty, respectively. Missing these checks is a frequent mistake in written algorithms. For queues, check for empty before dequeue, and for full before enqueue—especially in circular queues where the condition is non-trivial.
始终检查边界条件：在任何 push 或 pop 之前，分别验证栈是否已满或为空。在书面算法中遗漏这些检查是常见错误。对于队列，出队前检查空，入队前检查满——尤其是循环队列中，其条件较复杂。
Correct index updates in circular queues: Using modulo arithmetic is mandatory when indices reach the array bounds. Forgetting to use (index + 1) mod size or updating front/rear incorrectly causes the queue to behave erratically. Practice tracing with small arrays (size 4 or 5) to build confidence.
循环队列中正确更新索引：当索引到达数组边界时，必须使用模运算。忘记使用 (index + 1) mod size 或错误更新 front/rear 会导致队列行为异常。用小型数组（大小为 4 或 5）进行跟踪练习以建立信心。
Draw state diagrams accurately: When asked to show a stack or queue after a sequence of operations, draw the array or linked nodes clearly, indicate the exact position of pointers (top, front, rear), and mark empty slots. An ambiguous diagram will lose marks.
准确绘制状态图：当要求展示一系列操作后的栈或队列时，清晰绘制数组或链表节点，标明指针（top, front, rear）的确切位置，并标记空槽位。模糊的图示会失分。
Understand the difference between ADT and implementation: The WJEC specification emphasises that a stack or queue is an abstract idea, not tied to a specific implementation. You might be asked to implement a stack using an array or a linked list, and you should be able to discuss the trade-offs (fixed size vs. dynamic, memory usage, speed).
理解 ADT 与实现的区别：WJEC 考纲强调栈或队列是一个抽象概念，不绑定到特定实现。可能会
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图