Stacks and Queues Key Points | IB 计算机：栈与队列考点精讲

📚 Stacks and Queues Key Points | IB 计算机：栈与队列考点精讲

Stacks and queues are fundamental abstract data types (ADTs) in computer science, widely tested in the IB Diploma Programme. Understanding their principles, operations, implementations, and applications is crucial for both Paper 1 and the Internal Assessment. This guide distills the essential knowledge you need, bridging theory with clear bilingual explanation.

栈与队列是计算机科学中最基础的抽象数据类型（ADT），在IB文凭课程中考查频繁。掌握它们的原则、操作、实现方式及应用，对Paper 1和内部评估都至关重要。本指南凝练了你需要的关键知识，用清晰的中英双语解释架起理论与实战的桥梁。

1. Introduction to Stacks | 栈简介

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you can only take the top plate, and a new plate is placed on top. The last element added is the first one to be removed.

栈是一种遵循后进先出（LIFO）原则的线性数据结构。想象一摞盘子：你只能取走最上面的盘子，而新盘子也放在最上面。最后添加的元素最先被移除。

In IB Computer Science, a stack is typically implemented as an ADT with a fixed set of operations. Elements are only accessed at one end, called the “top”. The underlying storage can be an array or a linked list, but the user interacts solely through the stack interface.

在IB计算机科学中，栈通常作为一个具有固定操作集的ADT来实现。元素仅在被称为“栈顶”的一端被访问。底层存储可以是数组或链表，但用户仅通过栈的接口进行交互。

2. Stack Operations | 栈的基本操作

The standard stack operations are push(item), pop(), peek(), isEmpty(), and isFull() (when using a bounded array). Push adds an item to the top of the stack. Pop removes and returns the top item. Peek returns the top item without removing it. isEmpty checks whether the stack contains any elements.

标准的栈操作包括push(item)（入栈）、pop()（出栈）、peek()（取栈顶）、isEmpty()（判空）以及在使用有界数组时的isFull()（判满）。Push将一个元素添加到栈顶；Pop移除并返回栈顶元素；Peek返回栈顶元素但不移除；isEmpty检查栈中是否含有任何元素。

All these operations should run in O(1) time complexity. This constant time performance is a defining characteristic of a well-implemented stack. If a pop is attempted on an empty stack, this causes an underflow error; similarly, a push on a full stack causes an overflow error.

所有这些操作的时间复杂度都应该是O(1)。这种常数时间的性能是良好实现栈的决定性特征。如果对空栈执行pop操作，会引发下溢错误；类似地，对满栈执行push会引发上溢错误。

3. Implementing Stacks | 栈的实现方式

Stacks can be implemented using arrays or linked lists. In an array-based stack, we maintain an index (top pointer) that tracks the position of the last inserted element. Push increments the index and inserts; pop decrements the index. The array size is fixed, leading to potential overflow.

栈可以用数组或链表实现。在基于数组的栈中，我们维护一个索引（栈顶指针）来跟踪最后插入元素的位置。入栈时索引递增并插入；出栈时索引递减。数组大小是固定的，可能导致溢出。

In a linked list implementation, each node stores data and a reference to the next node. The top of the stack corresponds to the head of the list. Push inserts a new node at the head; pop removes the head node. This approach is dynamic and avoids overflow, but uses extra memory for pointers.

在链表实现中，每个节点存储数据和指向下一个节点的引用。栈顶对应链表的头部。入栈在头部插入新节点；出栈移除头部节点。该方法动态分配内存，避免了溢出，但为指针使用了额外内存。

4. Introduction to Queues | 队列简介

A queue is a linear data structure that operates on the First In, First Out (FIFO) principle. The best real-world analogy is a line of people waiting for service: the person who arrives first gets served first. Elements are added at the rear and removed from the front.

队列是一种遵循先进先出（FIFO）原则的线性数据结构。最贴切的现实比喻是排队等候服务的人群：最先到达的人最先得到服务。元素在队尾添加，在队头移除。

In IB terms, a queue is an ADT where insertion (enqueue) happens at one end and deletion (dequeue) happens at the other. It models systems like print spoolers, keyboard buffers, and breadth-first search queues. The interface hides the complexity of the underlying data management.

在IB术语中，队列是一种ADT，其插入（入队）在一端进行，删除（出队）在另一端进行。它模拟了如打印后台处理程序、键盘缓冲区以及广度优先搜索中的队列等系统。其接口隐藏了底层数据管理的复杂性。

5. Queue Operations | 队列的基本操作

The essential queue operations include enqueue(item), dequeue(), peek() (or front), isEmpty(), and isFull(). Enqueue adds an element to the rear; dequeue removes and returns the front element. Peek returns the front element without removing it.

队列的基本操作包括enqueue(item)（入队）、dequeue()（出队）、peek()（或front，队头）、isEmpty()和isFull()。Enqueue将一个元素添加到队尾；Dequeue移除并返回队头元素；Peek返回队头元素但不移除。

Like stacks, each queue operation should ideally run in O(1) time. In a naive array implementation, dequeue causes all remaining elements to shift, which is O(n). This is why circular queues are introduced, but the ADT specification itself does not prescribe the inner workings; it only guarantees FIFO behaviour.

和栈一样，每个队列操作理想情况下应在O(1)时间内运行。在朴素的数组实现中，dequeue会导致所有剩余元素移位，时间复杂度为O(n)。这正是引入循环队列的原因，但ADT规范本身并不规定内部机制；它只保证FIFO行为。

6. Implementing Queues | 队列的实现方式

Queues can be built using arrays or linked lists. In a simple linear array queue, we maintain a front index and a rear index. Enqueue increments rear; dequeue increments front. This leads to the problem of “wasted space” when the front moves forward, as we cannot reuse vacated slots.

队列可以用数组或链表构建。在简单的线性数组队列中，我们维护队头索引和队尾索引。入队时队尾索引递增；出队时队头索引递增。这就导致了“空间浪费”问题：当队头前移时，我们无法重用腾出的空位。

A linked list implementation avoids space wastage. The front of the queue is the head of the list, and the rear is the tail. Enqueue appends a node at the tail; dequeue removes the head node. Both operations are O(1) if we maintain a tail pointer. This is the most efficient general-purpose queue.

链表实现避免了空间浪费。队列的队头是链表头部，队尾是链表尾部。入队时在尾部追加节点；出队时移除头部节点。如果维护尾指针，这两个操作都是O(1)时间。这是最高效的通用队列实现。

7. Circular Queues | 循环队列

A circular queue overcomes the limitation of linear arrays by treating the array as circular. Two pointers, front and rear, wrap around to the beginning of the array when they reach the end. This allows the reuse of freed cells and ensures O(1) enqueue and dequeue without shifting.

循环队列通过将数组视为环形来克服线性数组的局限。两个指针——front（队头）和rear（队尾）——在到达数组末端时绕回开头。这实现了对已释放单元的复用，并保证入队和出队均为O(1)而无需移位。

To distinguish between an empty queue and a full queue in a circular array, we often sacrifice one cell. The queue is empty when front == rear. It is full when (rear + 1) % size == front. An alternative approach uses a separate count variable. IB exam questions may ask about these boundary conditions.

为区分循环数组中的空队和满队，我们通常牺牲一个单元。当front == rear时队列为空；当(rear + 1) % size == front时队列为满。另一种方法是使用一个独立的计数变量。IB试题可能会考查这些边界条件。

8. Deque (Double-Ended Queue) | 双端队列

A deque (pronounced “deck”) is a double-ended queue that allows insertion and deletion at both the front and the rear. It generalises both stacks and queues. You can add or remove elements from either end, making it a flexible ADT for certain algorithms.

双端队列（deque，读音同“deck”）是一种允许在队头和队尾进行插入和删除的队列。它同时泛化了栈和队列。你可以在任意一端添加或移除元素，这使其成为某些算法中灵活的ADT。

Operations for a deque include: pushFront(item), pushRear(item), popFront(), popRear(), peekFront(), peekRear(), isEmpty(), isFull(). Depending on restrictions, we can create an input-restricted deque (insertion at one end only) or an output-restricted deque (deletion at one end only). IB may test the basic concept and its operations.

双端队列的操作包括：pushFront(元素)（前端插入）、pushRear(元素)（后端插入）、popFront()（前端删除）、popRear()（后端删除）、peekFront()（取前端）、peekRear()（取后端）、isEmpty()、isFull()。根据限制，我们可以构建输入受限的双端队列（仅一端插入）或输出受限的双端队列（仅一端删除）。IB可能考查基本概念及其操作。

9. Applications of Stacks | 栈的应用

Stacks appear in many critical computing contexts. Function call stack: when a function is called, its local variables and return address are pushed onto the call stack; when it returns, they are popped. This enables recursion and nested function calls.

栈出现在许多关键的计算机语境中。函数调用栈：当一个函数被调用时，其局部变量和返回地址被压入调用栈；当函数返回时，它们被弹出。这使得递归和嵌套函数调用成为可能。

Other common applications include: undo/redo mechanisms in editors (each action is pushed onto a history stack), bracket matching in compilers and syntax checkers (push opening brackets, pop when matching closing bracket encountered), evaluating arithmetic expressions (infix to postfix conversion, postfix evaluation using stacks), and backtracking algorithms (e.g., depth-first search, maze solving).

