GCSE Computer Science: Stacks and Queues - Key Points | GCSE 计算机：栈与队列考点精讲

📚 GCSE Computer Science: Stacks and Queues – Key Points | GCSE 计算机：栈与队列考点精讲

Stacks and queues are fundamental abstract data structures that every GCSE Computer Science student must understand. They define how data is organised and accessed, appearing in countless algorithms and real-world systems. This article breaks down the key points for both data structures, covering their behaviour, operations, implementations, typical applications, common pitfalls and exam-style comparisons.

栈和队列是每个 GCSE 计算机学生必须掌握的基本抽象数据结构。它们定义了数据组织和访问的方式，出现在无数算法和现实系统中。本文详细拆解两种数据结构的关键考点，涵盖其行为、操作、实现方法、典型应用、常见陷阱以及考试中常见的对比题型。

1. What is a Stack? | 什么是栈？

A stack is a linear data structure that follows the LIFO principle — Last In, First Out. Imagine a pile of plates: the last plate placed on top is the first one to be taken off. You can only add (push) or remove (pop) items from the top of the stack. Access to any element below the top is not allowed without first removing all elements above it.

栈是一种遵循 LIFO（后进先出）原则的线性数据结构。想象一摞盘子：最后放上去的盘子会被第一个取走。只能在栈顶添加（push）或移除（pop）元素。如果不先移除其上方所有元素，就无法访问栈顶以下的任何元素。

The stack has a single access point called the top. Data elements are stored in order, but only the most recently added element is directly visible. Stacks are used extensively in programming language execution, recursion, and undo mechanisms.

栈只有一个访问点，称为栈顶。数据按顺序存储，但只有最近添加的元素是直接可见的。栈在编程语言执行、递归以及撤销机制中被广泛使用。

2. Core Stack Operations | 栈的核心操作

The essential stack operations are:

栈的核心操作包括：

push(item) — adds an item to the top of the stack.
push(item) — 将一个元素添加到栈顶。
pop() — removes and returns the top item. The stack size decreases by one.
pop() — 移除并返回栈顶元素。栈大小减一。
peek() or top() — returns the top item without removing it.
peek() 或 top() — 返回栈顶元素但不移除它。
isEmpty() — checks whether the stack contains any elements.
isEmpty() — 检查栈是否为空。
isFull() — used only when the stack has a fixed capacity (e.g. array implementation).
isFull() — 仅在栈有固定容量时使用（例如数组实现）。

A stack overflow occurs when you try to push onto a full stack. A stack underflow occurs when you try to pop from an empty stack. Both are runtime errors that exam questions like to test.

当试图向已满的栈执行 push 操作时会发生栈溢出。当试图从空栈执行 pop 操作时会发生栈下溢。两者都是运行时错误，是考试中喜欢考察的知识点。

Push: top ← top + 1; stack[top] ← item

推入：栈顶 ← 栈顶 + 1；栈[栈顶] ← 元素

Pop: item ← stack[top]; top ← top − 1

弹出：元素 ← 栈[栈顶]；栈顶 ← 栈顶 – 1

3. Stack Implementations | 栈的实现方式

Stacks can be implemented using either arrays or linked lists. Each method affects memory usage and flexibility, which is a common comparison question.

栈可以使用数组或链表来实现。每种方式会影响内存使用和灵活性，是常见的对比考点。

Array implementation: A fixed size is allocated. A variable ‘top’ tracks the index of the current top element (often -1 when empty). Pushing increments top; popping decrements it. The advantage is simple index-based access; the disadvantage is a fixed size that may cause overflow or wasted memory.

数组实现：分配固定大小。用一个变量 ‘top’ 追踪当前栈顶元素的索引（空栈时常设为 -1）。推入时 top 递增；弹出时递减。优点是索引访问简单；缺点是大小固定，可能导致溢出或浪费内存。

Linked list implementation: Each node contains data and a pointer to the next node. The ‘top’ points to the head of the list. Pushing inserts a new node at the head; popping removes the head node. This implementation grows dynamically and avoids overflow (until heap memory is exhausted), but requires extra memory for pointers.

链表实现：每个节点包含数据和指向下一个节点的指针。’top’ 指向链表的头节点。推入时在头部插入新节点；弹出时移除头节点。这种实现可以动态增长，避免溢出（直到堆内存耗尽），但需要额外的指针内存。

4. Applications of Stacks | 栈的应用场景

Stacks appear in many real-world and programming contexts:

栈出现在许多现实世界和编程场景中：

Call stack: When a function calls another function, the return address and local variables are pushed onto the call stack. Upon return, the last function’s data is popped first.
调用栈：当一个函数调用另一个函数时，返回地址和局部变量被推入调用栈。返回时，最后进入的函数数据首先被弹出。
Undo feature: Most applications record actions on a stack. Pressing Ctrl+Z pops the last action and reverses it.
撤销功能：多数应用将操作记录在栈中。按下 Ctrl+Z 会弹出上一个操作并逆转它。
Expression evaluation: Stacks convert infix expressions to postfix and evaluate them (e.g., ‘3 + 4 × 2’ becomes ‘3 4 2 × +’).
表达式求值：栈用于将中缀表达式转换为后缀表达式并求值（例如 ‘3 + 4 × 2’ 转为 ‘3 4 2 × +’）。
Backtracking: Maze solving, depth-first search and puzzle games use stacks to remember paths.
回溯算法：迷宫求解、深度优先搜索和谜题游戏使用栈来记录路径。

