📚 A-Level CCEA Computer Science: Stacks and Queues — Key Concepts and Exam Tips | A-Level CCEA 计算机科学：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) that appear frequently in A-Level CCEA Computer Science exams. They govern how data is organised and accessed, forming the backbone of many algorithms and system processes. This article breaks down the core principles, operations, implementations and typical exam scenarios, equipping you with the knowledge to tackle both theory questions and pseudocode tracing with confidence.
栈和队列是A-Level CCEA计算机科学考试中频繁出现的基础抽象数据类型（ADT）。它们决定了数据的组织与访问方式，构成了众多算法和系统流程的骨架。本文深入剖析核心原理、操作、实现方式及典型考题情景，帮助你自信应对理论问答和伪代码追踪题。
1. Introduction to Stacks and Queues | 栈与队列简介
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) rule: the last element added is the first one to be removed. Think of a stack of plates — you can only take the top plate off. A queue, on the other hand, obeys First-In-First-Out (FIFO): the first element added is the first to leave, just like a line of people waiting for a bus.
栈是一种线性数据结构，遵循后进先出（LIFO）规则：最后加入的元素最先被移除。想象一摞盘子——你只能取走最顶上的那个。队列则遵循先进先出（FIFO）：最早加入的元素最先离开，就像排队等公交的队伍一样。
Both ADTs restrict where insertions and deletions may occur. This restriction gives them predictable behaviour, making them suitable for problems where the order of processing is critical. In the CCEA specification, you are expected to define these ADTs, describe their operations, implement them using arrays or linked lists, and evaluate their use in real-world contexts.
这两种ADT都限制了插入和删除发生的位置。这种限制赋予了它们可预测的行为，使其特别适用于处理顺序至关重要的场景。在CCEA考纲中，你需要定义这些ADT，描述其操作，使用数组或链表实现它们，并评估它们在现实环境中的应用。
2. The Stack Data Structure (LIFO) | 栈数据结构（后进先出）
A stack is characterised by a single access point known as the top. All insertions (pushes) and deletions (pops) happen at the top. This means the order in which items are removed is the exact reverse of the order they were added. Stacks are naturally recursive in nature: the structure itself implies that the most recent context is processed first.
栈的特征是只有一个称为栈顶的访问点。所有插入（push）和删除（pop）操作都发生在栈顶。这意味着元素被移除的顺序恰好与它们被添加的顺序相反。栈天生具有递归性质：结构本身暗示着最近期的上下文最先被处理。
The stack pointer (or top index) keeps track of the current position. When the stack is empty, the top pointer is typically set to -1 (in an array-based implementation). As items are pushed, the pointer increments; as they are popped, it decrements. The LIFO behaviour makes stacks invaluable for managing nested structures, such as parentheses matching, expression evaluation, and function call management.
栈指针（或栈顶索引）跟踪当前位置。当栈为空时，栈顶指针通常设为 -1（在基于数组的实现中）。随着元素压入，指针递增；弹出时，指针递减。LIFO行为使栈在管理嵌套结构（如括号匹配、表达式求值和函数调用管理）方面极有价值。
3. Stack Operations: Push, Pop, Peek/Top | 栈操作：压入、弹出、查看
The core stack operations are push (add an item to the top), pop (remove and return the top item), and peek (or top — return the top item without removing it). Auxiliary operations include isEmpty and isFull, which are essential for avoiding underflow (popping from an empty stack) or overflow (pushing onto a full stack). In CCEA pseudocode, you must be able to write these operations clearly and trace their effect on the stack contents and pointer.
栈的核心操作包括push（将元素添加到栈顶）、pop（移除并返回栈顶元素）和peek（或top——返回栈顶元素但不移除）。辅助操作包括isEmpty和isFull，它们对于避免下溢（从空栈弹出）或上溢（向满栈压入）至关重要。在CCEA伪代码中，你必须能够清晰地编写这些操作，并追踪它们对栈内容和指针的影响。
| Operation | Description | Pointer Change |
|---|---|---|
| push(item) | Adds item to the top | top ← top + 1 |
| pop() | Removes and returns top item | top ← top – 1 |
| peek() | Returns top item without removal | No change |
| isEmpty() | Returns TRUE if top = -1 | No change |
| isFull() | Returns TRUE if top = maxSize – 1 | No change |
注意：在基于数组的栈中，top 初始化为 -1；压入前检查 isFull，弹出前检查 isEmpty。下溢错误常出现在错误处理递归边界时，而上溢则在固定大小数组中没有检查空间导致数据覆盖。考试中常要求你手写模拟栈操作的表格，展示每一步后数组内容和 top 值。
4. Implementing Stacks: Array vs Linked List | 栈的实现：数组与链表
Stacks can be implemented using a static array or a dynamic linked list. In an array-based stack, a fixed block of memory is allocated; the top pointer moves within this block. The advantage is simplicity and direct indexing, but the maximum size must be known in advance. A linked-list implementation uses nodes that point to the next element; the top of the stack corresponds to the head of the list. This allows the stack to grow dynamically, avoiding overflow until system memory is exhausted, but it incurs extra memory overhead for pointers.
栈可以用静态数组或动态链表实现。在基于数组的栈中，分配固定大小的内存块，栈顶指针在该块内移动。优点是简单且可直接索引，但必须预先知道最大容量。链式实现使用指向下一元素的节点，栈顶对应链表的头节点。这使得栈可以动态增长，在系统内存耗尽前避免了上溢，但会因存储指针产生额外内存开销。
CCEA examiners often ask you to compare these two implementations. Array stacks are faster for push/pop because no dynamic memory allocation is needed at each step, but they waste space if the stack rarely reaches full capacity. Linked lists use exactly the required memory, yet node creation and pointer manipulation cost time. For many practical scenarios (like a web browser’s back button history), a linked-list stack provides the needed flexibility.
CCEA考官常要求比较这两种实现。数组栈的压入/弹出更快，因为每一步无需动态分配内存，但如果栈很少达到满容量，会浪费空间。链表精确使用所需内存，但节点创建和指针操作耗时。在许多实际场景中（如网络浏览器的后退历史），链表栈提供了所需的灵活性。
5. The Queue Data Structure (FIFO) | 队列数据结构（先进先出）
A queue has two open ends: the rear (where items are inserted) and the front (where items are removed). This FIFO discipline ensures fairness — the element that has waited the longest is served first. Unlike stacks, queues require two pointers (front and rear) to manage both ends. The front pointer indicates the next item to be dequeued, while the rear pointer indicates where the next enqueued item will be placed.
队列有两个开口端：队尾（元素插入端）和队首（元素移除端）。这种FIFO规则确保了公平性——等待时间最长的元素最先得到服务。与栈不同，队列需要两个指针（front 和 rear）来管理两端。front 指针指示下一个要出队的元素，rear 指针指示下一个入队元素的放置位置。
Queues are everywhere in computing: print spoolers, keyboard buffers, CPU scheduling, and breadth-first search algorithms all rely on the FIFO principle. In CCEA, you must be able to distinguish between a linear queue and a circular queue, and explain how a circular queue overcomes the problem of wasted space.
队列在计算中无处不在：打印后台处理、键盘缓冲区、CPU调度和广度优先搜索算法都依赖FIFO原则。在CCEA中，你必须能够区分线性队列和循环队列，并解释循环队列如何克服空间浪费问题。
6. Queue Operations: Enqueue, Dequeue, Front/Rear | 队列操作：入队、出队、队首队尾
The primary queue operations are enqueue(item) — add an element to the rear — and dequeue() — remove and return the element at the front. As with stacks, auxiliary functions isEmpty() and isFull() prevent underflow and overflow. In a linear array-based queue, both front and rear pointers start at 0 (or -1 depending on convention) and move only forward; once the rear reaches the end of the array, no more items can be added even if space exists at the front. This is known as the “drifting” problem.
队列的主要操作是enqueue(item)（将元素添加到队尾）和dequeue()（移除并返回队首元素）。与栈类似，辅助函数isEmpty()和isFull()用于防止下溢和上溢。在基于数组的线性队列中，front 和 rear 指针都始于 0（或根据惯例为 -1）并只向前移动；一旦 rear 到达数组末尾，即使队首存在空位也无法再添加元素。这被称为“漂移”问题。
| Operation | Description | Pointer Update |
|---|---|---|
| enqueue(item) | Add item at rear | rear ← rear + 1; queue[rear] = item |
| dequeue() | Remove item from front | item ← queue[front]; front ← front + 1 |
| isEmpty() | True if front > rear | No change |
| isFull() | True if rear = maxSize – 1 | No change |
考试中常要求你根据给定序列画出队列的 front 和 rear 指针移动情况。务必注意：出队的元素只是逻辑删除，数组中的值仍然存在，但已不在队列范围内。
7. Implementing Queues: Linear and Circular | 队列的实现：线性与循环队列
A circular queue solves the drifting problem by treating the array as if it wraps around. The rear pointer can loop back to the beginning of the array when it reaches the end, provided there are free slots. The key invariant is: the queue is full when (rear + 1) % size == front, leaving one empty cell to distinguish between full and empty states. Otherwise, when front == rear, the queue is empty.
循环队列通过将数组视为环形来解决漂移问题。当 rear 指针到达数组末尾可以绕回到开头，前提是有空闲槽位。关键不变量是：当 (rear + 1) % size == front 时队列已满，预留一个空单元以区分满和空的状态。否则，当 front == rear 时队列为空。
Implementing a circular queue requires careful modular arithmetic to update pointers. For enqueue: rear = (rear + 1) % size; for dequeue: front = (front + 1) % size. The CCEA specification expects you to trace a circular queue with diagrams, showing the positions of front, rear, and the logical queue contents. This is a favourite exam topic because it tests understanding of abstract pointer manipulation.
实现循环队列需要仔细使用模运算更新指针。enqueue 时：rear = (rear + 1) % size；dequeue 时：front = (front + 1) % size。CCEA 考纲期望你通过图表追踪循环队列，显示 front、rear 的位置以及逻辑队列内容。这是常考的题型，因为它考查对抽象指针操作的理解。
Circular queue full condition: (rear + 1) mod maxSize = front
循环队列满条件：(rear + 1) mod maxSize = front
注意在考试伪代码中，mod 就是取余运算符，与数学表示一致。
8. Priority Queues and Deques | 优先队列与双端队列
A priority queue is an extension where each element has an associated priority, and the dequeue operation removes the element with the highest priority (not necessarily the one that arrived first). If two elements share the same priority, FIFO order is often used as a tiebreaker. Priority queues are commonly implemented using heaps for efficiency, but at A-Level you may simply need to describe the abstract behaviour and trace operations where priority is an integer field.
优先队列是一种扩展，其中每个元素关联一个优先级，出队操作移除优先级最高的元素（不一定是最早到达的）。如果两个元素优先级相同，通常以 FIFO 顺序作为平局规则。优先队列通常使用堆来实现以获得高效率，但在 A-Level 阶段你可能只需描述抽象行为，并追踪优先级为整数字段的操作。
A double-ended queue (deque, pronounced “deck”) allows insertion and deletion at both ends. This supports both LIFO and FIFO behaviours depending on which end is used. Deques can be implemented with an array or a doubly linked list. While deques are not a heavy CCEA focus, they may appear in questions about flexible data structures or when a problem requires both forward and backward scanning.
双端队列（deque，发音为“deck”）允许在两端进行插入和删除。这支持根据使用端实现 LIFO 和 FIFO 行为。双端队列可以用数组或双向链表实现。虽然双端队列不是 CCEA 的重点，但当问题需要向前和向后扫描时，它们可能在灵活数据结构的题目中出现。
9. Applications of Stacks | 栈的应用
Stacks are used in parsing and evaluating expressions (infix to postfix conversion using the shunting-yard algorithm), backtracking algorithms (e.g., depth-first search, solving mazes), undo/redo mechanisms in editors, and syntax checking (balancing brackets). The program call stack stores return addresses and local variables for function calls, naturally following LIFO — the most recently called function must finish before the caller continues.
栈用于解析和求值表达式（使用调度场算法将中缀转后缀）、回溯算法（如深度优先搜索、迷宫求解）、编辑器中的撤销/重做机制，以及语法检查（括号匹配）。程序调用栈存储函数调用的返回地址和局部变量，自然遵循 LIFO——最近调用的函数必须在调用者继续前完成。
CCEA questions often ask you to show how a stack can be used to reverse a string, check for balanced parentheses, or simulate a recursive process iteratively. You may be given a series of inputs and asked to draw the stack state after each operation. Practice tracing stacks with clear diagrams; label the top pointer and indicate the order of elements.
CCEA 试题常要求你展示如何使用栈反转字符串、检查括号平衡，或者模拟递归过程的迭代实现。可能会给你一系列输入，并要求画出每次操作后的栈状态。多练习用清晰图表追踪栈，标注栈顶指针并指示元素顺序。
10. Applications of Queues | 队列的应用
Queues model scenarios where serving order must be preserved: print jobs sent to a shared printer, CPU process scheduling (Round Robin uses a ready queue), buffering keyboard input, handling web server requests, and performing breadth-first traversal of graphs/trees. The fairness of FIFO is crucial in these systems to prevent starvation.
队列模拟必须维持服务顺序的场景：发送到共享打印机的打印任务、CPU 进程调度（轮询调度使用就绪队列）、键盘输入缓冲、处理网络服务器请求，以及对图/树执行广度优先遍历。FIFO 的公平性在这些系统中对防止饥饿至关重要。
When discussing applications, link the queue property (FIFO) to the requirement. For example, in a breadth-first search, nodes are explored in the order they are discovered, which naturally matches the behaviour of a queue. Examiners like to see you apply conceptual knowledge to a practical context, so prepare one or two detailed examples.
讨论应用时，要将队列特性（FIFO）与需求联系起来。例如，在广度优先搜索中，节点是按发现的顺序探索的，这自然匹配队列的行为。考官喜欢看到你将概念知识应用于实际场景，所以准备一两个详细例子。
11. Stacks and Recursion / Call Stack | 栈与递归 / 调用栈
Every time a function is called, a stack frame (containing return address, parameters, and local variables) is pushed onto the call stack. When the function returns, the frame is popped and execution resumes from the stored return address. This is why infinite recursion leads to a stack overflow error — the call stack runs out of space. Understanding the call stack helps debug recursion and also helps explain why iterative solutions can sometimes be more memory-efficient than recursive ones.
每次调用函数，一个栈帧（包含返回地址、参数和局部变量）被压入调用栈。当函数返回时，该帧被弹出，并从存储的返回地址继续执行。这就是无限递归导致栈溢出错误的原因——调用栈空间耗尽。理解调用栈有助于调试递归，也有助于解释为何迭代解有时比递归解更节省内存。
In CCEA, you might be asked to trace a recursive function and show the state of the call stack at a particular point. Represent each frame clearly with parameter values and a return marker. An iterative stack can mimic recursion, which is a common technique for converting recursive algorithms to avoid stack overflow in extreme cases.
在 CCEA 中，你可能需要追踪一个递归函数并显示特定时刻调用栈的状态。清晰地表示每一帧，包括参数值和返回标记。迭代栈可以模拟递归，这是在极端情况下为避免栈溢出而转换递归算法的常用技术。
12. Exam Tips and Common Pitfalls | 考试技巧与常见错误
Pointer confusion: Students often mix up the value of the top pointer and the data stored at that index. Remember, top is an index (or pointer), not the value itself. Empty vs full: In circular queues, always check the condition (rear+1) % size == front for full, and front == rear for empty; the reserved slot is a classic trick. Off-by-one errors: When drawing arrays, ensure you update pointers before storing data (for stacks: top++ then store; for queues: rear++ then store). Underflow/overflow: Always explicitly check isEmpty before pop/dequeue and isFull before push/enqueue in pseudocode answers — marks are awarded for defensive programming.
指针混淆：学生常将栈顶指针的值与该索引位置存储的数据搞混。记住，top 是一个索引（或指针），而非值本身。空与满判断：在循环队列中，始终检查条件 (rear+1) % size == front 判满，front == rear 判空；预留一个空位是经典考点。差一错误：绘制数组时，确保先更新指针再存储数据（栈：top++ 然后赋值；队列：rear++ 然后赋值）。下溢/上溢：在伪代码答案中，务必在 pop/dequeue 前检查 isEmpty，在 push/enqueue 前检查 isFull——防御性编程可得分。
Also, when comparing implementations, don’t just list advantages — relate them to the specific constraints of the problem (memory, speed, flexibility). Use the correct CCEA pseudocode style: indentation, capitalised keywords like IF…THEN…ENDIF, and the assignment arrow ← . Finally, practice tracing unfamiliar variations: e.g., a stack that stores only unique items, or a priority queue that uses alphabetical order as secondary key.
此外，比较实现方式时，不要只列出优点——要将其与问题的具体约束（内存、速度、灵活性）联系起来。使用正确的 CCEA 伪代码风格：缩进、大写关键字如 IF…THEN…ENDIF，以及赋值箭头 ← 。最后，练习追踪不常见的变体：例如，只存储唯一项的栈，或以字母顺序作为辅助键的优先队列。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导