Stacks and Queues in IGCSE Computer Science | IGCSE 计算机：栈与队列考点精讲

📚 Stacks and Queues in IGCSE Computer Science | IGCSE 计算机：栈与队列考点精讲

Stacks and queues are fundamental abstract data types that appear in almost every IGCSE Computer Science syllabus. Understanding their behaviour, operations and applications is essential for both the theory paper and problem-solving questions. This revision guide breaks down the key points you need to master, from LIFO and FIFO principles to array implementations and exam-style tracing.

栈和队列是几乎每个 IGCSE 计算机科学大纲中都会出现的基础抽象数据类型。理解它们的行为、操作和应用，对于理论卷和问题求解题都至关重要。本复习指南为你梳理了必须掌握的核心要点，从 LIFO 与 FIFO 原则到数组实现以及考试风格的追溯题，一应俱全。

1. 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: the last plate placed on top is the first one to be taken off. Only the top element is accessible at any time. Stacks can store any data type, but for IGCSE we usually work with integers or strings.

栈是一种遵循后进先出（LIFO）原则的抽象数据类型。想象一摞盘子：最后放在上面的盘子，会最先被拿走。任何时候只能访问栈顶元素。栈可以存储任何数据类型，但在 IGCSE 中，我们通常处理整数或字符串。

2. Stack Operations | 栈操作

The three essential stack operations are Push, Pop and Peek. Push adds an item onto the top of the stack. Pop removes and returns the top item. Peek (or Top) returns the top item without removing it. An additional operation, IsEmpty, checks whether the stack contains any elements. Trying to Pop or Peek from an empty stack causes an underflow error; pushing onto a full stack (when using a fixed-size array) causes an overflow error.

栈有三个基本操作：Push（入栈）、Pop（出栈）和 Peek（查看栈顶）。Push 将一项添加到栈顶。Pop 移除并返回栈顶项。Peek（或称 Top）返回栈顶项而不移除它。还有一个辅助操作 IsEmpty，用于检查栈是否为空。尝试对空栈执行 Pop 或 Peek 会导致下溢错误；当使用固定大小数组时，向已满的栈执行 Push 会导致上溢错误。

Push(item) – adds item to the top
Pop() – removes and returns the top item
Peek() – returns the top item without removing it
IsEmpty() – returns true if stack is empty
IsFull() – returns true if stack has reached maximum capacity

Push(项) – 将项添加到栈顶
Pop() – 移除并返回栈顶项
Peek() – 返回栈顶项但不移除
IsEmpty() – 若栈为空则返回真
IsFull() – 若栈已达到最大容量则返回真

3. Implementing a Stack with an Array | 用数组实现栈

At IGCSE level, stacks are often implemented using a 1D array and a variable holding the top pointer. Initially, top is set to -1 to indicate an empty stack. When an item is pushed, top increments and the value is stored at array[top]. When an item is popped, the value at array[top] is returned and top decrements. The stack is full when top equals the last index of the array.

在 IGCSE 阶段，栈通常用一个一维数组和一个存放栈顶指针的变量来实现。初始时，top 设为 -1 表示空栈。当入栈一个项时，top 加 1，值存入 array[top]。出栈时，返回 array[top] 的值，并将 top 减 1。当 top 等于数组最后一个索引时，栈为满。

Example pseudocode for Push given an array Stack[0..Max-1] and Top:

给定数组 Stack[0..Max-1] 和 Top 的 Push 伪代码示例：

IF Top = Max – 1 THEN
  OUTPUT “Stack overflow”
ELSE
  Top ← Top + 1
  Stack[Top] ← Item
ENDIF

4. Stack Applications | 栈的应用

Stacks are used in many real-world computing scenarios. Function call management uses a call stack to remember return addresses; the most recently called function returns first. Backtracking algorithms, such as navigating a maze, rely on stacks. The undo feature in software keeps previous states on a stack. Expression evaluation, especially postfix notation, also uses stacks. For IGCSE, you should be able to suggest a stack when a problem requires reversing order or tracking nested structures.

栈在许多实际计算场景中都有应用。函数调用管理使用调用栈来记住返回地址；最近调用的函数最先返回。回溯算法（如迷宫导航）依赖栈。软件中的撤销功能将之前的状态保留在栈中。表达式求值（尤其是后缀表示法）也使用栈。对于 IGCSE，当问题需要反转顺序或跟踪嵌套结构时，你应能想到使用栈。

5. Tracing Stacks in Exam Questions | 考试中的栈追溯题

Tracing questions ask you to show the state of a stack after a series of operations. Draw a vertical table with the operation, the value of top, and the array contents. Always initialise top to -1. For each Push, increase top and write the item at that index. For each Pop, record the returned value, then decrease top. Be careful with overwriting: when a new value is pushed onto an index that previously held data, the old data is conceptually erased.

追溯题要求你展示经过一系列操作后栈的状态。绘制一个垂直表格，包含操作、top 的值以及数组内容。始终将 top 初始化为 -1。每次 Push，top 加 1，并在该索引处写入项。每次 Pop，记录返回的值，然后将 top 减 1。注意覆盖：当新值被推入之前存有数据的索引时，旧数据在概念上被擦除。

Example: Push(5), Push(3), Pop(), Push(8)
Top after each: -1 → 0 → 1 → 0 → 1
Array: [5, 3, …] → [5, 8, …]

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

A queue is an abstract data type based on the First In, First Out (FIFO) principle. The item that has been in the queue the longest is the first to be removed, just like people waiting in a line. Elements are added at the rear and removed from the front. Only the front element can be accessed directly.

队列是一种基于先进先出（FIFO）原则的抽象数据类型。在队列中停留时间最长的项最先被移除，就像人们排队等候一样。元素在队尾添加，从队首移除。只能直接访问队首元素。

7. Queue Operations | 队列操作

The main queue operations are Enqueue and Dequeue. Enqueue adds an item to the rear of the queue; Dequeue removes and returns the item at the front. A Peek at the front item is sometimes required. Additional checks include IsEmpty and IsFull. Dequeuing from an empty queue causes underflow; enqueuing onto a full queue causes overflow. A queue may also provide a Size function to return the number of elements currently stored.

队列的主要操作是 Enqueue（入队）和 Dequeue（出队）。Enqueue 将一个项添加到队尾；Dequeue 移除并返回队首的项。有时需要 Peek 查看队首项。辅助检查包括 IsEmpty 和 IsFull。对空队列执行 Dequeue 会导致下溢；对满队列执行 Enqueue 会导致上溢。队列还可能提供 Size 函数来返回当前存储的元素数量。

Enqueue(item) – adds item to the rear
Dequeue() – removes and returns the front item
Peek() – returns the front item without removing it
IsEmpty() – returns true if queue is empty
IsFull() – returns true if queue is full

Enqueue(项) – 将项添加到队尾
Dequeue() – 移除并返回队首项
Peek() – 返回队首项但不移除
IsEmpty() – 若队列为空则返回真
IsFull() – 若队列满则返回真

8. Implementing a Queue with an Array | 用数组实现队列

A simple queue uses a 1D array and two pointers: Front and Rear. Initially Front is set to 0 and Rear to -1. Enqueue increments Rear and stores the item at array[Rear]. Dequeue returns array[Front] and increments Front. However, this linear approach wastes space because as items are removed, the unused positions at the beginning of the array cannot be reused. IGCSE often asks you to identify this drawback and suggest a circular queue as a solution.

简单队列使用一维数组和两个指针：Front 和 Rear。初始时 Front 设为 0，Rear 设为 -1。Enqueue 将 Rear 加 1 并在 array[Rear] 处存储项。Dequeue 返回 array[Front] 并将 Front 加 1。然而，这种线性方法会浪费空间，因为随着项被移除，数组开头未使用的位置无法被重用。IGCSE 经常要求你指出这一缺点，并提出循环队列作为解决方案。

9. Circular Queues | 循环队列

A circular queue treats the array as if it wraps around. When the Rear pointer reaches the end of the array, the next Enqueue moves Rear to index 0, provided that slot is free. This allows the queue to reuse spaces emptied by Dequeue. Both Front and Rear move in a circular fashion. The queue is full when there is one empty space between Front and Rear (or when (Rear + 1) mod Max = Front). The queue is empty when Front = Rear (depending on convention; many IGCSE texts use Front = -1 for empty). Tracing circular queues requires careful tracking of pointers modulo the array size.

循环队列将数组视为首尾相接。当 Rear 指针到达数组末尾时，下一个 Enqueue 会将 Rear 移动到索引 0，前提是该位置空闲。这使得队列能够重用 Dequeue 腾出的空间。Front 和 Rear 均以循环方式移动。当 Front 和 Rear 之间只有一个空位（或 (Rear + 1) mod Max = Front）时，队列为满。当 Front = Rear 时，队列为空（取决于约定；许多 IGCSE 教材用 Front = -1 表示空）。追踪循环队列需要谨慎地按数组大小取模来跟踪指针。

Enqueue in circular queue of size Max:
IF (Rear + 1) MOD Max = Front THEN
  OUTPUT “Queue full”
ELSE
  IF Front = -1 THEN Front ← 0
  Rear ← (Rear + 1) MOD Max
  Queue[Rear] ← Item
ENDIF

10. Queue Applications | 队列的应用

Queues appear wherever tasks must be processed in order of arrival. Operating system job scheduling uses queues to manage print spooling, CPU process scheduling and disk I/O requests. In simulation, queues model real-life waiting lines, such as customers at a bank or cars at a toll booth. Breadth-first search in graph algorithms relies on a queue. Keyboard buffers store keystrokes in a queue before the CPU processes them. In exams, you should recognise that when fairness or order preservation is required, a queue is the appropriate choice.

只要任务必须按到达顺序处理，就会用到队列。操作系统作业调度使用队列来管理打印后台、CPU 进程调度和磁盘 I/O 请求。在模拟中，队列用来建模现实中的等待线，如银行顾客或收费站车辆。图算法中的广度优先搜索依赖队列。键盘缓冲区在 CPU 处理击键之前用队列存储它们。在考试中，当需要公平性或保持顺序时，你应当认识到队列是合适的选择。

11. Stacks vs Queues – Key Comparison | 栈与队列对比要点

Stack follows LIFO; Queue follows FIFO. Stack has one access point (top); Queue has two (front and rear). Stack is good for reversing and backtracking; Queue is good for ordering and buffering. In terms of implementation, both can be built with arrays or linked lists. However, with arrays, a stack requires only one pointer, while a queue needs two (and often benefits from a circular design).

栈遵循 LIFO；队列遵循 FIFO。栈只有一个访问点（栈顶）；队列有两个（队首和队尾）。栈擅长反转和回溯；队列擅长排序和缓冲。在实现方面，两者都可用数组或链表构建。然而，使用数组时，栈只需要一个指针，而队列需要两个（并且通常采用循环设计更佳）。

Feature	Stack	Queue
Principle	LIFO (Last In, First Out)	FIFO (First In, First Out)
Insertion point	Top	Rear
Removal point	Top	Front
Number of pointers	1 (Top)	2 (Front, Rear)
Common uses	Undo, recursion, parsing	Print queue, CPU scheduling, BFS

12. Common Exam Pitfalls and Tips | 常见考试陷阱与提示

Many candidates forget to initialise pointers correctly; Top should start at -1, Front at 0 and Rear at -1 (or Front at -1 for circular). Mixing up overflow and underflow is another common error: overflow is full, underflow is empty. When tracing, always update pointers before storing or after retrieving, exactly as described in the pseudocode. Be precise about indices: ‘array[Top]’ is the top element, not ‘array[Top+1]’. For queue questions, check whether the question specifies a circular or linear queue, as tracing differs. Finally, in high-mark questions that ask you to compare or choose a data structure, always justify your choice by referring to LIFO/FIFO behaviour and the requirements of the scenario.

许多考生忘记正确初始化指针；Top 应从 -1 开始，Front 应从 0 开始，Rear 从 -1 开始（循环队列中 Front 可能从 -1 开始）。混淆上溢和下溢是另一个常见错误：上溢表示满，下溢表示空。在追溯时，务必按照伪代码所述，在存储之前或检索之后更新指针。对索引要精确：“array[Top]” 是栈顶元素，而不是 “array[Top+1]”。对于队列题，要检查题目明确指定的是循环队列还是线性队列，因为追溯方式不同。最后，在要求比较或选择数据结构的高分题中，始终通过引用 LIFO/FIFO 行为以及场景需求来证明你的选择。

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

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

Stacks and Queues in IGCSE Computer Science | IGCSE 计算机：栈与队列 考点精讲