📚 Stacks and Queues | 栈与队列
In both IB and CIE Computer Science, stacks and queues are fundamental abstract data types (ADTs) that appear in algorithm design, system architecture, and practical programming. Understanding their behaviour, implementation, and applications is essential for tackling exam questions on data structures, recursion, expression evaluation, and scheduling. This revision guide walks through every key point you need to master, from basic operations to circular and priority queues, with a clear comparison between the two structures.
在 IB 和 CIE 计算机科学中，栈与队列是基础的抽象数据类型（ADT），广泛用于算法设计、系统架构和实际编程。理解它们的行为、实现方式以及应用场景，对于解答关于数据结构、递归、表达式求值和调度等考题至关重要。本复习指南将从基本操作到循环队列和优先级队列，逐一精讲所有关键考点，并对两者进行清晰比较。
1. Stack as an Abstract Data Type | 作为抽象数据类型的栈
A stack is a linear data structure that follows a Last-In-First-Out (LIFO) principle: the last element pushed onto the stack is the first one to be popped off. Imagine a stack of plates—you can only take the top plate, and you place new plates on top. This constrained access makes stacks predictable and easy to implement, but unsuitable for random access.
栈是一种遵循后进先出（LIFO）原则的线性数据结构：最后推入栈的元素最先被弹出。可以想象成一摞盘子——你只能拿去最上面的盘子，也只能往顶部添加新盘子。这种受限的访问方式使栈行为可预测且易于实现，但不支持随机访问。
The stack ADT is defined purely by its operations, not its implementation. In exams, you will be asked to draw stack states, trace push/pop sequences, and write pseudocode for stack operations using either arrays or linked lists.
栈的 ADT 完全由其操作定义，而非其实现方式。在考试中，你会被要求画出栈的状态、跟踪 push/pop 序列、并用数组或链表为栈操作编写伪代码。
2. Core Stack Operations | 栈的核心操作
A typical stack supports the following operations: push(item) – adds an item to the top of the stack; pop() – removes and returns the item at the top; peek() or top() – returns the top item without removing it; isEmpty() – returns true if the stack contains no elements; isFull() – relevant when using a fixed-size array implementation. All core operations should run in O(1) time.
典型的栈支持以下操作：push(item)——将元素添加到栈顶；pop()——移除并返回栈顶元素；peek() 或 top()——返回栈顶元素但不移除；isEmpty()——栈为空时返回真；isFull()——当使用固定大小的数组实现时适用。所有核心操作的时间复杂度应为 O(1)。
When implementing a stack, you must carefully manage the stack pointer (often called top) which indicates the index or node of the most recently inserted item. Popping from an empty stack causes an underflow error; pushing to a full array-based stack causes an overflow error.
实现栈时，必须小心管理栈指针（通常称为 top），它指示最新插入元素的下标或节点。从空栈中弹出会导致下溢错误；向已满的数组栈中推入元素会导致上溢错误。
3. Array Implementation of a Stack | 栈的数组实现
An array-based stack uses a one-dimensional array and an integer variable top initialised to -1. When pushing, increment top and store the value at that index. When popping, retrieve the value at top and decrement top. This static implementation is straightforward but requires a maximum size to be declared in advance.
基于数组的栈使用一维数组和一个初始化为 -1 的整数变量 top。推入时，先递增 top 再存储值；弹出时，读取 top 索引处的值再递减 top。这种静态实现简单直接，但需要预先声明最大容量。
| Operation | Pseudocode |
|---|---|
| Push | if top < MAX-1 then top ← top + 1 stack[top] ← item else output “overflow” |
| Pop | if top >= 0 then item ← stack[top] top ← top – 1 return item else output “underflow” |
In practice, you must always check bounds to avoid runtime errors. Many exam questions provide a partially filled array and ask you to show the state after a sequence of push and pop calls.
实际应用中必须始终检查边界以避免运行时错误。许多考题会给出一个部分填充的数组，要求你展示经过一系列 push 和 pop 调用后的状态。
4. Linked List Implementation of a Stack | 栈的链表实现
A linked-list stack avoids the fixed-size limitation by dynamically allocating nodes. The top pointer references the head node of the list. Pushing creates a new node, links it to the current top, and updates top to the new node. Popping removes the head node and advances top to the next node. Memory is used only when needed, and overflow can only occur if system memory is exhausted.
链表栈通过动态分配节点避免了固定大小的限制。top 指针指向链表的头节点。推入操作创建一个新节点，将其链接到当前 top，然后更新 top 指向新节点。弹出操作移除头节点并将 top 前移。仅当需要时才使用内存，溢出只在系统内存耗尽时发生。
The O(1) time complexity holds because insertion and deletion occur at the head. However, linked structures require extra space for pointers, and pointer manipulation must be handled carefully to avoid losing references. Be prepared to write or trace pseudocode that uses objects with data and next attributes.
由于插入和删除都发生在头部，因此 O(1) 时间复杂度得以保持。但链式结构需要额外的指针存储空间，且必须小心处理指针操作以避免丢失引用。要做好准备编写或跟踪使用带有 data 和 next 属性的对象的伪代码。
5. Applications of Stacks | 栈的应用场景
Stacks are used wherever a LIFO behaviour is needed. Classic applications include: managing function calls (call stack), evaluating arithmetic expressions (postfix and prefix notation), implementing undo/redo features, backtracking algorithms (e.g., depth-first search, maze solving), and checking balanced parentheses in source code. In the call stack, each function invocation creates a stack frame containing return addresses and local variables; when a function returns, its frame is popped.
任何需要 LIFO 行为的场景都会用到栈。经典应用包括：函数调用管理（调用栈）、算术表达式求值（后缀与前缀表示法）、实现撤销/重做功能、回溯算法（如深度优先搜索、迷宫求解）以及检查源代码中的括号匹配。在调用栈中，每次函数调用都会创建一个包含返回地址和局部变量的栈帧；函数返回时其帧被弹出。
For expression evaluation, the shunting-yard algorithm uses two stacks to convert infix to postfix, and a single stack can then evaluate the postfix expression. The balanced parentheses problem is a favorite exam topic: push each opening bracket, pop when a matching closing bracket appears; mismatches or a non-empty stack at the end indicate an error.
在表达式求值中，调度场算法使用两个栈将中缀表达式转换为后缀表达式，然后单栈即可计算后缀表达式。括号匹配问题是热门的考试主题：每个左括号入栈，遇到匹配的右括号时出栈；不匹配或结束时栈非空都表示错误。
6. Queue as an Abstract Data Type | 作为抽象数据类型的队列
A queue is a linear data structure that follows a First-In-First-Out (FIFO) principle: the first element inserted is the first one to be removed. Like a line of people waiting at a ticket counter, the person who arrives first is served first. Access is restricted to the two ends—elements enter at the rear (tail) and leave from the front (head).
队列是一种遵循先进先出（FIFO）原则的线性数据结构：最先插入的元素最先被移除。就像排队购票的人群，先到的人先得到服务。访问被限制在两端——元素从队尾（后端）进入，从队首（前端）离开。
Queues are essential for modelling real-world waiting lines, scheduling tasks in operating systems, buffering data streams, and implementing breadth-first search. Their behaviour makes them ideal for any scenario where order of arrival must be preserved.
队列对于模拟现实世界的等待队列、在操作系统中调度任务、缓冲数据流以及实现广度优先搜索至关重要。它们的行为使其成为任何必须保持到达顺序的场景的理想选择。
7. Core Queue Operations | 队列的核心操作
The standard queue operations are: enqueue(item) – add an item to the rear; dequeue() – remove and return the item from the front; peek() or front() – return the front item without removing it; isEmpty() – check whether the queue is empty; isFull() – check whether the queue is full (for bounded queues). Just like stacks, these should all be O(1) when implemented efficiently.
标准队列操作有：enqueue(item)——将元素添加到队尾；dequeue()——移除并返回队首元素；peek() 或 front()——返回队首元素但不移除；isEmpty()——检查队列是否为空；isFull()——检查队列是否已满（针对有界队列）。与栈相同，高效实现时这些操作的时间复杂度都应为 O(1)。
In pseudocode, you will often use two pointers: head (or front) pointing to the next item to be removed, and tail (or rear) pointing to the position where the next item will be inserted. Managing these indices correctly is crucial to avoid wasting space or losing elements.
在伪代码中，通常使用两个指针：head（或 front）指向下一个待移除的元素，tail（或 rear）指向下一个元素将要插入的位置。正确管理这些下标对于避免空间浪费或丢失元素至关重要。
8. Linear Queue Implementation Using Arrays | 线性队列的数组实现
A simple linear queue can be built using an array with head and tail indices. Initially, both are set to 0. Enqueue stores the item at tail and increments tail; dequeue returns the item at head and increments head. However, this naïve approach suffers from the drifting problem: as elements are removed, the used portion of the array moves forward until tail reaches the end, leaving unused space at the beginning. This can be fixed by shifting elements, but that breaks O(1) dequeue.
简单线性队列可以用带有 head 和 tail 下标的数组来构建。初始时两者都置 0。入队时将元素存入 tail 处并递增 tail；出队时返回 head 处的元素并递增 head。然而这种朴素方法存在漂移问题：随着元素被移除，数组已用区域不断前移，直到 tail 到达末尾，而数组前端留下了未使用的空间。这可以通过移动元素来弥补，但会破坏 O(1) 的出队操作。
Because of the drifting problem, linear array implementations are rarely used in practice unless the array is explicitly treated as a circular buffer. Nevertheless, you must be able to trace a linear queue’s state and identify when it becomes inefficient.
由于漂移问题，线性数组实现在实践中很少使用，除非明确将数组视为循环缓冲区。然而，你必须能够跟踪线性队列的状态并识别其何时变得低效。
9. Circular Queue | 循环队列
A circular queue overcomes the drifting problem by wrapping the indices around to the beginning of the array. Both head and tail move modulo the array size. Enqueue stores the item at tail and updates tail = (tail + 1) MOD size; dequeue takes the item from head and updates head = (head + 1) MOD size. This reuses freed slots and maintains O(1) operations.
循环队列通过将下标回绕到数组开头来解决漂移问题。head 和 tail 都按数组大小取模移动。入队：将元素存入 tail 位置，然后令 tail = (tail + 1) MOD size；出队：从 head 位置取出元素，然后令 head = (head + 1) MOD size。这样可重复使用释放的槽位，并维持 O(1) 操作。
To distinguish between an empty queue (head == tail) and a full queue (head == tail), a common technique is to leave one slot unused. The queue is considered full when (tail + 1) MOD size == head. Exam questions often ask you to draw the state of a circular queue after a series of enqueues and dequeues, or to write pseudocode for the full and empty checks.
为了区分空队列（head == tail）和满队列（head == tail），常用技巧是保留一个未用的槽位。当 (tail + 1) MOD size == head 时认为队列已满。考题常要求你画出一系列入队和出队后循环队列的状态，或编写满/空检查的伪代码。
10. Priority Queue | 优先级队列
A priority queue is a variant where each element has an associated priority. The element with the highest priority is dequeued first, regardless of insertion order. If two elements have the same priority, they are usually served in FIFO order. Priority queues can be implemented using an unordered array (O(1) enqueue, O(n) dequeue), an ordered array (O(n) enqueue, O(1) dequeue), or a heap data structure (O(log n) for both). IB and CIE syllabuses may expect you to understand the concept and simple implementations, though heaps are more advanced.
优先级队列是一种变体，其中每个元素都关联一个优先级。优先级最高的元素最先出队，而不考虑插入顺序。如果两个元素优先级相同，则通常按 FIFO 顺序服务。优先级队列可用无序数组（入队 O(1)、出队 O(n)）、有序数组（入队 O(n)、出队 O(1)）或堆数据结构（两者均为 O(log n)）实现。IB 和 CIE 考纲可能要你理解这一概念及简单实现，堆则更为进阶。
Applications of priority queues include operating system process scheduling (e.g., shortest job first), bandwidth management, and Dijkstra’s shortest path algorithm. In pseudocode, you may be asked to implement a dequeue that scans for the highest priority item.
优先级队列的应用包括操作系统进程调度（如最短作业优先）、带宽管理以及 Dijkstra 最短路径算法。考题中可能要求你实现一个通过扫描查找最高优先级元素的出队操作。
11. Queue Implementation Using a Linked List | 队列的链表实现
A linked list provides a natural dynamic implementation for a queue. We maintain two pointers: front (pointing to the first node) and rear (pointing to the last node). Enqueue creates a new node, attaches it after rear, and updates rear. Dequeue removes the node at front and updates front to the next node; if the queue becomes empty, both front and rear are set to null. All operations are O(1).
链表为队列提供了一种自然的动态实现。我们维护两个指针：front（指向第一个节点）和 rear（指向最后一个节点）。入队时创建新节点，将其挂到 rear 之后并更新 rear。出队时移除 front 所指节点，并将 front 更新为下一个节点；若队列变空，则将 front 和 rear 都置空。所有操作均为 O(1)。
The linked-list approach eliminates size constraints and memory waste, making it very flexible. However, pointer maintenance can be error-prone, and extra memory is consumed for the node references. Be ready to trace or write code that handles the special case of enqueuing into an empty queue (where front and rear both point to the new node).
链表方法消除了大小限制和内存浪费，因此非常灵活。但指针维护容易出错，且节点引用会消耗额外内存。要准备好跟踪或编写处理特殊情况（入队到空队列时，front 和 rear 都指向新节点）的代码。
12. Applications of Queues and Comparison with Stacks | 队列的应用及与栈的比较
Queues are used extensively in computing: keyboard input buffers, printer spooling, CPU scheduling, breadth-first search in graphs, and simulation of physical waiting lines. In contrast, stacks are used for depth-first search, expression evaluation, and supporting recursion. The choice between stack and queue depends entirely on the order in which elements need to be processed—LIFO for reverse-order processing, FIFO for preserving input order.
队列在计算机中应用广泛：键盘输入缓冲区、打印机假脱机、CPU 调度、图的广度优先搜索以及物理排队模拟。相比之下，栈用于深度优先搜索、表达式求值以及支持递归。选择栈还是队列完全取决于元素需要被处理顺序——需要逆序处理时选 LIFO，需要保留输入顺序时选 FIFO。
| Feature | Stack | Queue |
|---|---|---|
| Discipline | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Insert operation | push (top) | enqueue (rear) |
| Remove operation | pop (top) | dequeue (front) |
| Typical pointer(s) | top | head/front, tail/rear |
| Overflow check | top == MAX-1 (array) | (tail+1) % MAX == head (circular) |
| Underflow check | top < 0 (or isEmpty) | head == tail (or isEmpty) |
| Key use cases | Undo, call stack, expression eval, DFS | Scheduling, buffering, BFS, simulation |
Understanding these similarities and differences is essential for answering comparison and selection questions. Remember that both structures restrict access to specific ends, yet they serve complementary roles in algorithm design.
理解这些异同对于回答比较和选择类问题至关重要。记住，两种结构都将访问限制在特定端点，但它们在算法设计中扮演互补的角色。
Published by TutorHao | IB CIE 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