其他常见应用包括：编辑器中的撤销/重做机制（每个操作被压入历史栈），编译器和语法检查器中的括号匹配（遇到开括号则入栈，遇到匹配的闭括号则出栈），算术表达式求值（使用栈进行中缀到后缀的转换以及后缀求值），以及回溯算法（例如深度优先搜索、迷宫求解）。

10. Applications of Queues | 队列的应用

Queues are the backbone of scheduling and buffering systems. Print queues store documents in the order they are sent to the printer; the first document sent is the first printed. Keyboard buffers ensure keystrokes are processed in the order typed, even if the system is busy.

队列是调度与缓冲系统的骨干。打印队列按发送到打印机的顺序存储文档；最先发送的文档最先打印。键盘缓冲区保证即使系统忙碌，击键也按输入顺序被处理。

In algorithm design, queues are essential for breadth-first search (BFS): nodes are discovered layer by layer. Other examples include simulation of waiting lines (e.g., supermarket checkouts), asynchronous data transfer in networks, and task scheduling in operating systems (e.g., round-robin scheduling uses a circular queue of processes).

在算法设计中，队列对于广度优先搜索（BFS）至关重要：节点逐层被发现。其他例子包括排队等待的模拟（如超市收银台）、网络中的异步数据传输，以及操作系统中的任务调度（例如，轮转调度使用进程的循环队列）。

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

Stacks and queues are both linear, restricted-access ADTs, but they differ fundamentally in removal discipline. A stack removes the most recently added element (LIFO), while a queue removes the least recently added element (FIFO). This single difference dictates their completely different use cases.

栈和队列都是线性的、访问受限的ADT，但它们从根本上在移除规则上不同。栈移除最近添加的元素（LIFO），而队列移除最早添加的元素（FIFO）。这单一的区别决定了它们完全不同的使用场景。

The table below summarises their key characteristics:

下表归纳了它们的关键特征：

Feature	Stack	Queue
Ordering Principle	LIFO (Last In, First Out)	FIFO (First In, First Out)
Insertion Point	Top only	Rear only
Deletion Point	Top only	Front only
Key Applications	Recursion, Undo, Parsing	Scheduling, BFS, Buffers
Common Implementations	Array, Linked List	Array, Linked List, Circular Array

In exams, you may be asked to trace stack/queue states given a sequence of operations, or to choose the appropriate structure for a given scenario. Always identify whether the problem requires the “most recent” or the “oldest” element next.

在考试中，你可能被要求根据一系列操作来跟踪栈/队列的状态，或者为给定场景选择合适的结构。始终识别出问题是需要“最近”的元素还是“最早”的元素。

12. Exam Tips and Tricks | 考试技巧与易错点

Tracing exercises are common in Paper 1. For stacks, draw a vertical column and update the top after each operation. For queues, draw a horizontal line with front and rear arrows, and remember that dequeue does not shift elements in a circular queue – only the pointers move.

跟踪练习在Paper 1中很常见。对于栈，画一个垂直的列，并在每次操作后更新栈顶。对于队列，画一条水平线并用箭头标出队头和队尾，同时记住在循环队列中出队并不移动元素——只有指针移动。

Be careful with the terminology: “push” and “pop” are for stacks; “enqueue” and “dequeue” are for queues. Do not confuse them in short-answer questions. Also, when describing ADT operations, never refer to underlying implementation details such as array indices – stay at the abstract level.

注意术语：”push”和”pop”用于栈；”enqueue”和”dequeue”用于队列。在简答题中不要混淆它们。另外，在描述ADT操作时，永远不要涉及底层实现细节，如数组索引——保持在抽象层面。

For IB’s pseudo-code questions, you might need to write algorithms using stacks/queues. For instance, reversing a string using a stack (push all characters, then pop all), or simulating a print queue. Practice such standard algorithms, and ensure you handle underflow/overflow conditions explicitly.

对于IB的伪代码题，你可能需要使用栈/队列编写算法。例如，使用栈反转字符串（所有字符入栈，然后全部出栈），或者模拟一个打印队列。练习这些标准算法，并确保明确处理下溢/上溢条件。

Finally, remember that both stacks and queues are often implemented as classes/objects in code-based questions. The examiner expects you to instantiate objects and invoke methods like myStack.push(5) rather than manipulate raw arrays. Structure your answers cleanly with these abstractions.

最后，记住在基于代码的问题中，栈和队列通常被实现为类/对象。考官期望你实例化对象并调用如myStack.push(5)这样的方法，而不是直接操纵原始数组。使用这些抽象结构，让你的答案清晰整洁。

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

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

Stacks and Queues Key Points | IB 计算机：栈与队列 考点精讲