📚 Stacks and Queues in A-Level Edexcel Computer Science | A-Level Edexcel 计算机：栈与队列考点精讲
Stacks and queues are fundamental abstract data types (ADTs) that appear throughout the Edexcel A-Level Computer Science specification. Understanding how they work, where they are applied, and how they can be implemented using static arrays, dynamic structures, or linked lists is essential for the exam. This guide covers the key operations, memory representations, real-world uses, and algorithmic patterns you must master, along with typical examination pitfalls.
栈和队列是 A-Level Edexcel 计算机科学考试大纲中最基础的抽象数据类型 (ADT)。掌握它们的工作原理、应用场景以及如何使用静态数组、动态结构或链表来实现，对考试至关重要。本指南将涵盖栈和队列的关键操作、内存表示、实际应用以及典型的算法模式，并梳理常见考试陷阱。
1. Abstract Data Types and the Core Concept | 抽象数据类型与核心概念
An abstract data type is defined by the operations it supports and not by how those operations are implemented. Stacks and queues are two classic ADTs. A stack follows a Last-In-First-Out (LIFO) principle – the last item added is the first one removed. A queue obeys a First-In-First-Out (FIFO) rule – the first item added is the first to leave. In the exam, you must be able to distinguish between the behaviours of these data structures and describe their interfaces precisely.
抽象数据类型由它所支持的操作来定义，而不是由其实现方式决定。栈和队列是两种经典的 ADT。栈遵循后进先出 (LIFO) 原则——最后加入的元素最先被移除。队列遵守先进先出 (FIFO) 规则——最先加入的元素最先离开。考试中需要能够准确区分这两种数据结构的行为，并精确描述它们的接口。
2. Stack Operations: Push, Pop, Peek, and IsEmpty/IsFull | 栈操作：压入、弹出、窥视及判空/判满
A stack must provide push(item) to add an item to the top, pop() to remove and return the top item, and peek() or top() to return the top item without removing it. Boolean checks isEmpty() and isFull() are needed when the stack has a fixed capacity. The specification expects you to define these operations clearly and to trace their effect on the stack contents and the stack pointer.
栈必须提供 push(item) 在栈顶添加元素，pop() 移除并返回栈顶元素，以及 peek() 或 top() 在不移除的情况下返回栈顶元素。当栈的容量固定时，还需要 isEmpty() 和 isFull() 布尔判断。考纲要求能清晰定义这些操作，并追踪它们对栈内容和栈指针的影响。
3. Queue Operations: Enqueue, Dequeue, Front, and Auxiliary Tests | 队列操作：入队、出队、访问队首及辅助测试
A queue’s key operations are enqueue(item) to add an item to the rear, dequeue() to remove and return the front item, and front() to inspect the front element without removal. Just like stacks, queues require isEmpty() and isFull() for bounded implementations. You should be able to write pseudocode for these operations and simulate a queue’s state after a sequence of calls – a frequent exam task.
队列的关键操作包括 enqueue(item) 将元素添加到队尾，dequeue() 移除并返回队首元素，以及 front() 查看队首元素但不移除。和栈一样，有界队列需要 isEmpty() 和 isFull() 检查。应能够为这些操作编写伪代码，并模拟一系列调用后队列的状态——这是考试的常见题型。
4. Implementing a Stack Using a Static Array | 使用静态数组实现栈
A stack can be implemented with a fixed-size array and an integer pointer (often called top). Initially top is set to -1 to represent an empty stack. Pushing increments top and stores the new element at that index. Popping returns the element at top and then decrements top. Overflow occurs when pushing to a full stack, and underflow when popping from an empty one. You must be able to write clean, boundary-checked code in pseudocode or a high-level language.
栈可以用固定大小的数组和整型指针（常称为 top）来实现。初始化时 top 设为 -1 表示空栈。压入操作将 top 加 1，并在该下标存储新元素。弹出操作返回 top 指向的元素，然后将 top 减 1。向已满的栈压入会发生上溢，从空栈弹出会发生下溢。必须能够使用伪代码或高级语言写出边界检查完善的代码。
5. Implementing a Queue Using a Static Circular Array | 使用静态循环数组实现队列
A linear array implementation of a queue wastes space because memory vacated by dequeued items cannot be reused. The examination focuses on the circular array solution: two pointers (front and rear) wrap around to the beginning when they reach the end of the array. Enqueue advances the rear pointer and inserts; dequeue advances the front pointer. Full and empty conditions must be carefully distinguished, typically by leaving one unused slot or by using a size counter. This is a classic A-Level programming problem.
线性数组实现队列会浪费空间，因为出队释放的内存无法重用。考试重点在于循环数组解决方案：两个指针（front 和 rear）到达数组末尾时会绕回开头。入队前移 rear 指针并插入；出队前移 front 指针。必须仔细区分满和空的条件，常见做法是空出一个单元或使用 size 计数器。这是经典的 A-Level 编程问题。
6. Dynamic Implementation: Linked Lists | 动态实现：链表
Both stack and queue ADTs can be implemented dynamically using singly linked lists. A stack uses a head pointer; push inserts at the head, and pop removes from the head. A queue needs both head and tail pointers: enqueue adds to the tail, and dequeue removes from the head. Dynamic implementations do not have a fixed capacity, but they require more memory per node for the pointers. Be ready to draw node diagrams and trace pointer manipulations step by step.
栈和队列 ADT 都可以使用单向链表来动态实现。栈用头指针；压入在头部插入元素，弹出从头部移除。队列需要头指针和尾指针：入队添加到尾部，出队从头部移除。动态实现没有固定容量，但每个节点需要额外的指针内存。备考时请准备好绘制节点图并逐步追踪指针操作。
7. Applications: Stacks in Expression Evaluation, Recursion, and Undo | 栈的应用：表达式求值、递归和撤销
Stacks are everywhere in computing. They evaluate postfix (Reverse Polish) expressions by pushing operands and, on encountering an operator, popping the required operands, performing the operation, and pushing the result. Stacks manage subroutine calls via call frames, enabling recursion and return addresses. In user interfaces, undo functionality relies on a stack of commands; the most recent action is reversed first. You should be able to trace these mechanisms given a sequence of operations.
栈在计算中无处不在。它们通过压入操作数计算后缀（逆波兰）表达式，当遇到运算符时弹出所需操作数、执行运算并将结果压入。栈通过调用帧管理子程序调用，支持递归和返回地址。在用户界面中，撤销功能依赖命令栈，最近执行的操作最先被撤销。你应该能够根据给定操作序列追踪这些机制。
8. Applications: Queues in Scheduling and Buffers | 队列的应用：调度与缓冲区
Queues model natural waiting lines. Operating systems use ready queues for CPU scheduling, print spoolers queue documents, and keyboard buffers store keystrokes in order. In a simulation, a queue can represent a checkout line or a network packet buffer. The exam may ask you to explain how FIFO order prevents starvation or ensures fairness, and to compare performance with a stack when order matters.
队列模拟自然的排队场景。操作系统用就绪队列进行 CPU 调度，打印后台处理程序将文档排成队列，键盘缓冲区按顺序储存按键。在模拟中，队列可以表示收银排队或网络数据包缓冲区。考试可能要求解释 FIFO 顺序如何防止饥饿或确保公平性，并在顺序重要时与栈的性能进行比较。
9. Call Stack and Stack Frames | 调用栈与栈帧
When a subroutine is called, the current processor state (return address, parameters, local variables) is pushed onto the call stack as a stack frame. When the subroutine returns, its frame is popped, restoring the previous context. Edexcel questions often ask you to trace a recursive function’s call stack, showing the values of local variables and the order of returns. This reinforces the LIFO nature and the concept of stack depth limits that cause stack overflow in deep recursion.
当调用一个子程序时，当前处理器状态（返回地址、参数、局部变量）作为栈帧压入调用栈。子程序返回时，其帧被弹出，恢复上一级上下文。Edexcel 考题经常要求追踪递归函数的调用栈，展示局部变量的值和返回顺序。这进一步加强了 LIFO 特性以及过深的递归会导致栈溢出的栈深度限制概念。
10. Comparing Stacks and Queues: Exam-Style Traces and Questions | 比较栈与队列：考试风格的追踪与问答
A typical exam question provides a sequence of mixed operations (push, pop, enqueue, dequeue) on both structures and asks you to show the contents after each step. You need to keep the list of elements in order according to the ADT’s discipline. Another common task is to decide which structure – stack or queue – is appropriate for a given scenario (e.g., undo vs. print spooler) and to justify your choice with clear reasoning about LIFO or FIFO.
典型的考试题目会给出对两种结构的一系列混合操作（压入、弹出、入队、出队），并要求展示每一步之后的内容。需要按照 ADT 规则保持元素顺序。另一种常见任务是判断哪种结构（栈还是队列）适用于给定场景（如撤销 vs. 打印后台程序），并用 LIFO 或 FIFO 的清晰推理说明理由。
11. Common Pitfalls and How to Avoid Them | 常见陷阱及对策
Students often confuse overflow/underflow of stacks and queues, especially failing to check boundary conditions in pseudocode. Another frequent error is assuming a circular queue is full when front equals rear; this actually indicates an empty queue unless a counter is used. Also, forgetting to adjust the stack pointer or the queue pointers after an operation leads to incorrect state. Practise writing small functions that explicitly test isEmpty/isFull before mutating the structure.
学生常混淆栈和队列的上溢/下溢，尤其是在伪代码中忘记检查边界条件。另一个常见错误是假设 front 等于 rear 时循环队列为满；实际上除非使用计数器，这种情况标志队列为空。还有，在操作之后忘记调整栈指针或队列指针会导致状态错误。请多练习编写在修改结构之前显式测试 isEmpty/isFull 的小函数。
12. Algorithms: Converting Infix to Postfix Using a Stack | 算法：用栈将中缀表达式转换为后缀表达式
A deeper A-Level topic is the Shunting Yard algorithm, which uses a stack to convert a fully parenthesised or un-parenthesised infix expression into postfix. Operands are output immediately; operators are pushed onto the stack and popped according to precedence and associativity rules, with parentheses forcing early pushes and matching pops. You should be able to simulate the algorithm and explain why a stack is the ideal structure for managing operator ordering.
更深层的 A-Level 主题是调度场算法，该算法使用栈将完全括号化或没有括号的中缀表达式转换为后缀表达式。操作数直接输出；运算符按照优先级和结合性规则压入栈并弹出，括号则强制提前压入和匹配弹出。你应该能够模拟该算法，并解释为什么栈是管理运算符顺序的理想结构。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导