5. What is a Queue? | 什么是队列？

A queue is a linear data structure that follows the FIFO principle — First In, First Out. Picture a line of people waiting: the first person to join the queue is the first to be served. Elements are added at the rear (back) and removed from the front.

队列是一种遵循 FIFO（先进先出）原则的线性数据结构。想象一排正在等待的人：最早加入队列的人最先得到服务。元素在队尾（后端）加入，从队首（前端）移除。

Access is strictly ordered; you cannot remove an element from the middle without violating the FIFO rule. This makes queues ideal for scheduling, buffering, and managing shared resources.

访问严格按顺序进行；如果不违反 FIFO 规则，就无法从中间移除元素。这使得队列非常适合调度、缓冲以及管理共享资源。

6. Core Queue Operations | 队列的核心操作

The primary queue operations are:

队列的主要操作如下：

enqueue(item) — adds an item to the rear of the queue.
enqueue(item) — 将元素添加到队尾。
dequeue() — removes and returns the item at the front. The front pointer moves to the next element.
dequeue() — 移除并返回队首元素。队首指针移动到下一个元素。
front() or peek() — returns the front element without removing it.
front() 或 peek() — 返回队首元素但不移除。
isEmpty() — checks if the queue is empty.
isEmpty() — 检查队列是否为空。
isFull() — relevant only for fixed-capacity implementations.
isFull() — 仅与固定容量实现相关。

Just like stacks, attempting to dequeue from an empty queue causes underflow, and attempting to enqueue into a full queue causes overflow. These errors must be guarded against in code.

与栈类似，尝试从空队列中出队会导致下溢，尝试向已满队列中入队会导致溢出。代码中必须防范这些错误。

Enqueue: rear ← rear + 1; queue[rear] ← item

入队：队尾 ← 队尾 + 1；队列[队尾] ← 元素

Dequeue: item ← queue[front]; front ← front + 1

出队：元素 ← 队列[队首]；队首 ← 队首 + 1

7. Queue Implementations | 队列的实现方式

Queues can also be implemented with arrays or linked lists. The array version often uses a circular queue to reuse empty slots and avoid wasted space as front advances.

队列同样可以用数组或链表实现。数组版本常使用循环队列来重用被腾出的空槽，避免随着队首前移而浪费空间。

In a circular array queue, when rear reaches the end, it wraps around to index 0 if slots are free. This requires careful use of modular arithmetic: rear ← (rear + 1) mod SIZE. Front and rear pointers chase each other, and a full queue is distinguished from an empty queue by leaving one slot unused or using a separate counter.

在循环数组队列中，当队尾抵达末尾时，如果还有空槽，会绕回到索引 0。这需要谨慎使用模运算：队尾 ← (队尾 + 1) mod 大小。队首和队尾指针相互追逐，而为了区分满队列和空队列，常采用保留一个空位或使用单独计数器的方法。

Linked list implementation: a queue is easily built with a singly linked list maintaining both front and rear pointers. Enqueue appends a node at the rear; dequeue removes the node at the front. No overflow problem exists (except memory limits), and it handles dynamic size elegantly.

链表实现：使用单链表并同时维护队首和队尾指针可以轻松构建队列。入队时在队尾添加节点；出队时移除队首节点。不存在溢出问题（除内存限制外），并能优雅地处理动态大小。

8. Applications of Queues | 队列的应用场景

Queues are everywhere in computing and everyday life:

队列在计算和日常生活中无处不在：

Printer spooler: Print jobs are queued in order and processed one by one.
打印假脱机：打印作业按顺序排队，逐个处理。
Keyboard buffer: Keystrokes are stored in a queue so they can be processed in order without missing any.
键盘缓冲区：按键被存储在队列中，以便按顺序处理，不会遗漏。
Task scheduling: The operating system uses queues to manage processes waiting for the CPU (ready queue).
任务调度：操作系统使用队列来管理等待 CPU 的进程（就绪队列）。
Breadth-first search: Graph algorithms use a queue to explore nodes level by level.
广度优先搜索：图算法利用队列逐层探索节点。
Call centre systems: Customers wait in a virtual queue until an agent is free.
呼叫中心系统：客户在虚拟队列中等待，直到有空闲客服。

9. Stack vs Queue: Comparison Table | 栈与队列比较表

GCSE exams love to ask you to compare stacks and queues. The following table summarises the key differences:

GCSE 考试喜欢要求比较栈和队列。下表总结了关键区别：

Feature	Stack	Queue
Order principle	LIFO (Last In, First Out)	FIFO (First In, First Out)
Add operation	push()	enqueue()
Remove operation	pop()	dequeue()
Access point(s)	Top only	Front and rear
When added item is removed	Removed before items added earlier	Removed after items added earlier
Real-world analogy	Pile of plates, back button	Checkout line, printer queue
Typical use	Undo, recursion, expression evaluation	Buffering, scheduling, breadth-first search

10. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧

Students often lose marks by confusing the access principles. Remember: a stack is always LIFO; a queue is always FIFO. When drawing diagrams, clearly label top, front, rear and show pointers accurately.

学生常因混淆访问原则而失分。要牢记：栈永远是 LIFO；队列永远是 FIFO。画图时，务必清楚标记栈顶、队首、队尾，并准确表示指针。

Pointer updates must be done in the correct order. For a stack push, increment top first then store the item. For a queue enqueue, update rear then place the item. Mixing up the order can cause data corruption or lost elements.

指针更新必须按正确顺序进行。对于栈推入，先递增 top 再存储元素。对于队列入队，先更新 rear 再放置元素。混淆顺序会导致数据损坏或元素丢失。

When tracing algorithms, keep a visual stack/queue table with separate columns for the state after each operation. GCSE papers often ask you to trace a sequence of pushes and pops, or enqueries and dequeues, and show the resulting data structure or the output returned.

追踪算法时，要维护可视化的栈/队列表格，用单独的列展示每次操作后的状态。GCSE 试卷常要求追踪一连串 push/pop 或 enqueue/dequeue 操作，并给出最终的数据结构或返回的输出。

Check for underflow and overflow conditions in every code snippet. Empty/full checks must be performed before pop/dequeue and push/enqueue respectively. If the question asks for pseudocode, always include those guards.

在每个代码片段中都要检查下溢和溢出条件。在执行 pop/dequeue 之前必须检查是否为空；执行 push/enqueue 之前必须检查是否已满。如果题目要求伪代码，一定要加入这些保护条件。

11. Tracing Example for the Exam | 考试追踪示例

Consider the following operations on an initially empty stack: push(5), push(3), pop(), push(7), push(1), pop(), pop().

考虑在一个初始为空栈上执行以下操作：push(5), push(3), pop(), push(7), push(1), pop(), pop()。

After push(5): stack = [5]
push(5) 后：栈 = [5]
After push(3): stack = [5, 3]
push(3) 后：栈 = [5, 3]
pop() returns 3 → stack = [5]
pop() 返回 3 → 栈 = [5]
push(7): stack = [5, 7]
push(7)：栈 = [5, 7]
push(1): stack = [5, 7, 1]
push(1)：栈 = [5, 7, 1]
pop() returns 1 → stack = [5, 7]
pop() 返回 1 → 栈 = [5, 7]
pop() returns 7 → stack = [5]
pop() 返回 7 → 栈 = [5]

Now for a queue: enqueue(10), enqueue(20), dequeue(), enqueue(30), dequeue(), dequeue().

队列示例：enqueue(10), enqueue(20), dequeue(), enqueue(30), dequeue(), dequeue()。

enqueue(10): queue = [10]
enqueue(10)：队列 = [10]
enqueue(20): queue = [10, 20]
enqueue(20)：队列 = [10, 20]
dequeue() returns 10 → queue = [20]
dequeue() 返回 10 → 队列 = [20]
enqueue(30): queue = [20, 30]
enqueue(30)：队列 = [20, 30]
dequeue() returns 20 → queue = [30]
dequeue() 返回 20 → 队列 = [30]
dequeue() returns 30 → queue = []
dequeue() 返回 30 → 队列 = []

Practising short tracing problems like these will build confidence for the written paper.

经常练习这类短小的追踪题可以增强笔试时的信心。

12. Summary and Final Advice | 总结与最后建议

Stacks and queues are simple but powerful data structures. Master their key properties (LIFO vs FIFO), the names of their operations (push/pop vs enqueue/dequeue), and how they are implemented using arrays and linked lists. Be ready to compare them, trace them, and write simple pseudocode that avoids overflow and underflow.

栈和队列是简单但功能强大的数据结构。要熟练掌握它们的关键属性（LIFO 与 FIFO）、操作名称（push/pop 与 enqueue/dequeue）以及如何用数组和链表实现它们。准备好进行对比、追踪，并写出能避免溢出和下溢的简单伪代码。

When tackling an exam question, carefully read whether the structure described behaves like a stack or a queue. If the scenario says ‘most recent action is undone first’, you are dealing with a stack. If it says ‘first-come, first-served’, you are dealing with a queue. Use the correct terminology and your marks will follow.

在解答考试题目时，要仔细判断所描述的结构行为是像栈还是像队列。如果情景说“最近的操作最先被撤销”，那就是栈。如果情景是“先到先服务”，那就是队列。使用正确的术语，成绩自然随之而来。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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

GCSE Computer Science: Stacks and Queues – Key Points | GCSE 计算机：栈与队列 考点精讲