Stack and Queue Operations for A-Level Programming | A-Level 编程中的栈和队列操作

📚 Stack and Queue Operations for A-Level Programming | A-Level 编程中的栈和队列操作

Understanding how to manipulate data using abstract data types (ADTs) is a core part of the Edexcel A-Level programming syllabus. Stacks and queues provide ordered, linear storage, but with very different access rules. This article explains every operation you need to know, from push and pop to enqueue and dequeue, along with real-world applications and implementation details.

理解如何使用抽象数据类型 (ADT) 处理数据是 Edexcel A-Level 编程课程的核心内容。栈和队列都提供有序的线性存储，但访问规则截然不同。本文详解从 push、pop 到 enqueue、dequeue 的每一项操作，结合真实应用场景与实现细节，助你全面掌握考点。

1. The Concept of Abstract Data Types (ADTs) | 抽象数据类型的概念

An ADT is a model for a data structure that defines the operations that can be performed without specifying how they are implemented. Stacks and queues are classic ADTs. For the A-Level exam, you need to describe them by their behavior, not by the underlying code.

抽象数据类型是一种数据结构模型，它定义了可以执行哪些操作，而不规定如何实现。栈和队列就是典型的 ADT。在 A-Level 考试中，你需要根据它们的行为进行描述，而不是依据底层代码。

For example, a Stack ADT must provide push, pop, and peek, while a Queue ADT must provide enqueue, dequeue, and possibly isEmpty. The underlying implementation could be an array or a linked list, but the interface stays the same.

例如，栈 ADT 必须提供 push、pop 和 peek，而队列 ADT 必须提供 enqueue、dequeue，可能还有 isEmpty。底层实现可以是数组或链表，但接口保持不变。

2. Stack ADT: Last In, First Out | 栈 ADT：后进先出

A stack follows the Last In, First Out (LIFO) principle. The last element inserted is the first one to be removed. Imagine a stack of plates: you can only take the top plate. In programming, a stack is used for function call management, undo operations, and expression evaluation.

栈遵循后进先出 (LIFO) 原则。最后插入的元素最先被移除。想象一摞盘子：你只能拿起最上面的盘子。在编程中，栈用于函数调用管理、撤销操作和表达式求值。

The essential operations are push(item) to add an item to the top, pop() to remove and return the top item, peek() or top() to view the top item without removing it, and isEmpty() to check whether the stack is empty.

基本操作包括 push(item) 将元素添加到栈顶，pop() 移除并返回栈顶元素，peek() 或 top() 查看栈顶元素但不移除，以及 isEmpty() 检查栈是否为空。

3. Stack Operations in Detail | 栈操作详解

When push(5) is called on an empty stack, 5 becomes the only element. A subsequent push(8) places 8 above 5. Now peek() returns 8. Calling pop() removes 8, and the stack shrinks, leaving 5 as the top. A second pop() retrieves 5; after that, the stack is empty and any further pop() would cause an underflow error unless handled.

当对空栈调用 push(5) 时，5 成为唯一的元素。紧接着 push(8) 将 8 置于 5 之上。现在 peek() 返回 8。调用 pop() 移除 8，栈缩小，栈顶变为 5。再次 pop() 取出 5；之后栈为空，若再次 pop() 会导致下溢错误，除非进行处理。

Push: O(1) time complexity, top pointer increments.
Pop: O(1) time complexity, top pointer decrements.
Peek: O(1), simply reads the element at the top index.

Push：时间复杂度 O(1)，栈顶指针递增。
Pop：时间复杂度 O(1)，栈顶指针递减。
Peek：O(1)，仅需读取栈顶索引处的元素。

When implementing with an array, a stack overflow occurs if there is no space left. Dynamic implementations using linked lists can grow indefinitely, making overflow less of a concern.

使用数组实现时，如果没有剩余空间则会发生栈溢出。使用链表的动态实现可以无限增长，溢出问题不那么严重。

4. Applications of Stacks in Exam Questions | 栈在考试题中的应用

Edexcel exam questions often ask you to trace stack states during the evaluation of postfix expressions, or to show how a stack handles subroutine calls. For example, the expression “2 3 + 4 *” can be evaluated step by step using a stack: push 2, push 3, encounter ‘+’ -> pop two, add, push result 5, push 4, encounter ‘*’ -> pop 5 and 4, multiply, push 20.

Edexcel 考题经常会让你跟踪后缀表达式求值过程中的栈状态，或展示栈如何处理子程序调用。例如，表达式 “2 3 + 4 *” 可以使用栈逐步求值：push 2，push 3，遇到 ‘+’ -> 弹出两个，相加，推入结果 5，push 4，遇到 ‘*’ -> 弹出 5 和 4，相乘，推入 20。

Backtracking algorithms, depth-first search, and the ‘undo’ feature in text editors all rely on stacks. You should be able to describe the role of the stack in each case using correct technical vocabulary.

回溯算法、深度优先搜索以及文本编辑器中的“撤销”功能都依赖于栈。你应能使用正确的技术词汇描述栈在各个场景中的作用。

5. Queue ADT: First In, First Out | 队列 ADT：先进先出

A queue operates on the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front, just like a line of people waiting for a bus. The first person to join the queue is the first to board.

队列按照先进先出 (FIFO) 原则运作。元素在队尾加入，从队首移除，就像排队等公交车的人群。最先排队的人最先上车。

Core operations include enqueue(item) to add to the rear, dequeue() to remove and return the front item, peek() to view the front item, and isEmpty(). Queues are heavily used in scheduling, buffering, and breadth-first search.

核心操作包括 enqueue(item) 将元素加入队尾，dequeue() 移除并返回队首元素，peek() 查看队首元素，以及 isEmpty()。队列广泛应用于调度、缓冲和广度优先搜索。

6. Enqueue and Dequeue Step by Step | Enqueue 和 Dequeue 逐步解析

Suppose we create an empty queue. enqueue(‘A’) places ‘A’ at the front and rear. enqueue(‘B’) adds ‘B’ at the rear, so the order is A → B. Now dequeue() removes ‘A’ and returns it, leaving ‘B’ at the front. If we then enqueue(‘C’), the queue becomes B → C. A second dequeue() retrieves ‘B’.

假设我们创建一个空队列。enqueue(‘A’) 将 ‘A’ 置于队首和队尾。enqueue(‘B’) 将 ‘B’ 添加到队尾，此时顺序为 A → B。现在 dequeue() 移除 ‘A’ 并返回，队首变为 ‘B’。若再执行 enqueue(‘C’)，队列变为 B → C。第二次 dequeue() 取出 ‘B’。

Time complexities for these operations are O(1) when using a linked list or a circular array with front and rear pointers. A naive linear array approach may require O(n) shifting, which is inefficient and should be avoided in design answers.

使用链表或带有 front 和 rear 指针的循环数组时，这些操作的时间复杂度为 O(1)。初级的线性数组方式可能需要 O(n) 的元素移动，效率低下，设计答案时应避免使用。

7. Circular Queue: Avoiding Wasted Space | 循环队列：避免空间浪费

With a linear array, after many enqueue and dequeue operations, the front index moves forward and the space before it becomes unusable. A circular queue solves this by treating the array as circular: when the rear reaches the end, it wraps around to the beginning if space is available.

对于线性数组，经过多次 enqueue 和 dequeue 操作后，front 索引前移，其前方的空间变得不可用。循环队列通过将数组视为环形来解决这个问题：当 rear 到达末尾时，如果有空间，就绕回到开头。

We maintain front and rear pointers and a count or a flag to distinguish between empty and full states. For an array of size N, the condition (rear + 1) % N == front indicates the queue is full. This is a key implementation detail that may appear in A-Level written code questions.

我们维护 front 和 rear 指针以及一个计数器或标志来区分空和满的状态。对于大小为 N 的数组，条件 (rear + 1) % N == front 表示队列已满。这是一个关键的实现细节，可能在 A-Level 书面代码题中出现。

8. Priority Queue: Ordering by Importance | 优先队列：按重要性排序

A priority queue does not strictly follow FIFO; each element has a priority, and the element with the highest priority is dequeued first. In the Edexcel specification, this ADT is often discussed in the context of scheduling processes in an operating system or in simulations.

优先队列并不严格遵循 FIFO；每个元素都有一个优先级，优先级最高的元素最先出队。在 Edexcel 大纲中，这种 ADT 通常会在操作系统进程调度或模拟的背景下讨论。

You could implement a priority queue using an unordered array (insert O(1), extract O(n)) or an ordered array (insert O(n), extract O(1)). A binary heap provides O(log n) for both insert and extract, which is ideal but beyond the basic A-Level scope.

可以使用无序数组（插入 O(1)，提取 O(n)）或有序数组（插入 O(n)，提取 O(1)）来实现优先队列。二叉堆可将插入和提取都优化为 O(log n)，这虽然理想，但超出 A-Level 基础范围。

9. Implementing Stacks and Queues Using Arrays | 使用数组实现栈和队列

For a stack, an array implementation requires a variable topIndex (initialized to -1). Push increments topIndex and stores the new item at that index. Pop returns the item at topIndex then decrements topIndex. Overflow must be checked against the array’s maximum size.

对于栈，数组实现需要一个变量 topIndex（初始化为 -1）。push 递增 topIndex 并将新元素存储在该索引处。pop 返回 topIndex 处的元素，然后递减 topIndex。必须根据数组的最大大小检查溢出。

For a linear queue with an array, we can use frontIndex and rearIndex. Initially, both are set to -1. Enqueue increments rearIndex and inserts the item. Dequeue increments frontIndex and returns that item. However, this leads to the “drifting” problem mentioned earlier, so a circular array is preferred.

对于使用数组的线性队列，我们可以使用 frontIndex 和 rearIndex。初始时均设为 -1。enqueue 递增 rearIndex 并插入元素。dequeue 递增 frontIndex 并返回对应元素。但这会导致前面提到的“漂移”问题，因此循环数组更受推崇。

10. Comparing Stacks and Queues: Exam-Style Analysis | 栈与队列对比：考试风格分析

Feature / 特性	Stack / 栈	Queue / 队列
Ordering Principle / 排序原则	LIFO / 后进先出	FIFO / 先进先出
Insertion Point / 插入点	Top / 栈顶	Rear / 队尾
Removal Point / 移除点	Top / 栈顶	Front / 队首
Typical Uses / 典型用途	Recursion, undo, parsing / 递归，撤销，解析	Print spooler, BFS, buffers / 打印假脱机，BFS，缓冲

When answering comparative questions, always highlight how the access rule influences the choice of ADT. For instance, LIFO suits nested structures, while FIFO suits sequential processing.

回答比较类问题时，务必强调访问规则如何影响 ADT 的选择。例如，LIFO 适合嵌套结构，而 FIFO 适合顺序处理。

11. Common Pitfalls and Edexcel Marking Points | 常见错误与 Edexcel 评分要点

A common mistake is confusing underflow with an empty check – underflow occurs when trying to pop from an empty stack, and you must handle it in algorithm descriptions. Also, when tracing algorithms, carefully update pointers; losing a pointer update costs marks.

一个常见错误是将下溢与空状态检查混淆——下溢是指尝试从空栈中弹出元素，你需要在算法描述中处理它。此外，在跟踪算法时，要仔细更新指针；遗漏指针更新会被扣分。

For top marks, always state the time complexity of each operation and justify it. Use correct terminology: “linear array”, “circular array”, “linked list”, “static”, “dynamic”. Marks are also awarded for discussing trade-offs between memory usage and speed.

为了获得高分，要始终说明每种操作的时间复杂度并给出理由。使用正确的术语：“线性数组”、“循环数组”、“链表”、“静态”、“动态”。讨论内存使用与速度之间的权衡也能得分。

12. Summary and Revision Tips | 总结与复习技巧

Stacks and queues are simple but powerful ADTs. Remember: stack = LIFO, queue = FIFO. Practise tracing algorithms for postfix, infix-to-postfix conversion, and circular queue states. Be ready to write pseudocode for push, pop, enqueue, and dequeue using arrays or linked lists.

栈和队列是简单但强大的 ADT。记住：栈 = LIFO，队列 = FIFO。练习跟踪后缀表达式、中缀转后缀转换以及循环队列状态的算法。准备好用数组或链表编写 push、pop、enqueue 和 dequeue 的伪代码。

Use revision flashcards for the ADT operations and their O(1) conditions. Create your own problem examples and draw the state changes step by step. The more visual your practice, the better you will perform on exam day.

使用复习闪卡记忆 ADT 操作及它们的 O(1) 条件。创建你自己的问题示例，并逐步画出状态变化。练习越可视化，考试当天的表现就越好。

Published by TutorHao | Programming Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Stack and Queue Operations for A-Level Programming | A-Level 编程中的栈和队列操作