📚 Stacks and Queues in A-Level Computer Science | A-Level 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) in computer science, forming the backbone of many algorithms and system-level processes. In the A-Level syllabus, you are expected not only to understand their behaviour and operations but also to implement them, analyse their efficiency, and apply them to solve real-world problems such as expression evaluation, backtracking, and job scheduling. This article provides a comprehensive revision guide covering every essential concept, from basic definitions to exam-focused tips.
栈和队列是计算机科学中最基础的抽象数据类型（ADT），支撑着众多算法和系统级流程。在A-Level考纲中，你不仅要理解它们的行为和操作，还需掌握实现方式、效率分析，并将其应用于表达式求值、回溯、作业调度等实际问题。本文提供一份全面的复习指南，涵盖从基础定义到考试技巧的所有核心概念。
1. Introduction to Stacks and Queues | 栈与队列简介
An abstract data type (ADT) defines a collection of data and the operations that can be performed on it, without specifying the underlying implementation. Both stacks and queues are linear ADTs that store elements in a specific order. A stack follows a Last-In-First-Out (LIFO) principle, whereas a queue follows a First-In-First-Out (FIFO) principle. These simple rules govern how data is added and removed, making them ideal for scenarios where order of processing matters.
抽象数据类型（ADT）定义了一组数据及可在其上执行的操作，而不规定底层实现。栈和队列都是线性ADT，按特定顺序存储元素。栈遵循后进先出（LIFO）原则，而队列遵循先进先出（FIFO）原则。这些简单规则控制着数据的添加和移除方式，使其非常适用于处理顺序至关重要的场景。
You can visualise a stack like a pile of plates: you can only add or remove a plate from the top. A queue, on the other hand, is like a line of people waiting for a bus: the person who arrives first boards first. These analogies are helpful for remembering the core difference between the two structures.
你可以把栈想象成一叠盘子：只能从顶部添加或移除盘子。而队列则像排队等公交车的人群：最先到达的人最先上车。这些类比有助于记忆两种结构的核心区别。
2. The Stack Data Structure | 栈数据结构
A stack is a restricted linear list where all insertions and deletions occur at one end, called the top. The element that has been in the stack the longest is at the bottom. Because of the LIFO nature, only the top element is accessible at any given time. This limitation makes stack operations extremely efficient, typically O(1) constant time.
栈是一种受限的线性表，所有插入和删除操作都发生在一端，称为栈顶。在栈中停留时间最长的元素位于栈底。由于后进先出的特性，任何时候只能访问栈顶元素。这种限制使得栈操作的效率极高，通常为O(1)常数时间。
Common states of a stack include empty (no elements) and full (if implemented with a fixed capacity). When trying to pop from an empty stack, a stack underflow occurs; pushing onto a full stack causes overflow. Many programming languages handle these errors by raising exceptions, but in low-level implementations such as assembly language, stack overflow can lead to security vulnerabilities.
栈的常见状态包括空栈（无元素）和满栈（若以固定容量实现）。当试图从空栈弹出时，会发生栈下溢；向满栈压入则导致上溢。许多编程语言通过引发异常来处理这些错误，但在低级实现（如汇编语言）中，栈溢出可能导致安全漏洞。
3. Stack Operations | 栈的操作
The primary operations on a stack are push, pop, and peek (or top). Push(item) adds an item to the top of the stack. Pop() removes and returns the top item. Peek() returns the top item without removing it. Additionally, helper functions such as isEmpty() and isFull() are essential for safe stack manipulation, especially when the stack is implemented with a static array.
栈的主要操作包括push、pop和peek（或top）。Push(项)将项添加到栈顶。Pop()移除并返回栈顶项。Peek()返回栈顶项但不移除。此外，辅助函数如isEmpty()和isFull()对于安全的栈操作至关重要，特别是当栈用静态数组实现时。
In pseudocode, a push operation increments the top pointer and assigns the value; pop reads the value and decrements the pointer. The time complexity of all these operations is O(1). This efficiency is one of the reasons stacks are widely used in system software, such as function call management and interrupt handling.
在伪代码中，push操作会递增栈顶指针并赋值；pop读取值并递减指针。所有这些操作的时间复杂度均为O(1)。这种高效是栈被广泛用于系统软件（如函数调用管理和中断处理）的原因之一。
| Operation | Description | Time Complexity |
|---|---|---|
| push(item) | Adds item to top | O(1) |
| pop() | Removes and returns top item | O(1) |
| peek() | Returns top item without removal | O(1) |
| isEmpty() | Checks if stack has no elements | O(1) |
4. Stack Implementation | 栈的实现
A stack can be implemented using an array or a linked list. The array-based approach uses a fixed-size array and an integer top to track the index of the last inserted element. When top equals -1, the stack is empty; when top equals array size minus one, the stack is full. This method is memory-efficient in terms of overhead but wastes space if the capacity is never fully utilised.
栈可以用数组或链表实现。基于数组的方法使用一个固定大小的数组和一个整数top来跟踪最后插入元素的索引。当top等于-1时，栈为空；当top等于数组大小减一时，栈为满。这种方法在开销方面内存效率高，但如果容量从未被完全使用，则会浪费空间。
Alternatively, a linked list implementation dynamically allocates nodes for each new element. The top of the stack corresponds to the head of the linked list. Push inserts a node at the head, and pop removes the head node. This dynamic approach consumes more memory per element (due to pointer storage) but eliminates the overflow problem associated with static arrays, constrained only by available heap memory. A-Level exams often ask you to compare these two implementations in terms of memory usage and speed.
或者，链表实现会为每个新元素动态分配节点。栈顶对应链表的头部。push在头部插入节点，pop移除头部节点。这种动态方法每个元素消耗更多内存（由于需存储指针），但消除了静态数组的上溢问题，仅受可用堆内存的限制。A-Level考试常要求你从内存使用和速度两方面比较这两种实现。
5. Applications of Stacks | 栈的应用
Stacks are essential in managing subroutine calls. When a function is called, the program counter, local variables, and return address are pushed onto the call stack. When the function returns, this information is popped, and execution resumes from the correct point. This mechanism supports recursion and nested function invocations.
栈在管理子例程调用中至关重要。当函数被调用时，程序计数器、局部变量和返回地址会被压入调用栈。当函数返回时，这些信息被弹出，程序从正确的位置继续执行。这种机制支持递归和嵌套函数调用。
Another classic application is expression evaluation and syntax parsing. Compilers use stacks to convert infix notation (e.g., A + B) to postfix (A B +) and to evaluate postfix expressions. The shunting-yard algorithm and stack-based evaluation scan tokens and use a stack to hold operands and operators, respecting precedence and associativity. Similarly, checking for balanced parentheses, brackets, and braces in source code is a straightforward stack problem: push opening symbols, and pop when a matching closing symbol is encountered; any mismatch or non-empty stack at the end indicates an error.
另一个经典应用是表达式求值和语法解析。编译器使用栈将中缀表示法（如A + B）转换为后缀（A B +）并计算后缀表达式。调度场算法和基于栈的求值会扫描标记，并利用栈存放操作数和运算符，同时考虑优先级和结合性。同样，检查源代码中的括号、方括号和大括号是否匹配也是一个简单的栈问题：遇到开符号则压入，遇到匹配的闭符号则弹出；任何不匹配或结束时栈非空都表示错误。
Undo functionality in software, back-button navigation in browsers, and depth-first search in graphs all rely on the LIFO behaviour of stacks. In each case, the most recent state or node is revisited first.
软件中的撤销功能、浏览器的后退按钮以及图的深度优先搜索都依赖栈的后进先出行为。在每种情形下，最近的状态或节点会最先被重新访问。
6. The Queue Data Structure | 队列数据结构
A queue is a linear collection where elements are added at one end, the rear (or tail), and removed from the other end, the front (or head). This FIFO discipline ensures that elements are processed in the order they arrive. Queues are pervasive in computing, from printer spooling to CPU task scheduling and message buffering.
队列是一个线性集合，元素在一端（队尾）添加，从另一端（队首）移除。这种先进先出规则确保元素按到达顺序处理。队列在计算中无处不在，从打印机假脱机到CPU任务调度和消息缓冲。
Like stacks, queues have empty and full states. However, because both ends of a queue move as elements are added and removed, a simple linear array implementation can suffer from the “drifting” problem, where unused space appears at the front but new elements cannot be added because the rear has reached the physical end of the array. This is elegantly solved by the circular queue, discussed later.
与栈类似，队列有空和满状态。然而，由于队列的两端会随着元素添加和移除而移动，简单的线性数组实现会遇到“漂移”问题：虽然队首前出现了未使用的空间，但队尾已到达数组物理末端，导致无法添加新元素。后面讨论的循环队列优雅地解决了这一问题。
7. Queue Operations | 队列的操作
The fundamental queue operations are enqueue and dequeue. Enqueue(item) inserts an item at the rear of the queue. Dequeue() removes and returns the item at the front. Auxiliary operations include peek() (inspect the front element without removing it), isEmpty(), and isFull(). All these operations are designed to run in O(1) time, preserving the queue’s efficiency.
队列的基本操作是enqueue和dequeue。Enqueue(项)将一个项插入队尾。Dequeue()移除并返回队首的项。辅助操作包括peek()（查看队首元素但不移除）、isEmpty()和isFull()。所有这些操作都设计为O(1)时间完成，从而保持队列的高效性。
In pseudocode, an array-based enqueue increments the rear pointer (modulo capacity in circular implementations) and stores the value; dequeue reads the front value and increments the front pointer. It is critical to handle the empty condition correctly: typically, when front and rear pointers become equal after a dequeue, the queue is considered empty and pointers are reset to the initial state.
在伪代码中，基于数组的enqueue递增rear指针（在循环实现中取模容量）并存储值；dequeue读取front值并递增front指针。正确处理空队列情况至关重要：通常，当dequeue后front和rear指针相等时，队列被视为空，并将指针重置为初始状态。
8. Queue Implementation | 队列的实现
Queues can be implemented using static arrays, dynamic circular arrays, or linked lists. A naive array implementation with two integer indices front and rear is simple but falls prey to the “one-off” drain problem, where the queue appears full despite empty slots at the beginning. To evaluate this approach, exam questions may ask you to trace the changing indices and identify wasted space.
队列可以用静态数组、动态循环数组或链表实现。使用两个整数索引front和rear的朴素数组实现很简单，但会遭遇“一次性”耗尽问题：尽管数组开头有空槽，队列却看似已满。为评估这种方法，考试题目可能要求你追踪索引变化并识别浪费的空间。
A linked list implementation circumvents these issues by dynamically creating nodes. The front pointer references the head node, and the rear pointer references the tail node. Enqueueing involves adding a node after the tail and updating the rear; dequeueing removes the head node and updates the front. This dynamic structure never suffers from artificial overflow, but as with the linked list stack, it incurs pointer overhead. The choice between array (circular) and linked list depends on the system’s memory constraints and the predictability of the queue size.
链表实现通过动态创建节点来规避这些问题。front指针引用头节点，rear指针引用尾节点。入队涉及在尾节点后添加节点并更新rear；出队移除头节点并更新front。这种动态结构永远不会遭受人为溢出，但与链表栈一样，它会产生指针开销。在数组（循环）和链表之间的选择取决于系统的内存约束和队列大小的可预测性。
9. Circular Queues | 循环队列
A circular queue treats the underlying array as if the first index follows the last, forming a ring. This is achieved by moving the front and rear pointers using modular arithmetic: front = (front + 1) % capacity and rear = (rear + 1) % capacity. This elegant solution reuses the slots vacated by dequeued elements, eliminating the shift-waste problem of linear queues and ensuring O(1) amortised enqueue and dequeue operations.
循环队列将底层数组视为首尾相连的环。这是通过使用取模运算移动front和rear指针来实现的：front = (front + 1) % capacity，rear = (rear + 1) % capacity。这种优雅的方案复用了出队元素腾出的槽位，消除了线性队列的移位浪费问题，并确保摊销的O(1)入队和出队操作。
However, distinguishing between a full queue and an empty queue becomes tricky because both states can result in front equalling rear. Two common strategies are: (1) sacrifice one cell—the queue is full when (rear + 1) % capacity equals front; (2) maintain an explicit count variable. The A-Level syllabus typically favours the first method for its simplicity. You must be able to draw step-by-step diagrams of circular queue operations and calculate the number of elements at any given state using the formula: (rear – front + capacity) % capacity.
然而，区分满队列和空队列变得棘手，因为这两种状态都可能使front等于rear。两种常见策略是：(1) 牺牲一个单元——当(rear + 1) % capacity等于front时队列为满；(2) 维护一个显式的计数变量。A-Level考纲通常青睐第一种方法的简洁性。你必须能够逐步画出循环队列操作的示意图，并使用公式 (rear – front + capacity) % capacity 计算任意状态下的元素数量。
10. Priority Queues | 优先级队列
A priority queue is a special variant where each element has a priority, and the element with the highest priority is dequeued before lower-priority elements, regardless of insertion order. If two elements share the same priority, FIFO order may be applied (stable priority queue). Priority queues are not strictly FIFO; they extend the queue ADT with a prioritisation mechanism.
优先级队列是一种特殊变体，其中每个元素都有一个优先级，最高优先级的元素在较低优先级元素之前出队，而不考虑插入顺序。如果两个元素具有相同优先级，则可应用FIFO顺序（稳定优先级队列）。优先级队列并非严格的先进先出；它们通过优先级机制扩展了队列ADT。
Common implementations include heaps (binary heap, Fibonacci heap) which offer O(log n) insertion and O(1) or O(log n) extraction, and unordered arrays or linked lists which may offer O(1) insertion but O(n) extraction. In A-Level, you may need to discuss the concept and compare the efficiency of different underlying structures. Real-world applications include Dijkstra’s shortest path algorithm, CPU scheduling (multi-level feedback queues), and bandwidth management.
常见的实现包括堆（二叉堆、斐波那契堆），提供O(log n)插入和O(1)或O(log n)提取，以及无序数组或链表，它们可能提供O(1)插入但O(n)提取。在A-Level中，你可能需要讨论这一概念并比较不同底层结构的效率。实际应用包括Dijkstra最短路径算法、CPU调度（多级反馈队列）和带宽管理。
11. Comparing Stacks and Queues | 栈与队列对比
Although both are linear ADTs with constrained access, their differing order principles dictate their suitability for different tasks. A stack’s LIFO nature makes it ideal for scenarios requiring reversal, nested structures, or backtracking, while a queue’s FIFO nature suits fair scheduling, buffering, and breadth-first traversal. The table below summarises key differences.
尽管两者都是具有受限访问的线性ADT，但它们不同的顺序原则决定了它们适用于不同的任务。栈的后进先出特性使其理想于需要反转、嵌套结构或回溯的场景，而队列的先进先出特性则适合公平调度、缓冲和广度优先遍历。下表总结了关键区别。
| Aspect | Stack | Queue |
|---|---|---|
| Order Principle | LIFO (Last-In-First-Out) | FIFO (First-In-First-Out) |
| Insertion Point | Top | Rear |
| Deletion Point | Top | Front |
| Key Applications | Function calls, undo, parsing | Scheduling, buffering, BFS |
| Typical Overflow Risk | Stack overflow (unbounded recursion) | Buffer overflow in fixed arrays |
When choosing between a stack and a queue, consider the required order of processing. If the last added element must be processed first, a stack is appropriate. If elements must be processed in arrival order, a queue is the correct choice. A common exam question asks you to justify your choice of data structure for a given scenario, referencing these properties.
在选择栈或队列时，需考虑所需的处理顺序。如果最后添加的元素必须最先处理，栈是合适的。如果元素必须按到达顺序处理，队列是正确的选择。常见的考试题要求你根据给定场景论证数据结构的选择，并引用这些特性。
12. Exam Tips for Stacks and Queues | 栈与队列考试技巧
In A-Level written papers, you are frequently required to trace stack and queue operations by showing the state after each step. Draw the structure visually, marking the top/front/rear pointers. For circular queues, always apply modular arithmetic and clearly indicate when the array wraps around. Practice with finite capacities and demonstrate underflow/overflow conditions explicitly.
在A-Level笔试中，常要求你通过展示每个操作后的状态来追踪栈和队列操作。用图示画出结构，标记top/front/rear指针。对于循环队列，务必应用取模运算，并清楚地指明数组何时绕回。练习有限容量，并明确展示下溢/上溢条件。
When implementing these ADTs in pseudocode, remember to check boundary conditions first. For stack push, verify not isFull(); for pop, check not isEmpty(). In queue dequeue, check for empty before accessing the front element. Use meaningful variable names like stackArray, topPointer, queueArray, frontIndex, and rearIndex. In linked list implementations, handle the special cases of inserting into an empty structure and deleting the last element, as these require updating both front and rear pointers.
在用伪代码实现这些ADT时，记得首先检查边界条件。对于栈push，验证not isFull()；对于pop，检查not isEmpty()。在队列dequeue中，访问队首元素前检查是否为空。使用有意义的变量名，如stackArray、topPointer、queueArray、frontIndex和rearIndex。在链表实现中，处理插入空结构和删除最后一个元素的特殊情况，因为这些情况需要同时更新front和rear指针。
Finally, link theory to real-world contexts in long-answer questions. For example, explain how a compiler uses a stack for parsing and a queue for buffering I/O streams. Citing concrete scenarios demonstrates deeper understanding and often earns higher marks. Revise the standard algorithms (infix to postfix, bracket matching, round-robin scheduling) until you can reproduce them accurately under timed conditions.
最后，在长答题中将理论与实际情境联系起来。例如，解释编译器如何用栈进行解析，以及如何用队列缓冲I/O流。引用具体场景能展示更深入的理解，通常能获得更高分数。反复复习标准算法（中缀转后缀、括号匹配、轮询调度），直到能够在限时条件下准确重现。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply