📚 Mastering Stack and Queue Operations | 掌握堆栈与队列操作
Stacks and queues are fundamental linear data structures that every A-Level Computer Science student must understand thoroughly. In the Edexcel specification, the operations on these abstract data types (ADTs), their implementations using arrays and linked lists, and their real-world applications form a core part of the algorithms and programming paper. This guide explains every essential operation, common pitfalls, and typical exam scenarios to help you master the topic.
堆栈和队列是每个 A-Level 计算机科学学生必须彻底掌握的基本线性数据结构。在 Edexcel 考纲中，这些抽象数据类型（ADT）的操作、使用数组和链表的实现方式以及它们的实际应用构成了算法与编程试卷的核心内容。本指南将解释每一个关键操作、常见陷阱以及典型考试情景，帮助你精通该主题。
1. Introduction to Abstract Data Types (ADTs) | 抽象数据类型简介
An abstract data type defines a logical model for data structures by specifying what operations can be performed without revealing how they will be implemented. Stacks and queues are classic examples of ADTs because their behaviour is defined by rules such as LIFO and FIFO, independent of the underlying implementation.
抽象数据类型通过指定可以执行哪些操作来定义数据结构的逻辑模型，而不会透露这些操作将如何实现。堆栈和队列是典型 ADT 的例子，因为其行为由 LIFO 和 FIFO 等规则定义，与底层实现无关。
2. What is a Stack? | 什么是堆栈？
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means the most recently added element is the first one to be removed. You can visualise a stack like a pile of plates: you can only take the top plate or add a new plate on top.
堆栈是一种遵循后进先出（LIFO）原则的线性数据结构。这意味着最近添加的元素会最先被移除。你可以把堆栈想象成一摞盘子：你只能拿最上面的盘子，或者在顶部添加一个新盘子。
3. Core Stack Operations | 核心堆栈操作
The five fundamental stack operations are push, pop, peek (or top), isEmpty, and isFull. Understanding their preconditions and postconditions is critical for exam success. A typical Edexcel question may ask you to trace through a sequence of operations or write pseudocode for them.
五个基本堆栈操作是 push（压入）、pop（弹出）、peek（查看栈顶，或 top）、isEmpty（判空）和 isFull（判满）。理解它们的前置条件和后置条件对考试成功至关重要。典型的 Edexcel 题目可能会要求你跟踪一系列操作或为它们编写伪代码。
| Operation | English Description | 中文描述 |
|---|---|---|
| push(item) | Adds an item to the top of the stack, provided the stack is not full. | 将元素添加到栈顶（前提是堆栈未满）。 |
| pop() | Removes and returns the top item, if the stack is not empty. | 移除并返回栈顶元素（前提是堆栈非空）。 |
| peek() | Returns the top item without removing it. Returns an error if empty. | 返回栈顶元素但不移除。若堆栈为空则返回错误。 |
| isEmpty() | Returns true if the stack contains no items; false otherwise. | 若堆栈不含任何元素则返回 true，否则返回 false。 |
| isFull() | Returns true if the stack has reached its maximum capacity (used with static arrays). | 若堆栈已达到最大容量则返回 true（用于静态数组实现）。 |
The top of the stack is usually tracked by a pointer or index variable (often called top). In a zero-based array implementation, top = -1 indicates an empty stack.
栈顶通常由一个指针或索引变量（常称作 top）来跟踪。在基于零索引的数组实现中，top = -1 表示空栈。
4. Applications of Stacks | 堆栈的应用
Stacks are used extensively in computer systems. In the Edexcel syllabus, you need to be able to explain how stacks support procedure calls (call stack), recursion, undo operations in software, and bracket matching in compilers. The call stack stores return addresses and local variables, growing and shrinking as functions are called and return.
堆栈广泛用于计算机系统中。在 Edexcel 考纲中，你需要能够解释堆栈如何支持过程调用（调用栈）、递归、软件中的撤销操作以及编译器中的括号匹配。调用栈存储返回地址和局部变量，随着函数的调用和返回而增长和收缩。
Another classic application is evaluating reverse Polish notation (RPN) expressions. A stack effortlessly handles postfix arithmetic: operands are pushed, and operators pop the required number of operands and push the result.
另一个经典应用是计算逆波兰表示法（RPN）表达式。堆栈可以轻松处理后缀算术运算：操作数被压入，运算符弹出所需数量的操作数并将结果压回。
5. What is a Queue? | 什么是队列？
A queue is a linear data structure operating on a First In First Out (FIFO) basis. The first element added is the first to be removed, much like a line of people waiting for a bus. Items are added at the rear (tail) and removed from the front (head).
队列是一种基于先进先出（FIFO）原则的线性数据结构。最先添加的元素最先被移除，很像人们排队等公交车。元素在队尾（rear）加入，从队头（front）移除。
6. Core Queue Operations | 核心队列操作
The essential queue operations are enqueue, dequeue, peek (or front), isEmpty, and isFull. These mirror the stack operations but follow the FIFO discipline. Exams often test your ability to differentiate between enqueue and dequeue with clear pointer updates.
基本队列操作是 enqueue（入队）、dequeue（出队）、peek（或 front，查看队头）、isEmpty 和 isFull。它们与堆栈操作类似，但遵循 FIFO 规则。考试经常测试你能否区分入队和出队操作，并正确更新指针。
| Operation | English Description | 中文描述 |
|---|---|---|
| enqueue(item) | Adds an item to the rear of the queue if space is available. | 如果有空间，将元素添加到队列尾部。 |
| dequeue() | Removes and returns the item at the front of the queue, provided the queue is not empty. | 若队列非空，移除并返回队头元素。 |
| peek() | Returns the front item without removing it; error if empty. | 返回队头元素但不移除；若为空则报错。 |
| isEmpty() | Checks whether the queue contains no elements. | 检查队列是否不含任何元素。 |
| isFull() | Indicates if the queue cannot accept more items (relevant for static implementations). | 指出队列是否已无法接受更多元素（与静态实现相关）。 |
7. Types of Queues: Linear, Circular, and Priority | 队列类型：线性、循环和优先级
A linear queue can suffer from wasted space when items are dequeued from the front, as the front index moves forward. This is solved by a circular queue, where the rear and front pointers wrap around to the beginning of the array when they reach the end. The circular queue is a key Edexcel topic, and you must be able to compute the number of free slots and the positions of front and rear using modulo arithmetic.
线性队列在元素从前端出队时可能会浪费空间，因为前端索引向前移动了。解决办法是使用循环队列，其队头和队尾指针到达数组末尾时会绕回到开头。循环队列是 Edexcel 的重要主题，你必须能利用模运算计算空闲槽位数量以及队头和队尾的位置。
A priority queue assigns a priority value to each element; elements with higher priority are dequeued before those with lower priority, regardless of their arrival order. Priority queues are often implemented using a heap structure, but at A-Level you may be expected to understand the abstract behaviour.
优先级队列为每个元素分配一个优先级值；优先级较高的元素会先于优先级较低的元素出队，不论它们的到达顺序如何。优先级队列通常使用堆结构实现，但在 A-Level 阶段你只需理解其抽象行为。
Circular Queue Enqueue: rear → (rear + 1) mod size
循环队列入队：rear → (rear + 1) mod 容量
8. Implementing Stacks and Queues | 实现堆栈与队列
Stacks can be implemented using a static array or a dynamic linked list. The array implementation is straightforward but has a fixed capacity, requiring careful overflow checks. A linked list implementation removes the size limit but adds memory overhead for pointers. In Edexcel, you are expected to compare the advantages of static vs dynamic structures for these ADTs.
堆栈可以用静态数组或动态链表实现。数组实现简单直接，但容量固定，需要仔细检查溢出。链表实现消除了大小限制，但增加了指针的内存开销。在 Edexcel 中，你要能够比较这些 ADT 的静态与动态结构各自的优势。
Similarly, queues can be implemented with arrays (linear or circular) or linked lists. With a linked list queue, you maintain a front pointer to the head node and a rear pointer to the tail node. Enqueue involves adding to the tail; dequeue removes the head. This design avoids the empty-slot problem of linear arrays.
同样，队列可以用数组（线性或循环）或链表实现。使用链表队列时，你维护一个指向头节点的 front 指针和一个指向尾节点的 rear 指针。入队操作在尾部添加节点；出队操作移除头节点。这种设计避免了线性数组的空槽问题。
9. Common Errors and Overflow/Underflow | 常见错误与溢出/下溢
A stack overflow occurs when you attempt to push an item onto a full stack; an underflow error occurs when you try to pop from an empty stack. Similar errors occur for queues: enqueue on a full queue causes overflow, and dequeue on an empty queue causes underflow. Edexcel exam questions often present fragmented code and ask you to identify these logical errors. Always validate preconditions.
当你试图向已满的堆栈压入元素时，会发生堆栈溢出；当你试图从空堆栈弹出元素时，会发生下溢错误。队列也有类似错误：向满队列入队导致溢出，从空队列出队导致下溢。Edexcel 考试经常给出不完整的代码，让你找出这些逻辑错误。一定要验证前置条件。
For circular queues, confusing the condition for full vs empty is a classic mistake. A common strategy is to leave one slot unused so that front == (rear + 1) mod size indicates full, while front == rear indicates empty. Another method uses a separate count variable.
对于循环队列，混淆满与空的判断条件是一个经典错误。常用策略是保留一个空槽位，这样 front == (rear + 1) mod 容量 表示已满，而 front == rear 表示为空。另一种方法是使用额外的计数变量。
10. Exam Tips and Key Points | 考试技巧与要点
In Edexcel A-Level programming papers, you may be asked to trace an algorithm involving stack/queue operations, complete a truth table of pointer values, or write pseudocode for given scenarios. Always show the pointer updates step by step. Clearly indicate when underflow or overflow checks are required. Use descriptive variable names like stackTop, queueFront, queueRear.
在 Edexcel A-Level 编程试卷中，你可能会被要求跟踪涉及堆栈/队列操作的算法、补全指针值的真值表，或为给定情景编写伪代码。务必逐步展示指针的更新过程。明确指出何时需要下溢或溢出检查。使用描述性变量名，如 stackTop、queueFront、queueRear。
Remember the key differences: stack uses LIFO, ideal for reversing order; queue uses FIFO, ideal for maintaining order. Both are ADTs, so the operations remain the same regardless of whether an array or linked list is used underneath. Mastering these operations will also help you understand the call stack used in recursion, which is a frequent deeper-mark question.
记住关键区别：堆栈使用 LIFO，适合反转顺序；队列使用 FIFO，适合保持顺序。两者都是 ADT，因此无论底层使用数组还是链表，操作都保持一致。掌握这些操作也有助于你理解递归中使用的调用栈，这常常是高分题目。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply