📚 Operations on Stacks and Queues | 栈与队列的操作
In A-Level Computer Science, understanding abstract data types such as stacks and queues is essential for solving problems efficiently. These linear data structures restrict how elements are inserted and removed, leading to well-defined operations that form the backbone of many algorithms. This article explores the core operations of stacks and queues, their implementations, time complexities, and typical exam scenarios.
在 A-Level 计算机科学中，理解栈和队列这样的抽象数据类型对于高效解决问题至关重要。这些线性数据结构限制了元素的插入和移除方式，形成了明确定义的操作，这些操作是许多算法的基石。本文探讨栈和队列的核心操作、实现方式、时间复杂度以及典型的考试场景。
1. What Is a Stack? | 什么是栈？
A stack is a Last-In-First-Out (LIFO) data structure. Imagine a stack of plates: the last plate placed on top is the first one you can take off. In programming, you can only access the top element. This restriction makes stacks ideal for tasks like tracking function calls, undo mechanisms, and parsing expressions.
栈是一种后进先出（LIFO）的数据结构。想象一摞盘子：最后放上去的盘子是你第一个能拿走的。在编程中，你只能访问栈顶元素。这种限制使得栈非常适合用于跟踪函数调用、撤销机制以及解析表达式等任务。
You can visualise a stack as a vertical arrangement where new elements are added to the top and removal also happens from the top. The underlying storage could be an array or a linked list, but the interface remains the same: you interact only with one end.
你可以将栈可视化为一个垂直排列，新元素被添加到顶部，移除操作也从顶部进行。底层存储可以是数组或链表，但接口保持不变：你只与其中一端交互。
2. Core Operations of a Stack | 栈的核心操作
A stack generally supports four fundamental operations: push, pop, peek (or top), and isEmpty. The push operation adds an element to the top of the stack. If the stack is implemented using an array with a fixed capacity, you must check for overflow before pushing.
栈通常支持四种基本操作：push（压入）、pop（弹出）、peek（或top，查看栈顶）和 isEmpty（判断是否为空）。push 操作将一个元素添加到栈顶。如果栈使用具有固定容量的数组实现，必须在压入前检查是否溢出。
The pop operation removes and returns the top element. If the stack is empty, calling pop results in an underflow error, which must be handled in robust programs. The peek operation returns the top element without modifying the stack, useful for inspecting the next item to be processed.
pop 操作移除并返回栈顶元素。如果栈为空，调用 pop 会导致下溢错误，这必须在健壮的程序中加以处理。peek 操作返回栈顶元素而不修改栈，这对于检查待处理的下一个项目非常有用。
The isEmpty operation returns a Boolean indicating whether the stack contains any elements. In some implementations, a size operation is also provided, though it is not strictly necessary if isEmpty is available.
isEmpty 操作返回一个布尔值，指示栈中是否含有任何元素。在某些实现中，还提供了 size 操作，但如果已有 isEmpty，它并非绝对必要。
Operation complexities: Push O(1), Pop O(1), Peek O(1)
操作复杂度：压入 O(1)，弹出 O(1)，查看栈顶 O(1)
3. Stack Applications in Programming | 栈在编程中的应用
Stacks shine in situations where you need to reverse something or keep track of state that must be unwound in reverse order. Browser back buttons, for example, use a stack to store visited URLs; clicking back pops the last visited page. Similarly, the call stack in programming languages records active subroutines, returning control in LIFO order.
栈在你需要反转某些内容或追踪必须以相反顺序展开的状态时大放异彩。例如，浏览器的后退按钮使用栈来存储访问过的 URL；点击后退会弹出上一个访问的页面。同样，编程语言中的调用栈记录活动的子程序，以后进先出的顺序返回控制。
Another classic use is checking for balanced parentheses in expressions. You push opening brackets and pop when encountering closing brackets; if at the end the stack is empty, the brackets are balanced. Expression evaluation, such as converting infix to postfix notation, relies heavily on stacks.
另一个经典用法是检查表达式中的括号是否平衡。遇到开括号时压栈，遇到闭括号时弹栈；如果最终栈为空，则括号平衡。表达式求值，例如将中缀表达式转换为后缀表示法，也严重依赖栈。
Recursion itself is implemented using a stack behind the scenes. Each recursive call places a new frame on the call stack, and unwinding occurs as base cases are reached.
递归本身在后台就是使用栈来实现的。每次递归调用会将一个新的帧压入调用栈，而回溯过程在到达基本情况时展开。
4. What Is a Queue? | 什么是队列？
A queue is a First-In-First-Out (FIFO) data structure. Think of a line at a cinema: the person who arrives first is served first. Insertion happens at the rear (or tail), and removal happens at the front (or head). This orderly processing makes queues ideal for scheduling tasks, buffering data, and managing shared resources.
队列是一种先进先出（FIFO）的数据结构。想想电影院排队：最先到达的人最先得到服务。插入操作发生在队尾，移除操作发生在队头。这种有序的处理方式使队列非常适合用于调度任务、缓冲数据以及管理共享资源。
Like stacks, queues can be implemented using arrays or linked lists. However, simple array implementation leads to a problem: after several dequeue operations, the front moves forward and unused spaces appear at the beginning, causing inefficient memory use. This is solved by circular queues.
和栈一样，队列可以使用数组或链表实现。然而，简单的数组实现会导致一个问题：经过几次出队操作后，队头前移，开头出现未使用的空间，导致内存利用率低下。这可以通过循环队列来解决。
5. Core Operations of a Queue | 队列的核心操作
The essential queue operations are enqueue, dequeue, peek (or front), and isEmpty. Enqueue adds an element to the rear of the queue. If the queue has a maximum capacity, you must ensure there is space before enqueuing to avoid overflow.
队列的基本操作是 enqueue（入队）、dequeue（出队）、peek（或 front，查看队头）以及 isEmpty（判断是否为空）。enqueue 将一个元素添加到队尾。如果队列有最大容量，必须在入队前确保有空间以避免溢出。
Dequeue removes and returns the element at the front. If the queue is empty, dequeue should throw an underflow exception or return a sentinel value. Peek returns the front element without removing it, helpful for inspecting the next element to be processed.
dequeue 移除并返回队头元素。如果队列为空，dequeue 应抛出下溢异常或返回一个哨兵值。peek 返回队头元素而不移除它，这对于检查即将处理的下一个元素很有帮助。
isEmpty checks whether the queue currently holds any items. In many designs, a size operation is also available. The time complexity for all these operations is O(1) when implemented efficiently.
isEmpty 检查队列当前是否含有任何项目。在许多设计中，也提供 size 操作。当高效实现时，所有这些操作的时间复杂度都是 O(1)。
Queue complexities: Enqueue O(1), Dequeue O(1), Peek O(1)
队列复杂度：入队 O(1)，出队 O(1)，查看队头 O(1)
6. Circular Queue and Its Operations | 循环队列及其操作
A circular queue, also known as a ring buffer, overcomes the wasted space problem in linear array-based queues. It treats the array as circular by wrapping the rear and front pointers around when they reach the end. Two pointers, front and rear, are maintained. Initially, front = -1 and rear = -1 indicate an empty queue.
循环队列，也称为环形缓冲区，克服了基于线性数组的队列中空间浪费的问题。它通过使队尾和队头指针在到达数组末尾时绕回，从而将数组视为循环结构。维护两个指针：front（队头）和 rear（队尾）。初始时，front = -1 且 rear = -1 表示队列为空。
Enqueue in a circular queue involves moving rear circularly: rear = (rear + 1) % capacity, then placing the item. The first enqueue sets front = rear = 0. Dequeue retrieves the item at front and moves front forward: front = (front + 1) % capacity. When front becomes equal to rear after a dequeue, the queue is considered empty. Full condition is when (rear + 1) % capacity == front.
循环队列中的入队操作涉及循环移动 rear：rear = (rear + 1) % capacity，然后放入元素。第一次入队时设置 front = rear = 0。出队操作取出位于 front 的元素，并将 front 前移：front = (front + 1) % capacity。当出队后 front 等于 rear 时，队列被视为空。满队列的条件是 (rear + 1) % capacity == front。
This clever design allows constant-time enqueue and dequeue without shifting elements. It is widely used in keyboard buffers, printer spooling, and real-time systems where fixed-size buffers are common.
这种巧妙的设计允许在常数时间内进行入队和出队，而无需移动元素。它被广泛用于键盘缓冲区、打印机后台处理以及常见于固定大小缓冲区的实时系统中。
7. Priority Queues and Their Special Operations | 优先队列及其特殊操作
Unlike a regular FIFO queue, a priority queue assigns a priority to each element. The dequeue operation removes the element with the highest priority, regardless of insertion order. This is not a strict linear structure but extends the queue concept. Priority queues are typically implemented using heaps to achieve efficient insertion and removal.
与常规的 FIFO 队列不同，优先队列为每个元素分配一个优先级。dequeue 操作移除具有最高优先级的元素，而不考虑插入顺序。这不是一个严格的线性结构，而是对队列概念的扩展。优先队列通常使用堆来实现，以实现高效的插入和移除。
Operations on a priority queue include insert (enqueue-like), extractMax or extractMin (dequeue-like), and peek. Insertion must place the element in the correct position based on priority, which in a binary heap takes O(log n) time. Extraction also takes O(log n) due to the need to restore the heap property. Peek is O(1).
优先队列上的操作包括 insert（类似入队）、extractMax 或 extractMin（类似出队）以及 peek。插入操作必须根据优先级将元素放置到正确的位置，在二叉堆中这需要 O(log n) 时间。由于需要恢复堆的性质，提取操作也需要 O(log n) 时间。peek 操作是 O(1) 的。
Priority queues are critical in algorithms like Dijkstra’s shortest path, Huffman coding, and task scheduling in operating systems. They differ from simple queues because the next element served is not necessarily the one that has waited the longest.
优先队列在诸如 Dijkstra 最短路径算法、哈夫曼编码以及操作系统中的任务调度等算法中至关重要。它们与简单队列的不同之处在于，下一个被服务的元素不一定是等待时间最长的那个。
8. Implementing Stacks and Queues Using Arrays and Linked Lists | 使用数组和链表实现栈和队列
You can implement a stack using an array by maintaining a top index. Push increments top and stores the value; pop returns the value at top and decrements top. Overflow is checked when top reaches capacity-1; underflow when top is -1. This gives O(1) operations. A dynamic array can be used to grow the stack automatically.
你可以通过维护一个 top 索引来使用数组实现栈。push 操作递增 top 并存储值；pop 操作返回位于 top 的值并递减 top。当 top 达到 capacity-1 时检查溢出；当 top 为 -1 时检查下溢。这实现了 O(1) 操作。动态数组可用于自动增长栈。
For a linked list implementation, push adds a new node at the head of the list (top). Pop removes the head node. No overflow unless memory is exhausted, and underflow occurs if head is null. Both operations remain O(1). Queues can also be implemented with a linked list: enqueue adds a node at the tail, dequeue removes from the head. Maintaining both head and tail pointers ensures O(1) for both ends.
对于链表实现，push 在链表头（栈顶）添加新节点。pop 移除头节点。除非内存耗尽，否则不会溢出；如果 head 为 null，则出现下溢。这两种操作都保持 O(1)。队列也可以用链表实现：enqueue 在尾部添加节点，dequeue 从头部移除。同时维护 head 和 tail 指针可以确保两端的操作都是 O(1)。
| Implementation | Stack | Queue |
|---|---|---|
| Array | Fixed size, O(1) | Circular array preferred, O(1) |
| Linked List | O(1) push/pop at head | O(1) enqueue at tail, dequeue at head |
| 实现方式 | 栈 | 队列 |
|---|---|---|
| 数组 | 固定大小，O(1) | 首选循环数组，O(1) |
| 链表 | 在头部压入/弹出，O(1) | 在尾部入队，在头部出队，O(1) |
9. Comparing Stacks and Queues: Operation Differences | 比较栈和队列：操作差异
Although both are linear and restrict access, the key difference lies in the removal order. A stack removes the most recently added item, while a queue removes the least recently added item. This distinction determines which real-world scenarios they model effectively.
尽管两者都是线性的且限制访问方式，但关键区别在于移除顺序。栈移除最近添加的项目，而队列移除最早添加的项目。这一区别决定了它们能有效建模哪些现实场景。
In stack operations, you talk about top, push, and pop. In queue operations, you refer to front, rear, enqueue, and dequeue. Confusing these terms can cost marks in exams. A useful mnemonic: stack is vertical like a pile of books; queue is horizontal like a waiting line.
在栈的操作中，你谈论的是栈顶、压入和弹出。在队列的操作中，你指的是队头、队尾、入队和出队。混淆这些术语可能会在考试中失分。一个有用的记忆方法是：栈是垂直的，像一摞书；队列是水平的，像一条等候的队伍。
Both can be implemented with similar underlying structures, but the mental model for their behaviour must be clear. When you need to reverse order, think stack; when you need to preserve order, think queue.
两者都可以用类似的底层结构实现，但对其行为的心理模型必须清晰。当你需要反转顺序时，想到栈；当你需要保持顺序时，想到队列。
10. Common Pitfalls and Exam Tips for Operations | 常见陷阱与考试技巧
Examiners often test boundary conditions: empty stack pop, full stack push, empty queue dequeue, and full circular queue enqueue. Drawing diagrams with pointers helps avoid confusion. Always initialise a stack’s top to -1 and a circular queue’s front and rear to -1 when coding from scratch.
考官经常测试边界条件：空栈弹出、满栈压入、空队列出队以及满循环队列入队。绘制带有指针的示意图有助于避免混淆。在从头编写代码时，始终将栈的 top 初始化为 -1，并将循环队列的 front 和 rear 初始化为 -1。
Be aware that in some exam boards, isEmpty is a separate function, while in others the condition is checked inline. Read the question carefully to determine which operations you are allowed to use. When tracing algorithms, show every step of pointer movement and item changes.
请注意，在某些考试局中，isEmpty 是一个独立的函数，而在另一些考试局中，这个条件是内联检查的。仔细阅读题目以确定你可以使用哪些操作。在追踪算法时，要展示指针移动和项目变化的每一步。
For pseudocode answers, use standard names like Push, Pop, Enqueue, Dequeue. Do not forget to handle overflow and underflow where required. If using a linked list, mention you are adding/removing nodes from the head/tail appropriately.
对于伪代码答案，使用标准名称，如 Push、Pop、Enqueue、Dequeue。在需要时，不要忘记处理溢出和下溢。如果使用链表，要提及你正在从头部/尾部适当地添加/移除节点。
11. Real-World Examples and Further Applications | 现实世界的例子与扩展应用
Stacks underpin the ‘undo’ feature in editors, the back button in browsers, and the evaluation of recursive functions. Queues manage print jobs, process scheduling in operating systems, and breadth-first search in graph algorithms. The priority queue variant handles emergency room triage and network packet scheduling.
栈是编辑器中“撤销”功能、浏览器中的后退按钮以及递归函数求值的基础。队列管理打印任务、操作系统中的进程调度以及图算法中的广度优先搜索。优先队列变体则处理急诊室分诊和网络数据包调度。
By mastering stack and queue operations, you build a foundation for understanding more complex abstract data types such as double-ended queues (deque) and trees. Always practice writing operations in pseudocode and high-level languages to solidify your understanding.
通过掌握栈和队列操作，你将为理解更复杂的抽象数据类型（如双端队列和树）打下基础。始终练习用伪代码和高级语言编写操作，以巩固你的理解。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply