Stacks and Queues: IB CCEA Computer Science Revision | 栈与队列考点精讲

📚 Stacks and Queues: IB CCEA Computer Science Revision | 栈与队列考点精讲

Stacks and queues are fundamental abstract data types (ADTs) that appear throughout the IB CCEA Computer Science syllabus. Understanding their behaviour, operations, and applications is essential for both theory examinations and practical problem-solving. This article provides a comprehensive revision guide covering definitions, implementations, real-world uses, and common exam pitfalls.

栈和队列是IB CCEA计算机科学课程中无处不在的基础抽象数据类型。理解它们的行为、操作和应用对于理论考试和实际解决问题都至关重要。本文提供一份全面的复习指南，涵盖定义、实现方式、实际应用场景以及常见考试陷阱。

1. Introduction to Abstract Data Types (ADTs) | 抽象数据类型简介

An abstract data type is a model for data structures that defines the behaviour of data and operations from the user’s perspective, independent of any concrete implementation. Stacks and queues are classic examples of ADTs because they specify what operations can be performed (e.g. push, pop, enqueue, dequeue) without dictating how the data is stored internally.

抽象数据类型是从用户角度定义数据及其操作行为的一种数据模型，它独立于任何具体实现。栈和队列就是典型的ADT例子，因为它们规定了可以执行哪些操作（例如push、pop、enqueue、dequeue），而不规定数据在内部是如何存储的。

In IB CCEA exams, you may be asked to identify whether a given data structure is an ADT and to explain the difference between an ADT and its implementation. Remember that arrays and linked lists are concrete data structures used to implement ADTs like stacks and queues.

在IB CCEA考试中，你可能会被要求判断某个数据结构是否属于ADT，并解释ADT与其实现之间的区别。请记住：数组和链表是实现栈、队列等ADT的具体数据结构。

Key properties of stacks and queues arise from their access policies: Last-In-First-Out (LIFO) for stacks and First-In-First-Out (FIFO) for queues. These policies constrain how elements are added and removed, making them suitable for specific algorithms.

栈和队列的关键特性源自它们的存取策略：栈遵循后进先出（LIFO），队列遵循先进先出（FIFO）。这些策略限制了元素的添加和删除方式，使它们适用于特定算法。

2. Stack Definition and Operations | 栈的定义与操作

A stack is a linear ADT that follows the LIFO principle: the last element inserted is the first one to be removed. Elements are inserted and removed only from one end, traditionally called the top. You can visualise a stack like a pile of plates; you can only take the topmost plate or add a new one on top.

栈是一种遵循LIFO原则的线性ADT：最后插入的元素最先被移除。元素只能从称为栈顶的一端插入和删除。你可以把栈想象成一叠盘子：只能拿最上面的那个，也只能把新盘子放在最上面。

The essential stack operations specified by the IB CCEA syllabus are:

push(item) – adds an item to the top of the stack.
pop() – removes and returns the item at the top of the stack.
peek() / top() – returns the top item without removing it.
isEmpty() – checks whether the stack contains any items.
isFull() – relevant when the stack has a fixed capacity (e.g. array-based).

IB CCEA教学大纲要求掌握以下基本栈操作：

push(item) – 将元素添加到栈顶。
pop() – 移除并返回栈顶元素。
peek() / top() – 返回栈顶元素但不移除。
isEmpty() – 检查栈是否为空。
isFull() – 当栈容量固定时使用（例如基于数组的实现）。

All core stack operations should ideally run in constant time, O(1), which is achievable in both array and linked-list implementations when managed correctly. Common exam questions ask for tracing these operations on a given stack or translating pseudocode into a real programming language.

所有核心栈操作理想情况下应在常数时间 O(1) 内完成，只要管理得当，无论是数组实现还是链表实现都能达到这一效率。常见考题要求对给定栈追踪这些操作，或将伪代码翻译成真实编程语言。

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

An array-based stack uses a fixed-size array and an integer variable top to track the index of the most recently inserted element. Initially, top is set to -1 to indicate an empty stack. When pushing, top increments and the new element is stored at that index; when popping, the element at top is returned and top decrements.

基于数组的栈使用一个固定大小的数组和一个整型变量top来记录最新插入元素的索引。初始时，top设为-1表示空栈。push时，top递增，新元素存入该索引处；pop时，返回top所指元素，然后top递减。

Pseudocode for array-based stack operations often appears in exams:

push(stack, item): if top < capacity-1 then top ← top + 1; stack[top] ← item

pop(stack): if top ≥ 0 then item ← stack[top]; top ← top – 1; return item

考试中常出现基于数组的栈操作伪代码：

push(stack, item)：如果 top < capacity-1，则 top ← top + 1；stack[top] ← item

pop(stack)：如果 top ≥ 0，则 item ← stack[top]；top ← top – 1；返回 item

A common pitfall is forgetting to check for stack overflow (push on a full stack) and underflow (pop from an empty stack). In IB CCEA, you must include appropriate error handling or indicate that a call is invalid. Arrays offer fast index-based access but waste memory if the stack is rarely full.

一个常见的陷阱是忘记检查栈溢出（对满栈执行push）和栈下溢（对空栈执行pop）。在IB CCEA考试中，你必须包含适当的错误处理，或者指出调用无效。数组提供快速的索引访问，但如果栈很少满，会浪费内存。

4. Stack Implementation Using Linked Lists | 使用链表实现栈

A linked-list stack uses a singly linked list where the head node represents the top of the stack. Each node contains a data field and a pointer to the next node. Pushing involves creating a new node and inserting it at the head; popping involves removing the head node and updating the head pointer.

基于链表的栈使用单链表，头节点代表栈顶。每个节点包含一个数据域和指向下一个节点的指针。push操作需要创建一个新节点并插入到头节点之前；pop操作需要移除头节点并更新头指针。

In this implementation, there is no fixed capacity, so the stack grows dynamically as long as memory is available. This avoids the overflow problem inherent in arrays, but each node requires extra memory for the pointer. All operations remain O(1).

在这种实现中，没有固定容量，只要内存允许栈就可以动态增长。这避免了数组固有的溢出问题，但每个节点需要额外的指针内存。所有操作仍然保持O(1)的时间复杂度。

Simplified push pseudocode for a linked-list stack:

push(head, item): newNode ← new Node(item); newNode.next ← head; head ← newNode

链表栈的简化push伪代码：

push(head, item)：newNode ← new Node(item)；newNode.next ← head；head ← newNode

Questions may ask you to compare the two implementations in terms of memory usage, speed, and dynamic resizing. You should also be able to write or interpret linked-list code for pop, peek, and isEmpty.

考试问题可能会要求你比较两种实现在内存使用、速度和动态调整大小方面的差异。你还应该能够编写或解读pop、peek和isEmpty的链表代码。

5. Stack Applications | 栈的应用

Stacks are used in a wide variety of computing contexts. The most important applications for IB CCEA include function call management, expression evaluation (infix to postfix conversion and postfix evaluation), bracket matching, undo mechanisms in software, and depth-first search (DFS) in graph algorithms.

栈被广泛应用于各种计算场景。对IB CCEA而言最重要的应用包括函数调用管理、表达式求值（中缀转后缀转换及后缀求值）、括号匹配、软件中的撤销功能，以及图算法中的深度优先搜索（DFS）。

The call stack is a classic example: when a function is invoked, its local variables and return address are pushed onto the call stack. When the function returns, its frame is popped. This mechanism naturally supports recursion, where calls pile up and unwind in LIFO order.

调用栈是一个经典例子：调用函数时，其局部变量和返回地址被推入调用栈；函数返回时，其栈帧被弹出。这一机制天然支持递归，递归调用按照LIFO顺序堆积和展开。

For expression conversion, the shunting-yard algorithm uses a stack to manage operators. When evaluating postfix expressions, operands are pushed onto a stack; when an operator is encountered, the required operands are popped, the operation is performed, and the result is pushed back. You might be asked to trace such an algorithm step by step.

对于表达式转换，调度场算法使用一个栈来管理运算符。在计算后缀表达式时，操作数被推入栈；遇到运算符时，弹出所需数量的操作数进行计算，结果再推回栈。你可能会被要求逐步追踪这样的算法。

Bracket matching is another common exam topic: a stack can check whether parentheses, braces, and brackets are balanced by pushing each opening symbol and popping when the corresponding closing symbol appears. If the stack is empty at the end, the expression is balanced.

括号匹配是另一个常见考试主题：栈可以通过推入每个开括号、并在遇到对应的闭括号时弹出来检查圆括号、花括号和方括号是否平衡。如果最后栈为空，则表达式是平衡的。

6. Queue Definition and Operations | 队列的定义与操作

A queue is a linear ADT that follows the FIFO principle: the first element inserted is the first one to be removed. Elements are added at the rear (or tail) and removed from the front (or head). This is analogous to a checkout line in a store – the person who has been waiting longest is served next.

队列是一种遵循FIFO原则的线性ADT：最先插入的元素最先被移除。元素在队尾添加，从队首移除。这就像商店里的结账队列——等待时间最长的人下一个被服务。

The core queue operations defined in the IB CCEA specification are:

enqueue(item) – adds an item to the rear of the queue.
dequeue() – removes and returns the item at the front of the queue.
peek() / front() – returns the front item without removing it.
isEmpty() – checks whether the queue is empty.
isFull() – used for bounded queues.

IB CCEA规范中定义的核心队列操作有：

enqueue(item) – 将元素添加到队尾。
dequeue() – 移除并返回队首元素。
peek() / front() – 返回队首元素但不移除。
isEmpty() – 检查队列是否为空。
isFull() – 用于有界队列。

All operations should run in O(1) time. Achieving O(1) dequeue with an array-based queue requires special handling – which leads to the circular queue concept discussed later.

所有操作应在O(1)时间内完成。使用基于数组的队列实现O(1)的出队需要特殊处理——这就引出了后面要讨论的循环队列概念。

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

A naive linear array implementation of a queue where the front is always at index 0 suffers from O(n) dequeue because all remaining elements must shift left. This is inefficient and not acceptable for the IB CCEA syllabus. Instead, two pointers (front and rear) are maintained to track the endpoints without shifting elements.

一种朴素的线性数组队列实现总是将队首放在索引0，这样每次出队都需要将所有剩余元素左移，导致O(n)的时间复杂度。这种做法效率低下，不符合IB CCEA教学大纲要求。应该维护两个指针（front和rear）来跟踪端点，而不移动元素。

In the two-pointer linear approach, front initially points to index 0, and rear to -1. Enqueue increments rear and inserts the item; dequeue retrieves the item at front and then increments front. However, this leads to the ‘unusable space’ problem: after several enqueue and dequeue operations, the space before front becomes wasted.

在双指针线性方案中，front初始指向索引0，rear初始指向-1。入队时rear递增并插入元素；出队时取出front所指元素，然后front递增。但这会导致“无用空间”问题：经过多次入队和出队后，front之前的位置就被浪费了。

IB CCEA questions often ask about this limitation to lead into the circular queue. You must be able to explain why a simple linear array implementation is flawed and how a circular queue overcomes it.

IB CCEA考试经常就此限制提问，以引出循环队列。你必须能够解释简单的线性数组实现为何存在缺陷，以及循环队列如何克服这一缺陷。

8. Circular Queues | 循环队列

A circular queue treats the array as if it were circular – when either the front or rear pointer moves past the last index, it wraps around to 0. This reuses the vacated space and allows the queue to operate in true O(1) time for both enqueue and dequeue while using a fixed-size array efficiently.

循环队列将数组视为环形——当front或rear指针越过最后一个索引时，就绕回到0。这重用了释放的空间，使队列能够在固定大小的数组上以真正的O(1)时间执行入队和出队操作，且高效利用空间。

Key formulas for circular queue operations:

enqueue: rear ← (rear + 1) mod capacity

dequeue: front ← (front + 1) mod capacity

循环队列操作的关键公式：

入队：rear ← (rear + 1) mod capacity

出队：front ← (front + 1) mod capacity

One difficulty is distinguishing between an empty and a full queue, because in both cases the front and rear can point to the same index. Common solutions include using a separate count variable, or sacrificing one array slot so that the queue is considered full when (rear + 1) mod capacity equals front. You need to be familiar with at least one strategy and its implications.

一个难点是区分空队列和满队列，因为在这两种情况下front和rear可能指向同一个索引。常见的解决方案包括使用一个独立的计数变量，或牺牲一个数组元素，使得当 (rear + 1) mod capacity 等于 front 时认为队列已满。你需要熟悉至少一种策略及其影响。

IB CCEA past papers frequently feature circular queue tracing exercises where you are given an array and a series of operations, and you must determine the final contents and pointer positions.

IB CCEA历年真题中经常出现循环队列追踪练习，题目给定一个数组和一系列操作，要求你确定最终的存储内容和指针位置。

9. Queue Implementation Using Linked Lists | 使用链表实现队列

A linked-list queue maintains two external pointers: one to the front node and one to the rear node. Enqueue adds a new node after the rear and updates rear; dequeue removes the front node and updates front. This avoids all waste of space and naturally supports dynamic resizing.

链表队列维护两个外部指针：一个指向队首节点，另一个指向队尾节点。入队时在rear之后添加新节点并更新rear；出队时移除front节点并更新front。这样就避免了所有空间浪费，并自然地支持动态调整大小。

Pseudocode for linked-list queue operations:

enqueue(front, rear, item): newNode ← new Node(item); rear.next ← newNode; rear ← newNode

dequeue(front, rear): if front ≠ NULL then item ← front.data; front ← front.next; return item

链表队列操作的伪代码：

enqueue(front, rear, item)：newNode ← new Node(item)；rear.next ← newNode；rear ← newNode

dequeue(front, rear)：如果 front ≠ NULL，则 item ← front.data；front ← front.next；返回 item

When the queue becomes empty after a dequeue, both front and rear should be reset to NULL to prevent dangling pointers. Memory management and pointer updates are classic sources of error in exams, so draw diagrams while tracing.

当出队后队列变空时，front和rear都应重置为NULL以防止悬空指针。内存管理和指针更新是考试中经典的错误来源，因此在追踪时最好画图辅助。

10. Queue Applications | 队列的应用

Queues are pervasive in computing systems. In IB CCEA, key applications include scheduling (print spooler, CPU task scheduling), buffering (keyboard input buffer, data streaming), breadth-first search (BFS) in graphs, and simulation of real-world waiting lines.

队列在计算系统中无处不在。IB CCEA课程中的关键应用包括调度（打印队列、CPU任务调度）、缓冲（键盘输入缓冲区、数据流）、图的广度优先搜索（BFS），以及对真实世界排队场景的模拟。

BFS particularly relies on a queue to explore vertices level by level. When visiting a vertex, its unvisited neighbours are enqueued. This ensures that vertices closer to the source are processed before those farther away. You may be asked to simulate BFS on a simple graph using a queue.

广度优先搜索尤其依赖队列来逐层探索顶点。访问一个顶点时，将它尚未访问的邻居入队。这确保了离起始点较近的顶点先于较远的顶点被处理。你可能会被要求使用队列在简单图上模拟BFS。

Priority queues are an extension but are not a core part of the standard queue topic. However, you should recognise that a standard queue maintains strict FIFO ordering, whereas a priority queue orders elements by a priority value. This distinction occasionally appears in higher-tier questions.

优先级队列是一种扩展，但不是标准队列主题的核心内容。但是，你应该认识到标准队列保持严格的FIFO顺序，而优先级队列按优先级值排序元素。这一区别偶尔会出现在高阶题目中。

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

Both stacks and queues are linear data structures that store collections of elements and support insertion and removal. The critical difference lies in the order of removal: LIFO for stacks, FIFO for queues. This single design decision dictates their suitability for different tasks.

栈和队列都属于线性数据结构，都能存储元素集合并支持插入和删除操作。关键区别在于删除的顺序：栈是LIFO，队列是FIFO。这一个设计决策就决定了它们适用于不同的任务。

A comparison table often helps to consolidate understanding:

Aspect / 方面	Stack / 栈	Queue / 队列
Insertion end / 插入端	Top / 栈顶	Rear / 队尾
Removal end / 删除端	Top / 栈顶	Front / 队首
Ordering principle / 排序原则	LIFO / 后进先出	FIFO / 先进先出
Typical uses / 典型用途	Call stack, undo, parsing / 调用栈、撤销、解析	Scheduling, BFS, buffers / 调度、BFS、缓冲区
Overflow/Underflow / 溢出/下溢	Push on full / pop on empty	Enqueue on full / dequeue on empty

表格有助于巩固理解。

In terms of implementation, both can be built using arrays or linked lists with their respective trade‑offs. IB CCEA often asks you to justify your choice of implementation for a given scenario, considering memory and performance constraints.

在实现方面，两者都可以用数组或链表构建，并各有其利弊。IB CCEA经常要求你针对给定场景论证你的实现选择，并考虑内存和性能约束。

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

When answering IB CCEA questions on stacks and queues, always read the scenario carefully. If an algorithm description mentions ‘return to the previous state’ or ‘backtrack’, it is likely a stack. If it mentions ‘waiting line’, ‘serve in order’, or ‘processing in sequence’, it is probably a queue.

解答IB CCEA关于栈和队列的题目时，务必仔细阅读场景描述。如果算法描述中提到“返回之前的状态”或“回溯”，那很可能适用栈。如果提到“排队等候”、“按顺序服务”或“顺序处理”，那很可能适用队列。

Common pitfalls include:

Forgetting to update both front and rear pointers when a linked-list queue becomes empty.
Mishandling the full/empty ambiguity in circular queues without a clear strategy.
Using confusion between pop/peek and dequeue/front terminologies – be precise.
Ignoring boundary conditions: empty stack/queue before pop/dequeue.
Drawing incomplete diagrams when tracing algorithms – always label the state after each step.

常见陷阱包括：

当链表队列变空时忘记同时更新front和rear两个指针。
在没有明确策略的情况下错误处理循环队列的满/空状态歧义。
混淆pop/peek与dequeue/front等术语——务必精确。
忽略边界条件：执行pop/dequeue之前先检查是否为空。
追踪算法时绘图不完整——务必标注每一步之后的状态。

Practice tracing exercises with small concrete examples. Write pseudocode from scratch for both ADTs using arrays and linked lists. This will prepare you for the structured questions that often require you to fill in missing code, identify errors, or draw the final state of a data structure.

多练习具体的追踪练习。从头开始为两种ADT编写基于数组和链表的伪代码。这会帮助你准备结构化问题，这类问题常要求填补缺失代码、找出错误或绘制数据结构的最终状态。

Finally, when comparing different implementations in an essay-style question, use technical vocabulary such as ‘time complexity’, ‘space complexity’, ‘static allocation’, and ‘dynamic allocation’. Linking the choice to the specific requirements of the application demonstrates higher-order thinking.

最后，在评述式问题中比较不同实现时，使用“时间复杂度”、“空间复杂度”、“静态分配”和“动态分配”等技术词汇。将选择与应用的具体需求联系起来，能体现高阶思维能力。

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

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

Stacks and Queues: IB CCEA Computer Science Revision | 栈与队列考点精讲