📚 Stacks and Queues: Key Points for CIE IGCSE Computer Science | 栈与队列：CIE IGCSE 计算机科学考点精讲
A stack and a queue are two fundamental abstract data types in computer science. They both store collections of elements, but they differ in the order in which elements are accessed and removed. Mastering these structures is essential for CIE IGCSE Computer Science, as they frequently appear in theory and algorithm questions. This article breaks down every key concept, operation, and application to help you answer exam questions with confidence.
栈和队列是计算机科学中两种基本的抽象数据类型。它们都用于存储元素的集合，但元素被访问和移除的顺序不同。掌握这些结构对 CIE IGCSE 计算机科学至关重要，因为它们经常出现在理论和算法题中。本文将逐一解析每个核心概念、操作和应用，帮助你自信应对考试题目。
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 abstract data types (ADTs) because they define behaviour (operations) independently of how they are implemented.
数据结构是一种组织和存储数据的方式，以便能够高效地访问和修改数据。栈和队列属于抽象数据类型(ADT)，因为它们定义的行为（操作）与其实现方式相互独立。
In the CIE syllabus, you need to understand how stacks and queues work logically, how they can be implemented using arrays or linked lists, and when to apply them in problem-solving. The focus is on the principle of restricted access: a stack only allows access to the top element, while a queue allows access to the front and back.
在 CIE 考纲中，你需要理解栈和队列在逻辑上是如何工作的，它们如何用数组或链表来实现，以及何时在解决问题时应用它们。重点是受限访问的原则：栈只允许访问栈顶元素，而队列允许访问队首和队尾。
2. Stack Basics: LIFO Principle | 栈基础：后进先出原则
A stack follows the Last-In-First-Out (LIFO) principle: the most recently added element is the first one to be removed. You can think of a stack like a pile of plates—you add clean plates to the top, and when you need a plate, you take from the top.
栈遵循后进先出 (LIFO) 原则：最近添加的元素最先被移除。你可以把栈想象成一摞盘子——你往顶端加上干净的盘子，需要用盘子时也从顶端取走。
The top of the stack is the only accessible position. Any attempt to remove an element from an empty stack causes an underflow error, while trying to add an element to a full stack (in a fixed-size implementation) causes an overflow error. These error conditions are important in exam scenarios.
栈顶是唯一可访问的位置。尝试从空栈中移除元素会导致下溢错误，而试图向已满的栈（在固定大小的实现中）添加元素则会导致上溢错误。这些错误条件在考试情境中非常重要。
- Key term: Stack Pointer – a variable that keeps track of the index of the top element (often -1 when empty).
- 关键术语： 栈指针 —— 一个跟踪栈顶元素索引的变量（栈为空时通常为 -1）。
3. Stack Operations: Push, Pop, Peek | 栈操作：入栈、出栈、查看栈顶
The three essential stack operations are push, pop, and peek (or top). Push adds an element to the top of the stack; pop removes and returns the top element; peek returns the top element without removing it.
栈的三个基本操作是入栈 (push)、出栈 (pop) 和查看栈顶 (peek 或 top)。入栈将一个元素添加到栈顶；出栈移除并返回栈顶元素；查看栈顶返回栈顶元素但不将其移除。
Let’s illustrate with a stack of integers. Starting with an empty stack, you push 5, push 8, push 3. The stack now contains [5, 8, 3] with 3 on top. A pop operation returns 3, leaving [5, 8]. A peek returns 8 without changing the stack.
我们用一个整数栈来演示。从一个空栈开始，你依次入栈 5、8、3。现在栈包含 [5, 8, 3]，栈顶是 3。一次出栈操作返回 3，栈中剩下 [5, 8]。一次查看操作返回 8，但不改变栈的内容。
In pseudocode, a push on an array implementation would involve incrementing the stack pointer and storing the new value at that position. A pop would retrieve the value at the stack pointer and then decrement the pointer. Always check for underflow/overflow before performing an operation.
在伪代码中，数组实现下的入栈操作会递增栈指针，并将新值存入该位置。出栈操作会取出栈指针指向的值，然后递减栈指针。执行操作前务必检查是否下溢或上溢。
4. Stack Implementation: Arrays vs Linked Lists | 栈的实现：数组与链表
Stacks can be implemented using either arrays or linked lists. An array-based stack has a fixed maximum size, making it memory efficient but prone to overflow if the capacity is exceeded. The stack pointer is simply an integer index.
栈可以用数组或链表来实现。基于数组的栈有固定的最大容量，内存使用效率高，但如果超出容量就容易发生上溢。栈指针只是一个整数下标。
A linked-list-based stack is dynamic, growing and shrinking as needed, so it avoids overflow (apart from running out of system memory). Each node holds a data value and a pointer to the node below it. The top of the stack is the head of the list, and there is no need for a separate stack pointer index.
基于链表的栈是动态的，可按需增长和收缩，因此避免了上溢（除了系统内存耗尽的情况）。每个节点包含一个数据值和一个指向下方节点的指针。栈顶就是链表的头节点，无需单独的栈指针下标。
In exams, you may be asked to trace a stack’s state after a series of operations using either implementation. Familiarity with both approaches helps you understand the underlying mechanics.
在考试中，你可能需要追踪一系列操作后栈的状态，无论是采用哪种实现方式。熟悉这两种方式有助于你理解底层机制。
| Feature | 特性 | Array-based Stack | 数组栈 | Linked-list Stack | 链表栈 |
|---|---|---|
| Size | 大小 | Fixed at creation | 创建时固定 | Dynamic, no preset limit | 动态，无预设限制 |
| Memory | 内存 | Wasted if not full | 未满时有浪费 | Extra memory for pointers | 需要额外空间存放指针 |
| Overflow | 上溢 | Possible | 可能发生 | Only if heap memory exhausted | 仅在堆内存耗尽时 |
5. Applications of Stacks | 栈的应用
Stacks are used whenever a LIFO order is required. Common examples include the undo feature in text editors, managing back and forward in web browsers, evaluating arithmetic expressions (postfix notation), and managing function calls in recursion (call stack).
每当需要后进先出顺序时，就使用栈。常见的例子包括文本编辑器中的撤销功能、网页浏览器中的后退和前进管理、算术表达式求值（后缀表示法），以及递归中函数调用的管理（调用栈）。
Reverse Polish Notation (RPN) evaluation: operands are pushed onto a stack; when an operator is encountered, the required number of operands are popped, the operator is applied, and the result is pushed back. This is a classic exam topic.
逆波兰表示法 (RPN) 求值：操作数被压入栈中；当遇到运算符时，弹出所需数量的操作数，应用运算符，然后将结果压回栈中。这是一个经典的考试主题。
Balanced parentheses checking: push opening brackets; when a closing bracket is read, pop and check if it matches. If the stack is empty at the end and all matches succeed, the expression is balanced.
括号匹配检查：遇到开括号时压入栈；遇到闭括号时，弹出栈顶元素并检查是否匹配。若最后栈为空且所有匹配均成功，则表达式括号平衡。
6. Queue Basics: FIFO Principle | 队列基础：先进先出原则
A queue follows the First-In-First-Out (FIFO) principle: elements are added at the rear (back) and removed from the front. Just like a line of people waiting for a bus, the person who arrives first is served first.
队列遵循先进先出 (FIFO) 原则：元素在队尾（后端）添加，并从队首（前端）移除。就像排队等公交的人一样，最先到达的人最先获得服务。
Queues have two pointers: a front pointer and a rear pointer. The front points to the next element to be removed, and the rear points to the last added element. In a linear array implementation, as items are removed, the front moves forward, leading to unused space at the start.
队列有两个指针：队首指针和队尾指针。队首指向下一个待移除的元素，队尾指向最后添加的元素。在线性数组实现中，随着元素被移除，队首指针向前移动，导致起始位置出现未使用的空间。
7. Queue Operations: Enqueue, Dequeue, Peek | 队列操作：入队、出队、查看队首
The fundamental operations are enqueue (add to rear), dequeue (remove from front), and peek (return front element without removing). If the queue is empty, a dequeue causes an underflow error.
基本操作是入队（添加到队尾）、出队（从队首移除）和查看队首（返回队首元素但不移除）。如果队列为空，出队操作会导致下溢错误。
Suppose a queue initially empty: enqueue(10), enqueue(20), enqueue(30). The front is 10, rear is 30. After dequeue, 10 is removed, front moves to 20. The queue becomes [20, 30]. A peek would return 20.
假设一个空队列：依次入队 10、20、30。队首是 10，队尾是 30。出队后，10 被移除，队首移动到 20。队列变为 [20, 30]。查看队首操作返回 20。
It’s crucial to update pointers correctly. In an array, after dequeue, if the front pointer overtakes the rear pointer, the queue becomes empty; both pointers are often reset to 0 or -1 depending on the implementation.
正确更新指针至关重要。在数组中，出队后如果队首指针超过了队尾指针，队列变为空；根据实现方式，两个指针通常会重置为 0 或 -1。
8. Types of Queues: Linear, Circular, Priority | 队列类型：线性、循环、优先级
A linear queue is the simplest form, but it suffers from wasted space when elements are removed. A circular queue solves this by allowing the rear pointer to wrap around to the beginning of the array, reusing vacant slots.
线性队列是最简单的形式，但当元素被移除时会出现空间浪费。循环队列解决了这个问题，它允许队尾指针绕回到数组开头，重新利用空闲的槽位。
In a circular queue, both front and rear move in a circle. A full circular queue is often identified when (rear + 1) % size == front, leaving one empty slot to distinguish between full and empty states. This is a common exam question.
在循环队列中，队首和队尾指针循环移动。判断循环队满的常用条件是 (rear + 1) % size == front，保留一个空槽以区分满和空的状态。这是一道常见的考试题。
A priority queue assigns a priority to each element. The element with the highest priority is dequeued first, regardless of its arrival order. It can be implemented using a heap or sorted linked list. CIE IGCSE may ask you to describe its behaviour, not its full implementation.
优先级队列为每个元素分配一个优先级。优先级最高的元素最先出队，无论其到达顺序如何。它可以用堆或有序链表来实现。CIE IGCSE 可能要求你描述其行为，而非完整的实现。
9. Queue Implementation: Arrays vs Linked Lists | 队列的实现：数组与链表
An array-based queue (linear) is simple to understand but requires shifting elements or dealing with unused space. A circular array queue avoids shifting and makes the implementation more efficient.
基于数组的队列（线性）易于理解，但需要移动元素或处理未使用的空间。循环数组队列避免了移动元素，使实现更加高效。
A linked-list queue uses a head pointer (front) and a tail pointer (rear). Enqueue adds a new node at the tail; dequeue removes the head node. There is no wasted space, and the size can grow as needed, but each node requires extra memory for the pointer.
基于链表的队列使用头指针（队首）和尾指针（队尾）。入队在尾节点之后添加新节点；出队移除头节点。没有空间浪费，大小可按需增长，但每个节点需要额外内存存放指针。
The choice of implementation depends on the context. For fixed-size buffering tasks (e.g., keyboard buffer) a circular array is often preferred. For unpredictable sizes, a linked-list queue is more flexible.
实现方式的选择取决于具体情境。对于固定大小的缓冲任务（例如键盘缓冲区），通常首选循环数组。对于大小不可预测的情况，链表队列更灵活。
10. Applications of Queues | 队列的应用
Queues are ubiquitous in computer systems. They manage print jobs in a printer spooler, process scheduling in operating systems, handling requests in web servers, and buffering data streams (e.g., keyboard input, network packets).
队列在计算机系统中无处不在。它们用于管理打印假脱机程序中的打印作业、操作系统中的进程调度、网络服务器中的请求处理，以及缓冲数据流（如键盘输入、网络数据包）。
In simulations, queues model real-world waiting lines, such as customers at a bank or cars at a traffic light. Breadth-first search (BFS) in graphs uses a queue to explore nodes level by level. These contexts illustrate the FIFO nature.
在模拟中，队列用于对现实世界的排队线进行建模，例如银行中的顾客或交通灯前的车辆。图中的广度优先搜索 (BFS) 使用队列逐层探索节点。这些场景充分体现了 FIFO 特性。
For IGCSE, be ready to describe how a queue is used in a given scenario and to trace simple queue operations. You might be given pseudocode and asked to identify the result of enqueue/dequeue sequences.
对于 IGCSE，要准备好描述队列在特定场景中的用法，并追踪简单的队列操作。你可能会被提供伪代码，并要求识别一系列入队/出队操作的结果。
11. Comparison of Stacks and Queues | 栈与队列的比较
| Aspect | 方面 | Stack | 栈 | Queue | 队列 |
|---|---|---|
| Principle | 原理 | LIFO (Last-In-First-Out) | 后进先出 | FIFO (First-In-First-Out) | 先进先出 |
| Insertion point | 插入点 | Top of stack | 栈顶 | Rear (tail) of queue | 队尾 |
| Removal point | 移除点 | Top of stack | 栈顶 | Front (head) of queue | 队首 |
| Typical uses | 典型用途 | Undo, back buttons, recursion, expression evaluation | 撤销、后退按钮、递归、表达式求值 | Print queues, BFS, buffering, process scheduling | 打印队列、BFS、缓冲、进程调度 |
Understanding the difference is straightforward if you remember: stacks are vertical (think of a stack of books), queues are horizontal (a line). Both restrict access, but the point of restriction differs.
如果记住以下比喻，理解两者的区别很容易：栈是垂直的（想象一摞书），队列是水平的（排队）。两者都限制访问，但限制的位置不同。
12. Exam Tips and Common Mistakes | 考试技巧与常见错误
Always read the question carefully to determine if you need to draw a diagram showing pointer positions. If tracing, show each step and the state of the data structure after each operation. Label stack/queue pointers clearly.
务必仔细审题，确定是否需要绘制显示指针位置的示意图。如果需要追踪，须展示每一步操作后数据结构的状态。清晰标注栈或队列指针。
Common mistakes: forgetting to check for underflow before a pop/dequeue operation; confusing LIFO and FIFO in explanations; failing to update the rear pointer correctly in an enqueue; and misidentifying the top or front element.
常见错误：出栈/出队操作前忘记检查下溢；在解释中混淆 LIFO 和 FIFO；入队时未能正确更新队尾指针；以及误判栈顶或队首元素。
For circular queues, the wrap-around logic can be tricky. Practice: (rear + 1) MOD size for enqueue and (front + 1) MOD size for dequeue. Remember that a full circular queue usually has one unused space.
对于循环队列，绕回逻辑可能比较棘手。练习：入队时 rear 更新为 (rear + 1) MOD size，出队时 front 更新为 (front + 1) MOD size。记住循环队列满时通常留有一个未用空间。
When comparing implementations, mention trade-offs in terms of memory, speed, and complexity. Use precise terminology like ‘abstract data type’, ‘pointer’, ‘overflow’, ‘underflow’. This demonstrates deeper understanding.
在比较实现方式时，要提及内存、速度和复杂度方面的权衡。使用精确的术语，如“抽象数据类型”、“指针”、“上溢”、“下溢”。这能体现更深层的理解。
Finally, practice pseudocode questions. You might be asked to write an algorithm for balanced parentheses using a stack, or simulate a circular queue with given operations. Familiarity leads to quick, accurate answers.
最后，练习伪代码题。你可能会被要求使用栈编写检查括号平衡的算法，或者模拟给定操作下的循环队列。熟练练习能让你快速准确地作答。
Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply