📚 A-Level OCR Computer Science: Stacks and Queues – Key Points | A-Level OCR 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) that appear throughout the OCR A‑Level Computer Science syllabus. Understanding their behaviour, implementation, and applications is essential for both the written examinations and the practical programming project. This article provides a detailed revision of every key point you need to master.
栈和队列是贯穿 OCR A‑Level 计算机科学课程的基本抽象数据类型。理解它们的行为、实现方式和应用，对笔试和实践编程项目都至关重要。本文为你梳理了必须掌握的每一个考点。
1. Introduction to Stacks and Queues | 栈与队列简介
A stack is a Last-In-First-Out (LIFO) data structure: the last element added is the first one to be removed. You can think of a stack of plates – you can only take the top plate. A queue is a First-In-First-Out (FIFO) data structure: elements are removed in the same order they were added, just like a line of people waiting at a bus stop.
栈是一种后进先出（LIFO）的数据结构：最后添加的元素第一个被移除。你可以想象一叠盘子，只能拿走最上面的那个。队列是一种先进先出（FIFO）的数据结构：元素按照加入的顺序被移除，就像在公交站排队的人群。
Both are dynamic structures that can grow and shrink during program execution. They hold a sequence of items and restrict access to only one or two ends. The OCR specification requires you to be able to describe the purpose of stacks and queues, and to trace their state as operations are applied.
两者都是动态结构，在程序执行过程中可以增长和收缩。它们保存一系列元素，并限制只能从一端或两端进行访问。OCR 考纲要求你能够描述栈和队列的用途，并追踪执行操作时它们的状态变化。
2. Stack ADT and Core Operations | 栈抽象数据类型及核心操作
The stack ADT defines a set of operations independent of any implementation. The five standard operations are named slightly differently across textbooks, but the OCR specification typically uses: push(item) – adds an item to the top of the stack; pop() – removes and returns the item from the top; peek() or top() – returns the top item without removing it; isEmpty() – checks whether the stack contains any items; isFull() – checks whether the stack has reached its maximum capacity (relevant for array-based implementations).
栈的抽象数据类型定义了一组与具体实现无关的操作。五种标准操作在不同教材中命名略有差异，但 OCR 考纲通常使用：push(item) – 将一个元素添加到栈顶；pop() – 移除并返回栈顶元素；peek() 或 top() – 返回栈顶元素但不移除；isEmpty() – 检查栈是否为空；isFull() – 检查栈是否已达到最大容量（与基于数组的实现相关）。
When you push, the top pointer moves up; when you pop, the top pointer moves down. If you attempt to pop from an empty stack, this causes an underflow error. If you push onto a full stack (in a bounded implementation), an overflow error occurs. You must be able to apply these operations to a trace table in an exam question.
执行 push 时，栈顶指针向上移动；执行 pop 时，栈顶指针向下移动。如果试图从空栈中弹出元素，会引起下溢错误。如果向已满的栈（在有界实现中）压入元素，则发生上溢错误。你必须能在考试题目中将这些操作应用到跟踪表中。
3. Array-based Stack Implementation | 基于数组的栈实现
An array gives a fixed-size stack. We maintain an integer variable top (sometimes called stackPointer) that stores the index of the most recently added item. Initially, when the stack is empty, top is set to -1. In OCR pseudocode, this may be written as top = -1.
数组提供了一个固定大小的栈。我们维护一个整型变量 top（有时称为 stackPointer），它存储最近添加元素的索引。初始状态下栈为空时，top 被设为 -1。在 OCR 伪代码中，这可能写成 top = -1。
For a push operation, we first check if top == maxSize - 1. If true, output an overflow error. Otherwise, increment top by 1 and store the new item at stackArray[top]. For a pop, if top == -1, output an underflow error. Otherwise, return stackArray[top] and then decrement top. Peek simply returns stackArray[top] without changing top.
执行压入操作时，我们首先检查 top == maxSize - 1。如果为真，输出上溢错误。否则，将 top 增加 1，然后将新元素存储在 stackArray[top] 中。弹出操作时，如果 top == -1，输出下溢错误。否则，返回 stackArray[top]，然后将 top 减 1。Peek 仅返回 stackArray[top] 而不改变 top。
All these operations run in O(1) time. The space complexity is O(n) where n is the maximum size. This implementation is simple but suffers from the limitation of a fixed capacity unless we use a dynamic array that resizes when full.
所有这些操作的时间复杂度均为 O(1)。空间复杂度是 O(n)，其中 n 是最大容量。这种实现简单，但受限于固定容量，除非使用在满时能够调整大小的动态数组。
4. Linked List-based Stack Implementation | 基于链表的栈实现
A stack can be implemented using a singly linked list, where the head of the list represents the top of the stack. Each node contains a data field and a pointer (next) to the node below it. The variable top holds a reference to the first node (or null/NULL if the stack is empty).
栈可以用单向链表实现，链表的头代表栈顶。每个节点包含一个数据域和一个指向下方节点的指针 (next)。变量 top 持有对第一个节点的引用（如果栈为空，则为 null 或 NULL）。
To push, we create a new node with the given data, set its next pointer to the current top, and then update top to point to the new node. To pop, if top is null we raise an underflow error; otherwise, we save the data from the top node, move top to top.next, and return the data. Peeking simply returns top.data without altering the structure. The empty and full checks are straightforward: isEmpty returns true when top is null; the linked list implementation is never truly full as long as heap memory is available.
压入时，我们用给定数据创建一个新节点，将其 next 指针设置为当前的 top，然后更新 top 指向新节点。弹出时，如果 top 为 null 则引发下溢错误；否则，保存 top 节点的数据，将 top 移动到 top.next，然后返回数据。Peeking 仅返回 top.data 而不改变结构。空和满的检查很简单：当 top 为 null 时 isEmpty 返回 true；只要有可用的堆内存，链表实现就永远不会真正满。
All operations still run in O(1) time. The space used is exactly proportional to the number of elements. This implementation is more flexible than the array version and is the one often required in Algorithm Design and Programming questions.
所有操作仍然在 O(1) 时间内运行。所使用的空间与元素数量成正比。这种实现比数组版本更灵活，并且是算法设计与编程题中通常要求使用的版本。
5. Queue ADT and Core Operations | 队列抽象数据类型及核心操作
A queue ADT supports operations that act on two ends: the rear (or tail) for adding items, and the front (or head) for removing items. The standard operations are: enqueue(item) – adds an item to the rear; dequeue() – removes and returns the item from the front; peek() or front() – returns the front item without removing it; isEmpty(); isFull() (for bounded implementations).
队列 ADT 支持作用于两端的操作：尾部用于添加元素，头部用于移除元素。标准操作包括：enqueue(item) – 将一个元素添加到尾部；dequeue() – 从头部移除并返回元素；peek() 或 front() – 返回头部元素但不移除；isEmpty()；isFull()（用于有界实现）。
When you enqueue, the rear pointer advances; when you dequeue, the front pointer advances. In a linear queue, as items are added and removed, the queue gradually shuffles towards the end of the array, leading to unused space at the beginning. This problem is solved by the circular queue, which is heavily tested in OCR papers.
执行入队时，尾部指针向前移动；执行出队时，头部指针向前移动。在线性队列中，随着元素的添加和移除，队列逐渐向数组末尾移动，导致起始位置的空间未被使用。循环队列解决了这个问题，这在 OCR 试卷中是重点考查内容。
6. Array-based Queue Implementation (Linear) | 基于数组的线性队列实现
An array-based queue uses two index pointers: front points to the position holding the first element, and rear points to the position of the last element. Initially, for an empty queue, we commonly set front to 0 and rear to -1. When an item is enqueued, rear is incremented and the item is stored at that index. When an item is dequeued, the item at front is removed and front is incremented.
基于数组的队列使用两个索引指针：front 指向第一个元素，rear 指向最后一个元素。初始状态下空队列通常将 front 设为 0，rear 设为 -1。入队时，rear 增加，元素被存储在该索引处。出队时，移除 front 处的元素，然后 front 增加。
The problem arises when rear reaches the end of the array but the front has moved past position 0. For example, after several enqueue and dequeue operations, front may be 5 and rear 9 in an array of size 10. Even though positions 0 to 4 are empty, the queue thinks it is full because rear == maxSize – 1. This is known as linear queue overflow. The circular queue is the standard fix, and exam questions frequently ask for a comparison.
当 rear 到达数组末尾，而 front 已经移过了位置 0 时，问题就出现了。例如，经过多次入队和出队操作后，在一个大小为 10 的数组中，front 可能是 5，rear 是 9。虽然位置 0 到 4 是空的，但队列会认为它已满，因为 rear == maxSize – 1。这被称为线性队列溢出。循环队列是标准的解决方案，考试题经常要求进行比较。
7. Circular Queue Implementation | 循环队列实现
In a circular queue, the array is treated as circular: when an index reaches maxSize – 1, the next index wraps around to 0. We still maintain front and rear pointers, but now the queue is full when the next position after rear equals front (assuming one empty slot is reserved to distinguish between full and empty states). The condition for fullness in OCR pseudocode is often (rear + 1) MOD maxSize == front.
在循环队列中，数组被视为环形的：当索引达到 maxSize – 1 时，下一个索引会回绕到 0。我们仍然维护 front 和 rear 指针，但现在当 rear 的下一个位置等于 front 时队列为满（假设保留一个空槽以区分满和空状态）。在 OCR 伪代码中，满的条件通常为 (rear + 1) MOD maxSize == front。
To enqueue, if the queue is not full, we move rear forward using rear = (rear + 1) MOD maxSize and store the item. To dequeue, if the queue is not empty, we save the item at front, then advance front with front = (front + 1) MOD maxSize. The empty condition is simply front == rear (when the queue is first initialised, both are set to 0, for example).
入队时，如果队列未满，我们使用 rear = (rear + 1) MOD maxSize 将 rear 向前移动，然后存储元素。出队时，如果队列非空，我们保存 front 处的元素，然后用 front = (front + 1) MOD maxSize 将 front 向前移动。空的条件就是 front == rear（例如，当队列刚刚初始化时，两者都设置为 0）。
Circular queues make efficient use of array space and are common in buffering applications such as keyboard input buffers or print queues. In exams, you may be asked to draw or trace a circular queue through several operations, so practise with small arrays (e.g., size 5).
循环队列能高效利用数组空间，在键盘输入缓冲区或打印队列等缓冲应用中很常见。考试中可能会要求你通过几次操作绘制或追踪循环队列，所以请用小型数组（如大小为 5）进行练习。
8. Linked List-based Queue Implementation | 基于链表的队列实现
A queue can also be implemented using a singly linked list with two external pointers: front (pointing to the first node) and rear (pointing to the last node). An empty queue has both front and rear set to null (or NULL).
队列也可以用单向链表实现，并维护两个外部指针：front（指向第一个节点）和 rear（指向最后一个节点）。空队列的 front 和 rear 都设为 null（或 NULL）。
To enqueue, we create a new node. If the queue is empty, we set both front and rear to point to the new node. Otherwise, we link the current rear node’s next pointer to the new node, and then update rear to be the new node. To dequeue, we check if the queue is empty. If not, we retrieve the data from the front node, update front to front.next, and if front becomes null we also set rear to null (since the queue is now empty). All operations run in O(1).
入队时，我们创建一个新节点。如果队列为空，则将 front 和 rear 都指向新节点。否则，将当前 rear 节点的 next 指针链接到新节点，然后更新 rear 为新节点。出队时，检查队列是否为空。若非空，从 front 节点中获取数据，将 front 更新为 front.next，如果 front 变为 null 则同时将 rear 也设为 null（因为现在队列为空）。所有操作均在 O(1) 时间内完成。
This implementation never suffers from overflow (except for running out of heap memory) and space grows dynamically. The OCR specification expects you to be able to write and trace linked-list implementations for both stacks and queues.
这种实现永远不会发生溢出（除非堆内存耗尽），并且空间动态增长。OCR 考纲要求你能够编写并追踪基于链表的栈和队列的实现。
9. Priority Queue Concept | 优先队列概念
A priority queue is an extension of a normal queue where each element has an associated priority. Elements with higher priority are dequeued before elements with lower priority, regardless of their arrival order. If two elements have the same priority, they are typically served in FIFO order.
优先队列是对普通队列的扩展，其中每个元素都有一个关联的优先级。优先级较高的元素比优先级较低的元素先出队，无论它们到达的顺序如何。如果两个元素优先级相同，通常按照 FIFO 顺序服务。
Priority queues can be implemented using a sorted array/list, an unsorted array/list, or a heap. Heaps give the most efficient implementation, providing O(log n) for insertion and removal of the highest-priority element. While the full heap data structure is beyond the AS-level, A-Level students need to recognise priority queues and understand their use in scheduling algorithms and event-driven simulations.
优先队列可以使用有序数组/列表、无序数组/列表或堆来实现。堆提供了最高效的实现，插入和移除最高优先级元素的时间复杂度为 O(log n)。虽然完整的堆数据结构超出了 AS 阶段的范围，但 A-Level 学生需要认识优先队列，并理解它们在调度算法和事件驱动仿真中的用途。
10. Applications of Stacks | 栈的应用
Stacks are used extensively in computing. Key applications that appear in OCR exams include: 1) Recursion – the call stack stores return addresses, parameters, and local variables for each active subroutine call. 2) Expression evaluation – converting infix expressions to postfix (Reverse Polish Notation) and evaluating postfix expressions using a stack. 3) Backtracking algorithms – solving mazes, the N‑Queens problem, or depth-first search. 4) Undo mechanisms in text editors and graphics software.
栈在计算领域有着广泛的应用。OCR 考试中出现的核心应用包括：1) 递归——调用栈为每个活动的子程序调用存储返回地址、参数和局部变量。2) 表达式求值——将中缀表达式转换为后缀表达式（逆波兰表示法）并使用栈对后缀表达式求值。3) 回溯算法——解决迷宫、N 皇后问题或深度优先搜索。4) 文本编辑器和图形软件中的撤销操作。
For the exam, practise tracing the conversion of an infix expression like A + B * (C - D) to postfix A B C D - * + using the shunting-yard algorithm with a stack. Then evaluate a postfix expression by pushing operands until an operator is encountered, popping the required operands, and pushing the result.
在备考时，请练习使用带有栈的调度场算法，追踪将中缀表达式 A + B * (C - D) 转换为后缀表达式 A B C D - * + 的过程。然后通过压入操作数直到遇到运算符、弹出所需的操作数并将结果压回栈中，来对后缀表达式求值。
11. Applications of Queues | 队列的应用
Queues are the natural choice wherever items must be processed in order: 1) Buffers – keyboards, network packets, and printer spooling all use queues to hold data temporarily. 2) CPU scheduling – jobs waiting for the CPU are held in a ready queue (often managed as a priority queue). 3) Breadth-first search – a queue stores nodes to be explored next in graph traversal. 4) Simulations – modelling real-world waiting lines, such as customers at a bank or supermarket.
对于任何必须按顺序处理的项目，队列都是自然的选择：1) 缓冲区——键盘、网络数据包和打印机假脱机都使用队列来临时存储数据。2) CPU 调度——等待 CPU 的作业被保存在就绪队列中（通常作为优先队列管理）。3) 广度优先搜索——在图的遍历中，队列存储下一步要探索的节点。4) 仿真——对银行或超市中的顾客排队等现实等待队列进行建模。
When answering exam questions, be ready to identify why a queue (linear vs circular vs priority) is the appropriate data structure for a given scenario, and suggest simple modifications, such as using a circular queue to avoid buffer overflow in a keyboard input routine.
在回答考试题目时，要准备好说明为什么某种队列（线性、循环或优先队列）适合给定的场景，并提出简单的修改建议，例如使用循环队列以避免键盘输入程序中的缓冲区溢出。
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
Many marks are lost through pointer mismanagement and ambiguous answers. Always: clearly state whether you are dealing with an array or linked-list implementation; label front/rear/top pointers on diagrams; check fullness before enqueue/push and emptiness before dequeue/pop; when describing a circular queue, show the modulo arithmetic explicitly.
许多分数因指针管理混乱和含糊的回答而丢失。一定要：清楚说明你处理的是数组还是链表实现；在图上标记 front/rear/top 指针；入队/压入前检查是否已满，出队/弹出前检查是否为空；在描述循环队列时，明确展示模运算。
A classic pitfall is confusing the top pointer’s initial value (-1 vs 0) and the conditions for empty and full. Trace table questions require you to record the state after each operation very carefully. Another is forgetting to handle the case when the queue becomes empty after a dequeue and failing to reset rear in a linked-list queue. Practise writing pseudocode from memory and explain the computational complexity of each operation.
一个常见的陷阱是搞混 top 指针的初始值（-1 还是 0）以及空和满的条件。跟踪表题目要求你非常仔细地记录每次操作后的状态。另一个常见错误是忘记了在出队后队列变空的情况，没能在链表队列中重置 rear。请练习凭记忆写出伪代码，并解释每个操作的计算复杂度。
Finally, do not neglect the big picture: OCR questions often ask you to compare ADTs (e.g., “Explain why a stack is more appropriate than a queue for backtracking”) or to analyse the suitability of different implementations. Be prepared to discuss trade-offs such as speed vs memory overhead, and static vs dynamic allocation.
最后，不要忽视全局：OCR 题目经常要求你比较 ADT（例如，“解释为什么栈比队列更适合回溯”），或分析不同实现方式的适用性。准备好讨论速度与内存开销、静态与动态分配等权衡问题。
Published by TutorHao | A-Level OCR 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