GCSE WJEC Computer Science: Stacks and Queues Exam Focus | GCSE WJEC 计算机：栈与队列 考点精讲

📚 GCSE WJEC Computer Science: Stacks and Queues Exam Focus | GCSE WJEC 计算机：栈与队列 考点精讲

Stacks and queues are two of the most important abstract data types you will encounter in GCSE WJEC Computer Science. They are used to manage data in a specific order and form the basis of many real-world computing processes, from undo functions in software to printer spooling. This article breaks down everything you need to know for the exam, with paired English and Chinese explanations, clear examples, and focused revision tips.

栈和队列是 GCSE WJEC 计算机科学中最重要的两种抽象数据类型。它们用于按特定顺序管理数据，是许多现实计算过程的基础，从软件中的撤销功能到打印机假脱机。本文用中英双语对照讲解考试所需的所有知识点，包括清晰示例和针对性的复习技巧。

---

1. Introduction to Data Structures | 数据结构简介

A data structure is a way of organising and storing data so that it can be accessed and modified efficiently. Stacks and queues are linear data structures, meaning elements are arranged in a sequence. Unlike simple variables, these structures manage collections of items and define strict rules for adding and removing data.

数据结构是一种组织和存储数据的方式，以便高效地访问和修改数据。栈和队列是线性数据结构，即元素按顺序排列。与简单变量不同，这些结构管理项目集合，并对数据的添加和移除定义了严格的规则。

In the WJEC specification, you need to understand how stacks and queues work, how to apply their operations, and how to interpret algorithms that use them. You may be asked to trace code, draw diagrams of pointer movements, or explain the differences between static and dynamic implementations.

在 WJEC 考试大纲中，你需要理解栈和队列的工作原理、如何应用它们的操作以及如何解释使用它们的算法。你可能会遇到追踪代码、画出指针移动示意图或解释静态与动态实现之间的差异等题目。

---

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

A stack is an abstract data type that follows the Last In, First Out (LIFO) principle. Think of a stack of plates: you can only take the topmost plate off, and when you add a new plate, it goes on top. The last item placed on the stack is the first one to be removed.

栈是一种遵循后进先出（LIFO）原则的抽象数据类型。想象一叠盘子：你只能拿走最上面的盘子，而添加新盘子时，它被放在最上面。最后一个放入栈中的项目会最先被取出。

Stacks are widely used in computing. The call stack in programming languages keeps track of function calls, allowing the program to return to the correct place after a function finishes. Another example is the undo feature in text editors, where each action is pushed onto a stack and popped off when you want to reverse it.

栈在计算中被广泛使用。编程语言中的调用栈跟踪函数调用，使程序能够在函数完成后返回到正确的位置。另一个例子是文本编辑器中的撤销功能，每个操作都被压入栈中，当你想撤销时便弹出。

---

3. Stack Operations and LIFO Principle | 栈操作与后进先出原则

The two primary stack operations are push and pop. Push adds an item to the top of the stack. Pop removes and returns the top item. A third operation, peek or top, allows you to view the top element without removing it. All these operations work exclusively at one end of the structure.

栈的两个主要操作是压入（push）和弹出（pop）。Push 将一个项目添加到栈顶，Pop 移除并返回栈顶项目。第三个操作 peek 或 top 允许你查看栈顶元素而不移除它。所有这些操作都只在结构的一端进行。

When a push is performed, the stack pointer, often called top, is incremented to point to the next free space, and the data is stored there. When a pop occurs, the data at the top pointer is retrieved, and the pointer is decremented. It is crucial to check for stack overflow (when pushing to a full stack) and stack underflow (when popping from an empty stack).

执行 push 时，栈指针（通常称为 top）会递增指向下一个空闲空间，并将数据存储在那里。执行 pop 时，top 指针处的数据被取出，指针递减。检查栈溢出（当栈满时仍然 push）和栈下溢（当栈空时仍然 pop）至关重要。

---

4. Stack Implementation Using Arrays | 用数组实现栈

A common way to implement a stack is by using a one-dimensional array with a variable to track the top index. For a stack of maximum size n, the array indices run from 0 to n-1. Initially, the top pointer is set to -1 to indicate an empty stack.

实现栈的一种常见方法是使用一维数组和一个跟踪栈顶索引的变量。对于最大容量为 n 的栈，数组索引范围是 0 到 n-1。最初，top 指针设置为 -1 表示空栈。

When pushing: if top < n-1, increment top by 1 and store the item at array[top]; otherwise, report overflow. When popping: if top >= 0, retrieve array[top] and decrement top by 1; otherwise, report underflow. This static implementation has a fixed size, which can be a limitation if the number of items is unpredictable.

