📚 Stacks and Queues in IGCSE WJEC Computer Science | IGCSE WJEC 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) in computer science. They provide two different ways of organising and manipulating data, each following a strict rule for how elements are added and removed. Understanding their behaviour, implementation and real‑world applications is essential for the IGCSE WJEC Computer Science examination. This article systematically covers all key points you need to master.
栈与队列是计算机科学中基本的抽象数据类型（ADT）。它们提供了两种不同的数据组织和操作方式，各自遵循严格的元素添加与移除规则。理解它们的行为、实现方式和现实世界应用是拿下 IGCSE WJEC 计算机科学考试的关键。本文将系统梳理你需要掌握的全部考点。
1. Introduction to Abstract Data Types | 抽象数据类型简介
An abstract data type (ADT) defines a collection of data and the operations that can be performed on it, without specifying how the data is physically stored. The user only needs to know what the operations do, not how they are implemented. Stacks and queues are perfect examples of ADTs because they can be built using arrays or linked lists while offering the same interface.
抽象数据类型（ADT）定义了一组数据以及可以对其执行的操作，但不规定数据在物理上是如何存储的。使用者只需要知道各个操作的功能，而不必关心底层实现。栈与队列正是 ADT 的典型代表，因为它们既可以用数组实现，也可以用链表实现，却提供相同的操作接口。
2. What is a Stack? | 什么是栈？
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The element added most recently is the first one to be removed. You can imagine a stack of plates: you take the top plate first, and you add a new plate onto the top. In a stack, all insertions and deletions take place at one end, called the top.
栈是一种遵循后进先出（LIFO）原则的线性数据结构。最后添加的元素最先被移除。你可以将其想象成一摞盘子：你总是先拿最上面的盘子，新盘子也摞在最上面。在栈中，所有的插入和删除操作都在同一端进行，这一端称为栈顶。
The stack keeps track of the top element using a pointer or index. Any attempt to access data below the top requires first removing (popping) all elements above it. This restricted access makes stacks highly predictable and suitable for tasks that require reverse‑order processing.
栈通过指针或索引跟踪栈顶元素。如果想访问栈顶下方的数据，必须先将上方的所有元素弹出。这种受限的访问方式使得栈的行为高度可预测，非常适合需要逆向处理的任务。
3. Basic Stack Operations | 栈的基本操作
The core operations on a stack are:
栈的核心操作包括：
- push(item) – adds an item to the top of the stack. If the stack is already full, a stack overflow error occurs.
- push(元素) – 将一个元素加入栈顶。如果栈已满，则会引发栈上溢错误。
- pop() – removes and returns the item at the top. If the stack is empty, a stack underflow error occurs.
- pop() – 移除并返回栈顶元素。如果栈为空，则会引发栈下溢错误。
- peek() or top() – returns the top item without removing it. This does not change the stack.
- peek() 或 top() – 返回栈顶元素但不移除它，栈本身不发生改变。
- isEmpty() – checks whether the stack contains any elements; returns a Boolean value.
- isEmpty() – 检查栈中是否没有任何元素，返回布尔值。
- isFull() – (when using a fixed‑size array) checks whether the stack has reached its capacity.
- isFull() – （使用固定大小数组时）检查栈是否已达到容量上限。
In pseudocode, these operations are often defined around a variable top that points to the index of the current top element. For an array implementation with size MAX, top is initialised to -1 for an empty stack.
在伪代码中，这些操作通常围绕变量 top 展开，top 指向当前栈顶元素的索引。对于容量为 MAX 的数组实现，栈空时 top 初始化为 –1。
| Operation | Pseudocode Logic | 中文描述 |
|---|---|---|
| push(item) | IF top = MAX–1 THEN “overflow” ELSE top ← top + 1; stack[top] ← item | 若栈满则上溢，否则 top 加 1，存入元素 |
| pop() | IF top = -1 THEN “underflow” ELSE item ← stack[top]; top ← top – 1; RETURN item | 若栈空则下溢，否则取出栈顶元素，top 减 1，返回元素 |
| peek() | IF top = -1 THEN error ELSE RETURN stack[top] | 若栈空则报错，否则返回 stack[top] |
4. Implementing Stacks | 栈的实现方法
A stack can be implemented using a static array, a dynamic array or a linked list. In WJEC IGCSE, the static array implementation is most common. Here, a one‑dimensional array and an integer variable top work together. The stack grows from index 0 upward. The top pointer always holds the index of the most recently added element.
栈可以用静态数组、动态数组或链表实现。在 WJEC IGCSE 中，最常见的实现是静态数组。一个一维数组配合一个整型变量 top 即可工作。栈从索引 0 开始向上增长，top 指针始终保存最近添加元素的索引。
A linked‑list implementation avoids fixed‑size limitations and eliminates overflow conditions as long as memory is available. Each node contains data and a pointer to the node below it. The top pointer references the head node. Pushing inserts a new head; popping removes the head.
链表实现避免了固定大小的限制，只要有内存就不会出现上溢。每个节点包含数据和指向下方节点的指针。栈顶指针引用头节点。入栈插入新的头节点；出栈移除头节点。
Whichever implementation you choose, the abstract behaviour of push, pop and peek remains identical, which is precisely the power of an ADT.
无论选择哪种实现，push、pop 和 peek 的抽象行为都完全相同，这正是 ADT 的威力所在。
5. Applications of Stacks | 栈的实际应用
Stacks appear in many computing contexts. The call stack is one of the most important: when a function calls another function, the return address and local variables are pushed onto the call stack. When the function finishes, its frame is popped, and execution returns to the correct place. This mechanism naturally supports recursion.
栈出现在许多计算场景中。调用栈是最重要的例子之一：当一个函数调用另一个函数时，返回地址和局部变量被压入调用栈。函数执行完毕时，其栈帧被弹出，执行流程返回到正确的位置。这种机制天然地支持递归。
Other applications include undo operations in text editors (each action is pushed; undo pops the latest action), bracket matching in compilers (left brackets are pushed; right brackets cause a pop and check), and evaluating postfix expressions. In reverse Polish notation, operators follow their operands, and a stack elegantly evaluates the expression.
其他应用包括文本编辑器中的撤销操作（每步操作压栈，撤销时弹出最新操作）、编译器中的括号匹配检测（左括号压栈，遇到右括号时弹出并检查），以及后缀表达式求值。在逆波兰表示法中，操作符在操作数之后，栈可以优雅地完成求值。
For WJEC, you should be able to trace a simple algorithm that uses a stack, such as reversing a word or converting decimal to binary (repeated division by 2 pushes remainders; popping prints them in reverse order).
在 WJEC 考试中，你应当能够追踪使用栈的简单算法，例如反转单词或十进制转二进制（反复除以 2 将余数压栈，再依次弹出即可得到逆序二进制位）。
6. What is a Queue? | 什么是队列？
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The element added first is the first one to be removed, just like a line of people waiting for a bus: the person at the front boards first, and newcomers join at the rear. In a queue, insertions occur at the rear and deletions occur at the front.
队列是一种遵循先进先出（FIFO）原则的线性数据结构。最先添加的元素最先被移除，就如同排队等公交车：队伍最前面的人先上车，新来的人加入队尾。在队列中，插入操作在队尾进行，删除操作在队首进行。
Queues preserve the order of arrival, making them ideal for buffering and scheduling. Access is even more restricted than in a stack, as you cannot look at or remove elements in the middle without first processing everything ahead of them.
队列保留了到达的顺序，这使其成为缓冲和调度的理想选择。访问限制比栈更严格，因为你不能在不处理前面所有元素的情况下查看或移除中间的元素。
7. Queue Operations and Circular Queues | 队列操作与循环队列
The fundamental queue operations are:
队列的基本操作包括：
- enqueue(item) – adds an item to the rear of the queue. If the queue is full, an overflow error occurs.
- enqueue(元素) – 将一个元素加入队尾。若队列已满，则发生上溢错误。
- dequeue() – removes and returns the item at the front. If the queue is empty, an underflow error occurs.
- dequeue() – 移除并返回队首元素。若队列为空，则发生下溢错误。
- front() or peek() – returns the front item without removing it.
- front() 或 peek() – 返回队首元素但不移除。
- isEmpty() – checks whether the queue has no elements.
- isEmpty() – 检查队列是否为空。
- isFull() – checks whether the queue has reached its maximum capacity.
- isFull() – 检查队列是否已满。
When a queue is implemented with a simple linear array, dequeue operations cause the front index to move forward, leaving unused spaces behind. Eventually the rear reaches the end of the array while the front has moved far ahead, giving a false impression of fullness. This wasteful situation is solved by a circular queue, where the array is treated as if it loops around. The rear pointer wraps to position 0 after reaching MAX–1, provided free slots exist.
用简单的线性数组实现队列时，dequeue 操作会导致 front 指针前移，留下未使用的空间。最终 rear 抵达数组末尾，而 front 已大幅前移，造成“假满”错觉。循环队列解决了这种浪费：数组被视作环形结构，当 rear 到达 MAX–1 后若前方有空闲位置，则绕回到索引 0 继续使用。
In a circular queue, the condition for full is often (rear + 1) MOD MAX = front, which means one slot is deliberately left unused to distinguish full from empty. Empty is defined as front = rear.
在循环队列中，队满的常用判定是（rear + 1）MOD MAX = front，即故意留出一个空位以区分满和空。队空则定义为 front = rear。
8. Implementing Queues | 队列的实现
Like stacks, queues can be built using arrays or linked lists. A linear array approach uses two pointers, front and rear. Initially front = 0 and rear = –1. When enqueuing, rear increments; when dequeuing, front increments. After many operations, items may only occupy a middle segment, and front may be greater than rear, which makes the queue appear empty even if items exist. This is why WJEC strongly emphasises the circular array method.
与栈类似，队列可以用数组或链表实现。线性数组方法使用两个指针：front 和 rear。初始时 front = 0，rear = –1。入队时 rear 加 1；出队时 front 加 1。多次操作后，元素可能只占据中间一段，front 甚至大于 rear，出现明明有元素却显示为空的混乱现象。因此 WJEC 非常强调循环数组的方法。
A linked‑list implementation of a queue uses two external references: head (front) and tail (rear). Enqueue adds a node at the tail; dequeue removes the head node. This naturally avoids overflow as long as memory permits and does not require wraparound logic. However, you must be careful to update both references when the queue becomes empty.
队列的链表实现使用两个外部引用：head（队首）和 tail（队尾）。入队在 tail 处添加节点；出队移除 head 节点。只要内存允许就不会溢出，且无需绕回逻辑。但要注意，当队列变为空时，必须同时更新两个引用。
9. Applications of Queues | 队列的应用
Queues are everywhere in computing. A printer spooler holds print jobs in a queue, processing them in the order they were submitted. Keyboard buffers store key presses in a queue so that fast typing is not lost, even if the CPU is busy. Operating systems use queues for task scheduling, placing processes in a ready queue to share CPU time fairly.
队列在计算中无处不在。打印机假脱机程序将打印作业放入队列，按提交顺序处理。键盘缓冲区将按键存入队列，即使 CPU 忙碌也不会丢失快速键入的内容。操作系统使用队列进行任务调度，将进程放入就绪队列以公平分配 CPU 时间。
In simulations, queues model real‑world lines such as customers at a checkout or cars at a toll plaza. Breadth‑first search algorithms in graphs also rely on a queue to explore nodes level by level. For WJEC, you may be asked to explain how a circular queue could be used to manage a small fixed buffer, such as streaming data between a producer and a consumer.
在模拟中，队列用来建模现实中的排队场景，如收银台前的顾客或收费站前的车辆。图的广度优先搜索算法也依赖队列逐层探索节点。在 WJEC 考试中，你可能会被要求解释如何用循环队列管理一个小的固定缓冲区，例如在生产者和消费者之间传输数据流。
10. Comparing Stacks and Queues | 栈与队列对比
| Aspect | Stack | Queue | 中文对比 |
|---|---|---|---|
| Ordering principle | LIFO (Last In, First Out) | FIFO (First In, First Out) | 栈：后进先出；队列：先进先出 |
| Insertion point | Top | Rear | 栈在栈顶，队列在队尾 |
| Deletion point | Top | Front | 栈也在栈顶；队列在队首 |
| Key variables | top pointer | front and rear pointers | 一个指针 vs 两个指针 |
| Overflow condition | top = MAX – 1 | (rear + 1) MOD MAX = front (circular) | 不同判定方法 |
| Typical use case | Reverse order, backtracking | Ordered processing, buffering | 逆向处理 vs 顺序缓冲 |
Both structures store linear collections, but their access policies make them suited to completely different problems. Choosing the right ADT is a key design skill that WJEC examiners love to test.
两者都存储线性集合，但存取策略的差异使它们分别适用于截然不同的问题。选择合适的 ADT 是一项关键的设计能力，也是 WJEC 考官喜欢考查的。
11. Exam Tips and Common Pitfalls | 考点与常见错误
Candidates often lose marks by confusing overflow and underflow conditions or by forgetting that pop and dequeue remove items permanently. When tracing an algorithm, draw a diagram of the stack or queue after each step. Label the pointer(s) clearly and show the values stored. Never assume that top automatically updates itself: you must write out the increment or decrement explicitly.
考生常因混淆上溢与下溢条件、或忘记 pop/dequeue 会永久移除元素而丢分。在追踪算法时，请逐步绘制栈或队列的示意图。清晰标出指针并显示存储的数值。绝不要假设 top 会自动更新，必须明确写出递增或递减步骤。
In circular queue problems, many students calculate the wrapped index incorrectly. Remember to use modulo arithmetic: newRear ← (rear + 1) MOD MAX. Also, read the question carefully: if the array size is given as N and one slot is reserved, the effective capacity is N – 1. Watch out for descriptions like “a queue of size 5 implemented with a 5‑element array” – this often implies a 4‑item capacity.
在循环队列问题中，许多学生错误计算绕回索引。记住使用模运算：newRear ← (rear + 1) MOD MAX。此外，仔细读题：若数组大小为 N 且需保留一个空位，则有效容量为 N – 1。注意类似“使用 5 元素数组实现大小为 5 的队列”的描述——这通常意味着仅可容纳 4 个元素。
Be prepared to compare stacks and queues in a short written question. Use precise terminology: LIFO, FIFO, top, front, rear. Support your answer with a real‑world analogy, such as a PEZ dispenser for a stack and a supermarket checkout for a queue. Marks are often allocated for correct use of technical vocabulary.
做好在简答题中比较栈和队列的准备。使用准确术语：LIFO、FIFO、top、front、rear。用现实生活中的类比支持你的回答，比如用 PEZ 糖果盒比喻栈，用超市收银台比喻队列。正确使用技术词汇通常有额外得分。
12. Summary | 总结
Stacks and queues are simple yet powerful abstract data types. A stack enforces LIFO access with operations push, pop and peek, driven by a single top pointer. It excels at reversing order and is the hidden engine behind recursion and undo features. A queue enforces FIFO access with enqueue and dequeue, using both front and rear pointers. Its circular variant prevents wasted space, making it perfect for buffering and scheduling tasks.
栈与队列都是简单而强大的抽象数据类型。栈通过 push、pop 和 peek 操作实施 LIFO 访问规则，依靠一个 top 指针驱动。它擅长颠倒顺序，是递归和撤销功能背后的隐藏引擎。队列通过 enqueue 和 dequeue 实施 FIFO 访问规则，同时使用 front 和 rear 指针。其循环变体避免了空间浪费，完美适配缓冲和调度任务。
By mastering their definitions, operations, implementations and applications, you will confidently answer any WJEC question on this topic. Draw diagrams to trace algorithms, always check boundary conditions, and remember the key principle that distinguishes them: stack is LIFO; queue is FIFO.
掌握了它们的定义、操作、实现和应用，你便能自信地回答任何 WJEC 与此相关的题目。多画图追踪算法，务必检查边界条件，并牢记两者的核心区别：栈是后进先出，队列是先进先出。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导