📚 Stack and Queue: Exam Revision Essentials | IB Edexcel 计算机：栈与队列 考点精讲
Stack and queue are fundamental linear data structures in computer science, essential for managing data in an ordered collection. They appear frequently in IB (International Baccalaureate) Computer Science as well as Edexcel IAL/GCSE specifications. Understanding their abstract data types (ADT), operations, typical implementations, and applications is crucial for both theoretical and practical exams. This article provides a focused revision guide covering key concepts, operations, complexity analysis, and classic problems, helping you master stacks and queues with confidence.
栈和队列是计算机科学中基本的线性数据结构，用于管理有序集合中的数据。它们在IB国际文凭课程和Edexcel IAL/GCSE计算机科学考试中频繁出现。理解抽象数据类型（ADT）、操作、典型实现方式以及应用场景，对于理论和实践考试都至关重要。这篇文章提供一份考点精讲，涵盖核心概念、操作、复杂度分析和经典问题，帮助你有信心地掌握栈与队列。
1. Stack ADT and LIFO Principle | 栈的抽象数据类型与后进先出原则
A stack is an abstract data type that follows the Last In, First Out (LIFO) principle. Elements are added to and removed from the same end, called the top of the stack. Think of a stack of plates: you can only take the plate from the top, and you place new plates on top. In computing, the stack is used to manage data where the most recently added item is the first to be processed.
栈是一种遵循后进先出（LIFO）原则的抽象数据类型。元素从同一端添加和移除，这一端称为栈顶。想象一摞盘子：你只能从顶部取盘子，新盘子也只能放在顶部。在计算中，栈用于管理那些最近添加的项目需要最先被处理的数据。
- Key characteristic: LIFO order.
- 关键特征：后进先出顺序。
- Operations: push, pop, peek/top, isEmpty, isFull (for bounded stacks).
- 操作：入栈（push）、出栈（pop）、取栈顶（peek/top）、判空（isEmpty）、判满（isFull，用于有界栈）。
2. Queue ADT and FIFO Principle | 队列的抽象数据类型与先进先出原则
A queue is an ADT that follows the First In, First Out (FIFO) principle. Elements are added at one end, called the rear (or tail), and removed from the other end, called the front (or head). This mirrors a real-world queue of people waiting in line: the first person to join is the first one to leave. Queues are widely used for scheduling, buffering, and handling asynchronous data.
队列是一种遵循先进先出（FIFO）原则的抽象数据类型。元素在称为队尾（rear）的一端添加，从称为队首（front）的另一端移除。这就像现实生活中排队等候的人群：最先加入队列的人最先离开。队列被广泛用于调度、缓冲和处理异步数据。
- Key characteristic: FIFO order.
- 关键特征：先进先出顺序。
- Operations: enqueue, dequeue, front/peek, isEmpty, isFull.
- 操作：入队（enqueue）、出队（dequeue）、取队首（front/peek）、判空、判满。
3. Core Operations: Push, Pop, Peek (Stack) | 核心操作：入栈、出栈、取栈顶
The fundamental stack operations are push, pop, and peek. Push adds an element to the top; pop removes the top element and usually returns its value; peek returns the top element without removing it. All these operations must handle boundary conditions such as stack underflow (pop/peek on empty) and overflow (push on full fixed-size stack).
栈的基本操作是入栈、出栈和取栈顶。入栈将元素添加到栈顶；出栈移除栈顶元素并通常返回其值；取栈顶返回栈顶元素但不移除它。所有这些操作都必须处理边界条件，例如栈下溢（空栈执行出栈/取顶）和上溢（满栈执行入栈）。
| Operation | Description | Time Complexity |
|---|---|---|
| push(item) | Add item to top | O(1) |
| pop() | Remove and return top item | O(1) |
| peek() | Return top item without removal | O(1) |
| isEmpty() | Check if stack has no elements | O(1) |
4. Core Operations: Enqueue, Dequeue, Front (Queue) | 核心操作：入队、出队、取队首
Queue operations are enqueue (add to rear), dequeue (remove from front), and front/peek (retrieve front element without removal). Like stacks, most implementations provide O(1) time complexity for these operations, making queues highly efficient for FIFO data handling. Care must be taken to avoid underflow or overflow errors in fixed-size implementations.
队列操作包括入队（添加到队尾）、出队（从队首移除）和取队首（获取队首元素但不移除）。与栈类似，大多数实现都为这些操作提供O(1)的时间复杂度，使得队列在FIFO数据处理方面非常高效。在固定大小的实现中必须注意避免下溢或上溢错误。
| Operation | Description | Time Complexity |
|---|---|---|
| enqueue(item) | Add item to rear | O(1) |
| dequeue() | Remove and return front item | O(1) |
| front() | Return front item without removal | O(1) |
| isEmpty() | Check if queue is empty | O(1) |
5. Implementing a Stack with Arrays and Linked Lists | 用数组和链表实现栈
A stack can be implemented using an array (static) or a linked list (dynamic). In an array-based stack, a fixed-size array holds the elements, and an integer variable ‘top’ tracks the index of the topmost element. Pushing increments top and stores the item; popping retrieves the item at top and decrements top. The array approach is memory-efficient but suffers from a fixed capacity – overflowing when full.
栈可以用数组（静态）或链表（动态）来实现。在基于数组的栈中，一个固定大小的数组存储元素，一个整型变量’top’跟踪栈顶元素的索引。入栈操作增加top并存储元素；出栈操作获取top处的元素并减小top。数组方式内存效率高，但受限于固定容量——满时会发生上溢。
With a linked list, each node contains data and a pointer to the next node. The top pointer always references the head of the list. Pushing creates a new node and inserts it at the head; popping removes the head node. This eliminates overflow issues (until system memory is exhausted) and allows dynamic resizing, which is beneficial in situations where the maximum size cannot be determined in advance.
使用链表时，每个节点包含数据和指向下一个节点的指针。栈顶指针始终引用链表头。入栈创建一个新节点并将其插入到头部；出栈移除头部节点。这消除了上溢问题（直到系统内存耗尽），并允许动态调整大小，在无法预先确定最大容量的情况下非常有益。
6. Implementing a Queue with Arrays and Linked Lists | 用数组和链表实现队列
An array-based queue uses a fixed-size array with two pointers: front and rear. Enqueuing adds an element at rear and increments rear; dequeuing removes from front and increments front. This simple linear approach wastes space because once an element is dequeued, its slot cannot be reused, leading to the ‘false overflow’ problem when the rear reaches the array end but the front has moved forward.
基于数组的队列使用固定大小的数组以及两个指针：front和rear。入队在rear处添加元素并递增rear；出队从front处移除元素并递增front。这种简单的线性方法会浪费空间，因为一旦元素出队，其槽位无法被重用，导致rear到达数组末尾但front已前移时的“假溢出”问题。
To solve this, a circular queue (discussed next) is often used. A linked-list implementation of a queue maintains front and rear pointers to the first and last nodes respectively. Enqueuing inserts a node at the rear, dequeuing removes the head node. This dynamic approach avoids capacity limits entirely and is straightforward to code. Exam questions may ask you to trace or implement queue operations using either method.
为解决这个问题，通常使用循环队列（下一节讨论）。队列的链表实现维护指向第一个和最后一个节点的front和rear指针。入队操作在rear处插入节点，出队操作删除头节点。这种动态方式完全避免了容量限制，并且编码简单。试题可能要求你追踪或用任一方法实现队列操作。
7. Circular Queue and its Advantages | 循环队列及其优点
A circular queue treats the underlying array as circular: when the rear pointer reaches the last index, it wraps around to index 0 if the front has advanced. This allows efficient reuse of slots vacated by dequeue operations. It is also called a ring buffer. The queue is considered full when the next position of rear equals front (commonly using (rear+1) % arraySize == front), sacrificing one slot to distinguish between empty and full conditions.
循环队列将底层数组视为环状：当rear指针到达最后一个索引时，如果front已前移就绕回索引0。这使得出队操作空出的槽位能被高效重用。它也被称为环形缓冲区。当rear的下一个位置等于front时（通常使用(rear+1) % arraySize == front）队列被视为满，牺牲一个槽位以区分空和满的状态。
The main advantage is memory efficiency within a fixed size, preventing false overflow. In IB and Edexcel exams, you may be asked to draw the state of a circular queue after a series of operations or to calculate indices. Time complexity of enqueue and dequeue remains O(1).
主要优点是在固定大小内实现内存高效，防止假溢出。在IB和Edexcel考试中，你可能需要画出一系列操作后循环队列的状态，或计算索引。入队和出队的时间复杂度仍然为O(1)。
8. Priority Queue ADT | 优先队列抽象数据类型
A priority queue is an abstract data type where each element has a priority value. Elements with higher priority are dequeued before those with lower priority, regardless of their insertion order. If two elements share the same priority, they are served according to FIFO order (stable priority queue). Priority queues are not strict FIFO like standard queues.
优先队列是一种抽象数据类型，其中每个元素都有一个优先级值。优先级较高的元素比较低优先级元素更早出队，无论它们插入的顺序如何。如果两个元素具有相同优先级，则按照FIFO顺序服务（稳定优先队列）。优先队列不像标准队列那样严格遵循FIFO。
Common implementations include using a heap (binary heap gives O(log n) for insert and delete), or an unordered/ordered array or linked list (tradeoffs between O(1) insert/O(n) delete or vice versa). In exams you should know the conceptual behaviour and typical applications like task scheduling and Dijkstra’s algorithm.
常见实现包括使用堆（二叉堆使得插入和删除的复杂度为O(log n)），或无序/有序数组或链表（在O(1)插入/O(n)删除之间权衡，反之亦然）。在考试中应了解其概念行为和典型应用，如任务调度和Dijkstra算法。
9. Double-Ended Queue (Deque) | 双端队列
A deque (double-ended queue) allows insertion and deletion at both ends. It generalises both stack and queue: it can behave LIFO, FIFO, or a mix. Operations include addFront, addRear, removeFront, removeRear. This flexibility makes deques useful in certain algorithms, such as maintaining a sliding window maximum or implementing undo/redo functionality.
双端队列（deque）允许在两端进行插入和删除。它推广了栈和队列：可以表现为LIFO、FIFO或混合模式。操作包括前端添加、后端添加、前端移除、后端移除。这种灵活性使得双端队列在某些算法中非常有用，例如维护滑动窗口最大值或实现撤销/重做功能。
In coursework or paper-based exams, you may need to compare a deque with a stack or queue, and highlight when a deque would be more efficient. Implementations can be done with arrays (circular) or doubly linked lists, giving O(1) operations at both ends.
在课程作业或笔试中，你可能需要比较双端队列与栈或队列，并强调何时使用双端队列会更高效。可以用数组（循环）或双向链表实现，在两端都提供O(1)操作。
10. Stack Applications: Function Calls & Recursion | 栈的应用：函数调用与递归
One of the most important applications of a stack is managing function calls in programming languages. Each time a function is invoked, a stack frame (containing parameters, local variables, and return address) is pushed onto the call stack. When the function returns, its frame is popped. This mechanism supports nested and recursive function calls naturally, where the last called function must finish first.
栈最重要的应用之一是管理编程语言中的函数调用。每次调用函数时，一个栈帧（包含参数、局部变量和返回地址）会压入调用栈。当函数返回时，其栈帧被弹出。这种机制自然地支持嵌套和递归函数调用，即最后调用的函数必须最先完成。
Recursion relies entirely on the call stack. For example, factorial calculation n! = n × (n-1)! results in multiple pauses of the executing function while a new call is made. If the recursion is too deep without a base case, the stack overflows. IB/Edexcel exam questions may ask you to trace the stack content during recursive execution.
递归完全依赖调用栈。例如，阶乘计算 n! = n × (n-1)! 会导致执行函数多次暂停，同时进行新的调用。如果递归太深且没有基本情况，栈会溢出。IB/Edexcel的试题可能要求你跟踪递归执行期间栈的内容。
11. Stack Applications: Expression Evaluation & Syntax Parsing | 栈的应用：表达式求值与语法解析
Stacks are used to evaluate arithmetic expressions, convert between infix, postfix, and prefix notations, and check balanced parentheses. For instance, the infix expression (A + B) × (C – D) can be converted to postfix A B + C D – × using the Shunting-yard algorithm with a stack. Evaluating a postfix expression requires one stack: push operands; when an operator is encountered, pop two operands, apply the operator, push the result.
栈用于求值算术表达式，在中缀、后缀和前缀表示法之间转换，并检查括号是否平衡。例如，中缀表达式 (A + B) × (C – D) 可以通过使用栈的调车场算法转换为后缀表达式 A B + C D – ×。求值后缀表达式需要一个栈：将操作数入栈；遇到运算符时，弹出两个操作数，应用运算符，将结果压栈。
Bracket matching is another classic problem: scan the string character by character, push opening brackets onto a stack, and when a closing bracket is encountered, pop the stack and check if it matches. Any mismatch or unterminated bracket triggers an error. This technique appears in compilers and syntax checkers.
括号匹配是另一个经典问题：逐个字符扫描字符串，将开括号推入栈，遇到闭括号时弹出栈顶并检查是否匹配。任何不匹配或未终止的括号都会触发错误。这种技术出现在编译器和语法检查器中。
12. Queue Applications: Scheduling and Buffering | 队列的应用：调度与缓冲
Queues are fundamental in operating systems and networking for scheduling processes, managing print spools, and buffering data streams. A CPU scheduler often uses a ready queue to hold processes awaiting execution; they are dispatched in FIFO order (or priority-based). Similarly, keyboard input buffers and message queues in inter-process communication rely on queue behaviour.
队列是操作系统和网络中用于调度进程、管理打印假脱机以及缓冲数据流的基础。CPU调度器通常使用就绪队列来存放等待执行的进程；它们按照FIFO顺序（或基于优先级）分派。同样，键盘输入缓冲区和进程间通信的消息队列也依赖队列行为。
In simulation, queues model real-world scenarios such as customer service lines, call centres, or packet routing. Understanding queue ADT allows programmers to design fair and efficient systems. Exam questions may involve tracing values through a queue or justifying the choice of a queue over a stack in a given application.
在模拟中，队列对现实世界场景建模，如客户服务排队、呼叫中心或数据包路由。理解队列ADT使得程序员能够设计公平高效的系统。考题可能涉及通过队列追踪数值，或在给定应用中解释选择队列而非栈的理由。
Published by TutorHao | 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