Stacks and Queues Revision for IB & OCR Computer Science | 栈与队列考点精讲

📚 Stacks and Queues Revision for IB & OCR Computer Science | 栈与队列考点精讲

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle, while a queue follows the First-In, First-Out (FIFO) principle. Mastering these abstract data types is essential for IB and OCR Computer Science exams, as they underpin recursion, expression evaluation, scheduling, and buffering.

栈是遵循后进先出（LIFO）原则的线性数据结构，而队列则遵循先进先出（FIFO）原则。掌握这两种抽象数据类型对于 IB 和 OCR 计算机科学考试至关重要，因为它们是递归、表达式求值、调度和缓冲的基础。

1. Introduction to Stacks and Queues | 栈和队列简介

A stack only allows access to the most recently added element, just like a pile of plates where you can only take the top plate. A queue, on the other hand, operates like a line of people: the first person to join is the first to be served.

栈只允许访问最后添加的元素，就像一摞盘子你只能拿最上面的那个。队列则像排队的人群：最先加入的人最先得到服务。

Both are abstract data types (ADTs) that can be implemented using arrays or linked lists. The choice of implementation affects time complexity and memory usage.

两者都是可以用数组或链表实现的抽象数据类型（ADT）。实现方式的选择会影响时间复杂度和内存使用。

2. Stack Operations: Push, Pop, Peek | 栈操作：压入、弹出、查看栈顶

The three primary operations on a stack are push(item), pop(), and peek(). Push adds an element to the top of the stack, pop removes and returns the top element, and peek returns the top element without removing it.

栈的三个主要操作是 push(item)、pop() 和 peek()。Push 将一个元素压入栈顶，pop 移除并返回栈顶元素，peek 返回栈顶元素但不移除。

push(item):
if top == MAX – 1 then overflow error
else top = top + 1; stack[top] = item

pop():
if top == -1 then underflow error
else item = stack[top]; top = top – 1; return item

In the array implementation, top is an integer pointer initially set to -1, indicating an empty stack. The operation peek simply returns stack[top] when the stack is not empty.

在数组实现中，top 是一个整型指针，初始值为 -1，表示空栈。peek 操作在栈非空时直接返回 stack[top]。

Time complexity of push, pop, peek is O(1) in both array and linked list implementations if no resizing occurs.

如果不涉及扩容，push、pop、peek 的时间复杂度在数组和链表实现中均为 O(1)。

3. Stack Implementations: Arrays and Linked Lists | 栈的实现：数组与链表

Using a static array provides O(1) access but may cause overflow if the capacity is exceeded. A dynamic array can grow, but resizing takes O(n) time, which is amortised O(1).

使用静态数组可实现 O(1) 访问，但如果超过容量则会发生溢出。动态数组可以扩容，但扩容操作耗时为 O(n)，平均分摊为 O(1)。

A linked list implementation allocates nodes dynamically, avoiding fixed-size limitations. Each push creates a new node that becomes the new head; pop removes the head. Memory overhead is higher due to pointers.

链表实现动态分配节点，避免了固定大小的限制。每次 push 创建一个新节点并成为新的头结点；pop 移除头节点。由于指针的存在，内存开销更大。

Example linked-list stack in pseudocode: push creates a node with data and a next pointer pointing to the current top, then updates top. Pop returns top’s data and sets top to top.next.

链表栈的伪代码示例：push 创建一个包含数据及指向当前 top 的 next 指针的节点，然后更新 top。pop 返回 top 的数据并将 top 设为 top.next。

4. Applications of Stacks | 栈的应用

Stacks are widely used to reverse data, parse syntax (bracket matching), evaluate postfix expressions, convert infix to postfix, implement undo operations, and manage function calls via the call stack.

栈被广泛用于逆转数据、语法解析（括号匹配）、后缀表达式求值、中缀转后缀、实现撤消操作以及通过调用栈管理函数调用。

When a function is called, the return address and local variables are pushed onto the call stack. Upon return, the stack frame is popped. This mechanism enables recursion.

当函数被调用时，返回地址和局部变量被压入调用栈。返回时，栈帧被弹出。这一机制使递归成为可能。

In programming, stack overflow occurs when recursion is too deep or infinite, filling the call stack. Understanding this is crucial for IB/OCR exam questions on debugging and recursion limits.

在编程中，递归过深或无限递归会填满调用栈，导致栈溢出。理解这一点对于 IB/OCR 考试中关于调试和递归限制的题目至关重要。

5. Queue Operations: Enqueue, Dequeue | 队列操作：入队与出队

A queue supports enqueue(item) to add an element to the rear and dequeue() to remove and return the front element. A front pointer tracks the first element; a rear pointer tracks the last.

队列支持 enqueue(item) 将元素添加到队尾，以及 dequeue() 移除并返回队首元素。front 指针跟踪第一个元素；rear 指针跟踪最后一个元素。

enqueue(item):
if (rear == MAX – 1) then overflow
else if front == -1 then front = 0; rear = rear + 1; queue[rear] = item

dequeue():
if (front == -1 or front > rear) then underflow
else item = queue[front]; front = front + 1; if front > rear then front = rear = -1; return item

In a simple linear queue, after several dequeues, the front advances, causing unused spaces at the beginning – this is the ‘wasted space’ problem, leading to the circular queue design.

在简单的线性队列中，经过多次出队后，front 前移，导致队首出现未使用的空间——这就是“空间浪费”问题，从而催生了循环队列的设计。

6. Queue Implementations: Linear and Circular Queues | 队列的实现：线性队列与循环队列

A circular queue treats the array as circular: when the rear reaches the end, it wraps around to index 0 if space is available. This eliminates wasted space.

循环队列将数组视为环形：当 rear 到达末尾时，如果有空间，它会绕回到索引 0。这消除了空间浪费。

Key conditions for a circular queue using an array of size MAX:

Full: (rear + 1) % MAX == front

Empty: front == -1

Enqueue: rear = (rear + 1) % MAX; queue[rear] = item
Dequeue: item = queue[front]; if front == rear then front = rear = -1 else front = (front + 1) % MAX

入队：rear = (rear + 1) % MAX; queue[rear] = item
出队：item = queue[front]; 如果 front == rear，则令 front = rear = -1，否则 front = (front + 1) % MAX

Many exams ask candidates to trace or code a circular queue. Remember that one slot is sacrificed to distinguish between full and empty states, unless an extra counter is used.

许多考试要求考生追踪或编写循环队列。请记住，除非使用额外的计数变量，否则需要牺牲一个槽位以区分满和空的状态。

A linked-list queue avoids space waste and can grow indefinitely. It maintains two pointers, front and rear, and adds to rear while removing from front, both O(1) operations.

链表实现的队列避免空间浪费并可以无限增长。它维护 front 和 rear 两个指针，在 rear 处添加，从 front 处移除，均为 O(1) 操作。

7. Priority Queues | 优先队列

In a priority queue, each element has a priority. The dequeue operation removes the highest-priority element, not necessarily the oldest. This ADT is often implemented with a heap for O(log n) efficiency.

在优先队列中，每个元素都有一个优先级。出队操作移除优先级最高的元素，而不一定是最早加入的。这种抽象数据类型通常用堆实现，以达到 O(log n) 的效率。

OCR and IB may include basic questions on priority queue behaviour and its applications in operating systems (e.g. process scheduling) and graph algorithms (e.g. Dijkstra’s algorithm).

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

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

Stacks and Queues Revision for IB & OCR Computer Science | 栈与队列 考点精讲