📚 Stacks and Queues for AQA A-Level Computer Science | 栈与队列考点精讲
In A-Level Computer Science, data structures form the backbone of efficient algorithm design. Among the most fundamental abstract data types (ADTs) are the stack and the queue. Understanding their behaviour, operations, implementation techniques, and real-world applications is essential for success in the AQA specification. This article provides a thorough revision of stacks and queues, covering everything from basic principles to exam-style tracing and coding.
在A-Level计算机科学中，数据结构是高效算法设计的支柱。栈和队列属于最基础的抽象数据类型(ADT)。理解它们的行为、基本操作、实现方法以及实际应用，对于在AQA考试中取得好成绩至关重要。本文对栈与队列进行系统精讲，从基本原理到考试常见的状态追踪和编程要点，一网打尽。
1. What Is an Abstract Data Type? | 什么是抽象数据类型？
An abstract data type (ADT) is a model that defines a data structure purely in terms of the operations it supports, without specifying how those operations are implemented. Key ADTs include stacks, queues, lists, and priority queues. The separation of interface from implementation allows programmers to use an ADT without worrying about the underlying code, an important principle in modular design.
抽象数据类型是一种模型，仅通过其支持的操作来定义数据结构，而不指定这些操作如何实现。常见的ADT有栈、队列、列表和优先队列等。这种接口与实现分离的方式使得程序员可以使用ADT而无需关心底层代码，是模块化设计的重要原则。
In the AQA exam, you are expected to recognise that both stacks and queues are ADTs, and you should be able to describe their operations, apply them in tracing exercises, and explain standard implementations using arrays or linked lists.
在AQA考试中，你需要认识到栈和队列都属于ADT，能够描述它们的操作，在追踪练习中应用，并解释使用数组或链表的典型实现方式。
2. Stack: LIFO Principle | 栈：后进先出原则
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of a stack of plates in a cafeteria: the last plate placed on top is the first one to be taken off. In computer science, a stack only allows access to the most recently added element, which sits at the ‘top’ of the structure.
栈是一种遵循后进先出(LIFO)原则的线性数据结构。想象自助餐厅的一摞盘子：最后放上去的盘子最先被取走。在计算机科学中，栈只允许访问最近添加的元素，该元素位于栈的“顶端”。
All insertions and deletions happen at one end, called the top. Elements deeper in the stack cannot be accessed until the ones above them are removed. This restricted access makes stacks simple but powerful.
所有的插入和删除操作都在同一端进行，这一端称为栈顶。栈中较深的元素只有在它上方的元素全部弹出后才能被访问。这种受限的访问方式使栈结构简单却功能强大。
3. Basic Operations on a Stack | 栈的基本操作
A stack ADT must support at least the following operations. Push(item) adds an item to the top of the stack. Pop() removes and returns the top item. Peek() or Top() returns the top item without removing it. isEmpty() checks whether the stack contains no elements. Optionally, isFull() may be required when the stack has a fixed capacity.
栈的ADT必须至少支持以下操作。Push(元素) 将一个元素添加到栈顶。Pop() 移除并返回栈顶元素。Peek() 或 Top() 返回栈顶元素但不移除。isEmpty() 检查栈是否为空。当栈有固定容量时，还可能要求有 isFull() 操作。
Exam questions often ask you to trace the state of a stack after a series of push and pop calls, noting the returned values and any errors such as stack underflow (popping from an empty stack) or stack overflow (pushing onto a full stack).
考试题常要求你追踪一系列push和pop调用后栈的状态，记录返回值以及可能发生的错误，如栈下溢（从空栈弹出）或栈上溢（向已满栈压入元素）。
4. Implementing a Stack with an Array | 用数组实现栈
A static stack can be implemented using a one-dimensional array and an integer variable top that stores the index of the current top element. Typically, top is initialised to -1 to indicate an empty stack. To push an item, increment top and store the item at stack[top], making sure top does not exceed the maximum index (MAX – 1). To pop, retrieve stack[top] and decrement top, ensuring top is not -1 before the operation.
静态栈可以使用一维数组和一个整型变量top来实现，top存储当前栈顶元素的索引。通常top初始化为-1表示空栈。压入元素时，先将top加1，再把元素存入stack[top]，并确保top不超过最大索引(MAX – 1)。弹出时，返回stack[top]后将top减1，确保操作前top不为-1。
if top < MAX-1: top ← top + 1; stack[top] ← item
This array-based implementation is straightforward and commonly examined. It is space-efficient, but the maximum size must be known in advance. The stack is full when top equals MAX – 1, and empty when top equals -1.
这种基于数组的实现方式简明易懂，是考试的重点。它空间效率高，但必须提前确定最大容量。当top等于MAX-1时栈满，top等于-1时栈空。
5. Implementing a Stack with a Linked List | 用链表实现栈
A dynamic stack can be created using a singly linked list, where the top of the stack corresponds to the head of the list. A push operation creates a new node and inserts it at the head of the list, making it the new top. A pop operation removes the head node and returns its data, with the second node becoming the new top. Here, overflow only occurs if the system runs out of memory, and underflow is detected by checking for an empty list.
动态栈可以使用单链表实现，其中栈顶对应于链表的头结点。push操作用于创建新结点并将其插入链表头部，使之成为新的栈顶。pop操作移除头结点并返回其数据，第二个结点随即成为新栈顶。此实现中，只在系统内存耗尽时才会发生溢出，下溢则通过检查链表是否为空来判断。
The linked-list implementation avoids the fixed-size limitation of arrays and does not need to shift elements. This trade-off uses slightly more memory per element to store pointers. In the AQA specification, you might be asked to describe or compare these two implementation strategies.
链表实现避免了数组的固定容量限制，也无需移动元素。代价是每个元素需要额外内存存储指针。在AQA大纲中，考生可能需要描述或比较这两种实现策略。
6. Queue: FIFO Principle | 队列：先进先出原则
A queue is another linear ADT, but it operates on a First In, First Out (FIFO) basis. It resembles a line of people waiting for service: the person who joins the queue first is the first to be served. Data enters at the rear of the queue and leaves from the front.
队列是另一种线性ADT，遵循先进先出(FIFO)原则。它就像排队等候的人群：最先进入队列的人最先得到服务。数据从队尾进入，从队首离开。
Just like a stack, a queue restricts access, but at both ends. The front element is the one that has been waiting the longest; the rear element is the most recently added. This behaviour makes queues ideal for modelling any first-come-first-served scenario.
和栈一样，队列也限制访问，但是是在两端分别限制。队首元素是等待最久的，队尾元素是最近加入的。这一行为使队列非常适合模拟一切先到先服务的场景。
7. Basic Operations on a Queue | 队列的基本操作
The essential queue operations are: Enqueue(item) adds an item to the rear of the queue. Dequeue() removes and returns the item from the front. isEmpty() checks whether the queue has no items. isFull() checks whether the queue has reached its capacity (for bounded queues). A Front() or Peek() operation might also be defined to look at the front item without removing it.
队列的基本操作有：Enqueue(元素) 将一个元素添加到队尾。Dequeue() 移除并返回队首元素。isEmpty() 检查队列是否为空。isFull() 检查队列是否达到容量上限（针对有界队列）。有时还会定义 Front() 或 Peek() 操作来查看队首元素但不移除。
When tracing queue operations, careful attention must be paid to the movement of front and rear pointers and to the conditions that distinguish an empty queue from a full queue. These conditions vary with implementation strategy, which is a common source of tricky exam questions.
在追踪队列操作时，必须仔细留意队首和队尾指针的移动，以及区分空队列和满队列的条件。这些条件随实现方式而变化，是考试中常见的难点。
8. Linear Queue Implementation Issues | 线性队列实现的问题
A straightforward array-based linear queue uses two indices: front and rear. Initially both are set to 0 or -1, and rear advances on each enqueue while front advances on each dequeue. The problem is that after a series of enqueue and dequeue operations, front moves forward, leaving empty spaces at the beginning of the array that cannot be reused. This is wasteful and can cause the queue to appear full even when empty spaces exist.
基于数组的简单线性队列使用两个索引：front和rear。初始均设为0或-1，每次enqueue时rear前移，每次dequeue时front前移。问题在于，经过一系列入队出队操作后，front会向前移动，导致数组开头遗留下无法重用的空位。这不仅浪费空间，还可能在明明有空位时让队列看似已满。
To overcome this limitation, a circular queue is used, where the array wraps around so that the position after the last index is the first index. This needs careful handling of the full and empty states.
为了克服这一局限，常使用循环队列，让数组形成环绕，使得最后一个索引的下一个位置就是第一个索引。这样需要仔细处理满和空两种状态的判断。
9. Circular Queue Implementation | 循环队列实现
A common AQA approach to a circular queue maintains three variables: the array, a front index, a rear index, and an integer count storing the current number of items. Front points to the first occupied position, rear points to the next free position, and count tracks how many items are present. The queue is empty when count equals 0, and full when count equals the array size.
AQA考试中常见的循环队列实现维护三个变量：数组、front索引、rear索引以及一个存储当前元素个数的整型计数count。front指向第一个有元素的位置，rear指向下一个空闲位置，count记录当前元素数量。当count等于0时队列为空，当count等于数组大小时队列为满。
Enqueue operation: if the queue is not full, store the item at queue[rear], then update rear to (rear + 1) MOD capacity and increment count. Dequeue operation: if the queue is not empty, retrieve item from queue[front], update front to (front + 1) MOD capacity and decrement count. This scheme avoids wasting a slot and simplifies full/empty detection.
入队操作：若队列未满，将元素存入queue[rear]，然后将rear更新为(rear + 1) MOD 容量，并将count加1。出队操作：若队列非空，从queue[front]取出元素，将front更新为(front + 1) MOD 容量，并将count减1。这种方案不会浪费额外的存储单元，并且简化了满/空状态的判断。
rear ← (rear + 1) MOD maxSize
Always initialise front and rear to 0 and count to 0. This is a robust base for exam tracing questions.
始终将front和rear初始化为0，count初始化为0。这是应对考试追踪题的可靠基础。
10. Priority Queues (Briefly) | 优先队列（简要）
A priority queue is an ADT where each element is assigned a priority, and the element with the highest priority is dequeued first, regardless of insertion order. If two elements have the same priority, they may obey FIFO ordering or some other rule. Priority queues are commonly implemented using a heap data structure, but at A-Level you only need to recognise the concept and perhaps compare it with ordinary queues in scenario-based questions.
优先队列是一种ADT，其中每个元素被赋予一个优先级，优先级最高的元素最先出队，而不考虑入队顺序。如果两个元素优先级相同，则可能遵循FIFO顺序或其他规则。优先队列通常使用堆数据结构来实现，但在A-Level阶段你只需了解概念，并可能在情境题中将其与普通队列进行比较。
Example: a hospital emergency room uses a priority queue to treat the most critical patients first, not simply the first to arrive. This illustrates how the ADT abstraction can model real-world scenarios beyond simple FIFO.
例如，医院急诊室使用优先队列来优先处理最危急的病人，而不仅仅是先到先治。这表明ADT抽象能够模拟超越简单FIFO的现实场景。
11. Applications of Stacks | 栈的应用
Stacks appear in numerous areas of computing. One of the most important is the call stack used by programming language runtimes. When a function is called, the current address and local variables are pushed onto the stack; when the function returns, the stack frame is popped, allowing execution to resume correctly. Recursion also relies entirely on the call stack.
栈在计算领域中有大量应用。最重要的之一是编程语言运行时使用的调用栈。调用函数时，当前地址和局部变量被压入栈中；函数返回时，其栈帧弹出，使得程序可以正确恢复执行。递归也完全依赖于调用栈。
Bracket matching in compilers and text editors is another classic use. An opening bracket is pushed onto a stack; when a closing bracket is read, it is checked against the top of the stack. If they match, the top is popped; otherwise, an error is reported. At the end, an empty stack indicates all brackets are correctly balanced.
编译器与文本编辑器中的括号匹配是另一个经典应用。遇到开括号时将其压入栈中；读到闭括号时，与栈顶元素比对。若匹配则弹出栈顶，否则报错。最终空栈意味着所有括号正确匹配。
Reverse Polish Notation (RPN), also called postfix notation, uses stacks for both conversion from infix expressions and evaluation. For evaluation, operands are pushed onto a stack; when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back. For example, the infix expression 2 + 3 × 4 becomes 2 3 4 × + in RPN. Evaluation steps:
逆波兰表示法（也称后缀表达式）同时使用栈来进行中缀转换和求值。求值时，操作数压入栈；遇到操作符时，弹出所需的操作数，执行运算，再将结果压回栈中。例如，中缀表达式 2 + 3 × 4 的逆波兰形式为 2 3 4 × +。求值过程为：
- Push 2, push 3, push 4. / 压入2，压入3，压入4。
- Read ‘×’: pop 4 and 3, compute 3 × 4 = 12, push 12. / 读到“×”：弹出4和3，计算3 × 4 = 12，压入12。
- Read ‘+’: pop 12 and 2, compute 2 + 12 = 14, push 14. / 读到“+”：弹出12和2，计算2 + 12 = 14，压入14。
- Result is 14. / 结果为14。
These applications are frequently examined, so practice tracing algorithms that involve stacks.
这些应用常被考查，因此要多练习涉及栈的算法追踪。
12. Applications of Queues | 队列的应用
Queues are used wherever a ‘first-come-first-served’ order is required. Operating systems use queues extensively: processes waiting for the CPU sit in a ready queue; print jobs are held in a printer spooler; keystrokes are buffered in a keyboard buffer so that they are processed in the order they arrived.
队列适用于任何需要“先到先服务”顺序的场景。操作系统大量使用队列：等待CPU的进程存放在就绪队列中；打印任务在打印缓冲池中排队；键盘输入则通过键盘缓冲区暂存，确保按键按到达顺序处理。
In algorithm design, queues are fundamental to breadth-first search (BFS) in graphs and trees. BFS explores nodes level by level, using a queue to keep track of nodes yet to be visited. This is another exam-relevant area, particularly for those studying algorithms and data structures at A-Level.
在算法设计中，队列是图和树的广度优先搜索（BFS）的基础。BFS按层次遍历节点，用队列来记录待访问的节点。这也是与考试相关的领域，尤其是对学习算法与数据结构的A-Level考生而言。
Simulations, such as modelling a supermarket checkout or a network router’s packet handling, also rely on queues to mimic real-world waiting lines. Understanding how to apply queues to these scenarios strengthens your ability to answer context-based exam questions.
模拟场景，例如模拟超市收银台或网络路由器的数据包处理，也依赖于队列来再现现实中的排队现象。理解如何将队列应用于这些场景，能够增强你回答情境化考题的能力。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导