压入操作：如果 top < n-1，将 top 增加 1 并将项目存储在 array[top]；否则报告溢出。弹出操作：如果 top >= 0，取出 array[top] 并将 top 减 1；否则报告下溢。这种静态实现具有固定大小，如果项目数量不可预测，这可能是一个限制。

---

5. Applications of Stacks | 栈的应用

Stacks are used in many algorithms and system processes. In recursion, each recursive call adds a frame to the call stack; when the base case is reached, frames are popped in reverse order. Syntax parsing in compilers often uses stacks to check matching brackets and parentheses.

栈用于许多算法和系统进程中。在递归中，每次递归调用都会向调用栈添加一个帧；当达到基本情况时，帧按相反顺序弹出。编译器中的语法分析通常使用栈来检查匹配的括号和大括号。

Another classic application is evaluating arithmetic expressions in Reverse Polish Notation (RPN). Numbers are pushed onto a stack, and operators pop the required operands, perform the calculation, and push the result back. The browser back button is a simple everyday example: visited pages are pushed onto a stack, and pressing back pops the top page.

另一个经典应用是计算逆波兰表示法（RPN）的算术表达式。数字被压入栈中，运算符弹出所需的操作数，执行计算，并将结果压回栈中。浏览器后退按钮是一个简单的日常例子：访问过的页面被压入栈中，按下后退时弹出栈顶页面。

---

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

A queue is an abstract data type that follows the First In, First Out (FIFO) principle. Imagine a line of people waiting for a bus: the first person to join the line is the first to board. Items are added at the rear and removed from the front, so the oldest item is processed first.

队列是一种遵循先进先出（FIFO）原则的抽象数据类型。想象一队等公交车的人：最先加入队伍的人最先上车。项目在队尾添加，从队首移除，因此最早的项目最先被处理。

Queues are essential for managing tasks that must be handled in order of arrival, such as print jobs sent to a printer, keyboard buffers, and job scheduling in operating systems. They ensure fairness and predictability in processing sequences.

队列对于管理必须按到达顺序处理的任务至关重要，例如发送到打印机的打印作业、键盘缓冲区和操作系统中的作业调度。它们确保处理顺序的公平性和可预测性。

---

7. Queue Operations and FIFO Principle | 队列操作与先进先出原则

The two main queue operations are enqueue and dequeue. Enqueue adds an item to the rear of the queue. Dequeue removes and returns the item from the front. Like stacks, queues also have a front pointer and a rear pointer to manage the positions.

队列的两个主要操作是入队（enqueue）和出队（dequeue）。Enqueue 将一个项目添加到队尾，Dequeue 从队首移除并返回一个项目。与栈类似，队列也有一个 front 指针和一个 rear 指针来管理位置。

When an item is enqueued, the rear pointer advances; when dequeued, the front pointer advances. In a simple linear array implementation, after several operations both pointers may move towards the end of the array, leading to unused space at the beginning. This problem is solved by circular queues.

入队时，rear 指针向前移动；出队时，front 指针向前移动。在简单的线性数组实现中，经过若干次操作后，两个指针都可能向数组末端移动，导致开头有未使用的空间。这个问题可以通过循环队列解决。

---

8. Linear and Circular Queues | 线性队列与循环队列

A linear queue implemented with an array suffers from the problem of ‘stale’ space: even if the queue is logically empty, the front pointer may have advanced so far that no further enqueues are possible without resetting. This is wasteful and limits the effective capacity.

用数组实现的线性队列存在“陈旧”空间问题：即使逻辑上队列已空，front 指针可能已前移很远，导致无法再进行入队，除非重置。这很浪费，并限制了有效容量。

A circular queue treats the array as if it were a circle: when the rear pointer reaches the last index, it wraps around to index 0 if there is free space. This allows the full capacity of the array to be reused. The queue is full when (rear + 1) mod n equals front. The queue is empty when front equals rear (or front = -1 in some implementations).

循环队列将数组视为一个圆圈：当 rear 指针到达最后一个索引时，如果有空闲空间，它会环绕回到索引 0。这允许数组的全部容量被重复利用。当 (rear + 1) mod n 等于 front 时，队列已满。当 front 等于 rear（或在某些实现中 front = -1）时，队列为空。

---

9. Queue Implementation Using Arrays | 用数组实现队列

To implement a circular queue of size n, you need an array of n elements and two integers: front and rear. Initially, front and rear are both set to -1 or 0 depending on the convention. For enqueue: if the queue is not full, advance rear (wrapping around if necessary) and insert the item. If the queue was empty, set front to point to the first item.

要实现一个容量为 n 的循环队列，需要一个包含 n 个元素的数组和两个整数：front 和 rear。初始时，根据惯例，front 和 rear 都设置为 -1 或 0。入队操作：如果队列未满，移动 rear（必要时环绕）并插入项目。如果队列此前为空，则将 front 设置为指向第一个项目。

For dequeue: if the queue is not empty, remove the item at front and advance front (wrapping around if needed). If after dequeue the queue becomes empty, reset the pointers. Always check for overflow (enqueue on full) and underflow (dequeue on empty).

出队操作：如果队列不为空，移除 front 处的项目并移动 front（必要时环绕）。如果出队后队列变空，则重置指针。始终检查溢出（满队列入队）和下溢（空队列出队）。

---

10. Applications of Queues | 队列的应用

Queues appear wherever tasks must be processed in the order they arrive. Print spooling is a classic example: documents are enqueued as they are sent, and the printer dequeues them one by one. Keyboard buffers use queues to store key presses until the CPU can process them.

队列出现在必须按到达顺序处理任务的任何地方。打印假脱机是一个经典例子：文档在发送时入队，打印机逐个出队处理它们。键盘缓冲区使用队列存储按键，直到 CPU 能够处理它们。

In networking, routers use packet queues to manage data traffic. In simulation software, queues model real-world waiting lines, such as customers at a bank. Breadth-first search algorithms on graphs typically use a queue to manage the frontier of nodes to explore next.

在网络中，路由器使用数据包队列来管理数据流量。在仿真软件中，队列模拟现实世界的排队，例如银行里的顾客。图上广度优先搜索算法通常使用队列来管理待探索节点的边界。

---

11. Comparing Stacks and Queues | 栈与队列的比较

Understanding the fundamental differences helps you choose the right data structure for a problem. The table below summarises the contrasts:

了解基本差异有助于你为问题选择正确的数据结构。下表总结了对比：

Feature | 特征	Stack | 栈	Queue | 队列
Ordering principle | 排序原则	LIFO – Last In, First Out | 后进先出	FIFO – First In, First Out | 先进先出
Main operations | 主要操作	Push, Pop, Peek | 压入、弹出、查看	Enqueue, Dequeue | 入队、出队
Pointers used | 使用的指针	Top only | 仅 top	Front and rear | front 和 rear
Access point | 访问点	One end (top) | 一端（栈顶）	Front for removal, rear for insertion | 队首移除，队尾插入
Real-world analogy | 现实类比	Stack of plates | 一叠盘子	Queue at a bus stop | 公交站排队

Both structures are linear and can be implemented using arrays or linked lists. The choice depends on whether the problem requires processing the most recent item first (stack) or the oldest item first (queue).

两种结构都是线性的，可以用数组或链表实现。选择哪一种取决于问题要求先处理最新的项目（栈）还是最早的项目（队列）。

---

12. Exam Tips and Common Mistakes | 考试技巧与常见错误

When answering WJEC exam questions on stacks and queues, always show your pointer movements clearly. Diagrams can earn marks, so sketch the array and mark the top/front/rear pointers after each operation. Label everything carefully.

在回答 WJEC 考试中有关栈和队列的问题时，务必清晰地展示指针移动。图表可以得分，因此每次操作后画出数组并标记 top/front/rear 指针。仔细标注所有内容。

A common mistake is forgetting to check for overflow/underflow conditions. Always include a condition before push/pop or enqueue/dequeue. Another pitfall is confusing LIFO and FIFO; if a question says ‘the first item added is the first removed’, you must recognise a queue, not a stack.

一个常见错误是忘记检查溢出/下溢条件。在 push/pop 或 enqueue/dequeue 之前，务必包含条件判断。另一个陷阱是混淆 LIFO 和 FIFO；如果题目说“最先添加的项目最先移除”，你必须识别出这是队列而不是栈。

Practise tracing algorithms that use stacks or queues, such as RPN evaluation or breadth-first search. You may be given pseudocode and asked to determine the contents of the data structure after a series of operations. Work step by step and update the pointers methodically.

练习追踪使用栈或队列的算法，如 RPN 求值或广度优先搜索。你可能会遇到给出伪代码并要求判断一系列操作后数据结构内容的题目。逐步进行，有条不紊地更新指针。

Finally, revise the advantages and disadvantages of array-based implementations versus dynamic linked-list implementations, as a comparison question often appears in higher-tier papers.

最后，复习基于数组的实现与基于动态链表实现的优缺点，因为在高级卷中经常出现比较类问题。

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

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