📚 Stacks and Queues in IGCSE Computer Science | IGCSE Edexcel 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) that you must master for the IGCSE Edexcel Computer Science exam. This article explains their principles, operations, implementations using both arrays and linked lists, and real-world applications, all directly aligned with the exam specification.
栈和队列是你在 IGCSE Edexcel 计算机科学考试中必须掌握的基本抽象数据类型(ADT)。这篇文章将讲解它们的原理、操作、用数组和链表实现的方法以及实际应用，所有内容都直接紧扣考试大纲。
1. Introduction to Abstract Data Types (ADTs) | 抽象数据类型简介
An abstract data type (ADT) is a logical description of how data is viewed and the operations that can be performed on it, without specifying the underlying implementation. Stacks and queues are classic examples of ADTs because they are defined by their behaviours (LIFO and FIFO) rather than by a specific code structure.
抽象数据类型(ADT)是对数据如何被看待以及可以对数据执行哪些操作的逻辑描述，而不规定底层的实现方式。栈和队列是 ADT 的经典例子，因为它们由自身的行为（后进先出和先进先出）来定义，而不是由某种具体的代码结构来定义。
2. The Stack Data Structure | 栈数据结构
A stack is a collection of items that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you can only take the top plate off the pile, and when you add a new plate, it goes onto the top. The last item added to the stack is always the first one to be removed.
栈是一种遵循后进先出（LIFO）原则的数据项集合。想象一摞盘子：你只能从顶部拿走最上面的盘子，而添加一个新盘子时，它会被放在顶部。最后加入栈中的项总是最先被移除的那一个。
3. Stack Operations: Push and Pop | 栈操作：压栈和弹栈
The two primary operations on a stack are push and pop. A push operation adds a new item onto the top of the stack. A pop operation removes the item currently at the top of the stack and typically returns it. If you try to pop from an empty stack, a stack underflow error occurs.
栈的两个主要操作是压栈（push）和弹栈（pop）。压栈操作将一个新项添加到栈的顶端。弹栈操作移除当前处于栈顶的项，并通常将其返回。如果你尝试从一个空栈中进行弹出，就会发生栈下溢错误。
When implementing push, the size of the stack increases by one. When implementing pop, the size decreases by one. Some languages or exam scenarios treat pop as simply removing the top item without returning it; always read the question context carefully.
执行压栈时，栈的大小会增加 1。执行弹栈时，大小会减少 1。某些编程语言或考试情境中，弹出只是移除栈顶元素而不返回它；请务必仔细阅读题目背景。
4. Stack Peek and Auxiliary Operations | 栈的查看与其他辅助操作
Besides push and pop, stacks usually provide a peek (or top) operation, which returns the value of the top item without removing it. This is useful when you need to inspect the next item to be popped without changing the stack’s state. Other helper operations include isEmpty (returns true if the stack contains no elements) and isFull (returns true if a fixed-size array implementation has reached its maximum capacity).
除了压栈和弹栈，栈通常还提供一个查看操作（peek 或 top），它返回栈顶元素的值但不移除它。当你需要检查下一个即将弹出的元素而又不改变栈的状态时，该操作非常有用。其他辅助操作还包括 isEmpty（如果栈中没有元素则返回 true）和 isFull（如果固定大小的数组实现已达到最大容量则返回 true）。
5. Implementing a Stack Using an Array | 用数组实现栈
An array-based stack uses a fixed-size array and a variable called a stack pointer (often named top) that stores the index of the current top element. A push operation increments the pointer and places the new item at that index. A pop operation reads the item at the pointer index and then decrements the pointer.
基于数组的栈使用一个固定大小的数组和一个名为栈指针（通常称为 top）的变量，该变量存储当前栈顶元素的索引。压栈操作会递增指针，并将新项放到该索引处。弹栈操作会读取指针索引处的项，然后递减指针。
You must always check for overflow (push when stack is full) and underflow (pop when stack is empty). A simple array stack works perfectly for situations where the maximum number of elements is known in advance, for example when evaluating expressions with a known depth.
你必须始终检查溢出（栈满时压栈）和下溢（栈空时弹栈）。当最大元素数量事先已知时，简单的数组栈能很好地工作，例如在评估已知深度的表达式时。
6. Implementing a Stack Using a Linked List | 用链表实现栈
A linked-list stack uses dynamic memory allocation, where each node contains the data and a pointer to the next node. The top of the stack corresponds to the head of the linked list. A push creates a new node, makes its next pointer point to the current top, and updates the top pointer to the new node. A pop moves the top pointer to the next node and frees (or ignores) the old top node.
基于链表的栈使用动态内存分配，每个节点包含数据和一个指向下一节点的指针。栈顶对应着链表的头。压栈创建一个新节点，使其 next 指针指向当前栈顶，并将栈顶指针更新为新节点。弹栈则将栈顶指针移动到下一个节点，并释放（或忽略）原来的栈顶节点。
A linked-list implementation never suffers from a fixed capacity limit, so overflow only occurs when system memory is exhausted. This makes it more flexible than the array approach, but the code is slightly more complex to manage pointers correctly.
基于链表的实现不会受到固定容量限制，因此只有在系统内存耗尽时才会发生溢出。这使得它比数组方法更加灵活，但为了正确管理指针，代码也会稍微复杂一些。
7. Applications of Stacks | 栈的应用
Stacks appear in many computing scenarios. The call stack used by most programming languages stores return addresses and local variables when functions are called. When a function returns, its frame is popped from the call stack. This is exactly how recursion and nested subroutine calls are managed.
栈出现在许多计算场景中。大多数编程语言使用的调用栈会在函数被调用时存储返回地址和局部变量。当一个函数返回时，它的栈帧就会从调用栈中弹出。这正是递归和嵌套子程序调用被管理的方式。
- Expression evaluation: converting infix to postfix and evaluating postfix expressions uses stacks.
- 表达式求值：将中缀表达式转换为后缀表达式并对后缀表达式求值都用到栈。
- Undo functions in editors: each action is pushed onto a stack; the undo operation pops the most recent action.
- 编辑器中的撤销功能：每一次操作都被压入栈中；撤销操作则弹出最近的一次操作。
- Backtracking algorithms, e.g., maze solving: the path is pushed and popped as the algorithm tries different routes.
- 回溯算法，例如迷宫求解：当算法尝试不同路径时，路径会被压栈和弹栈。
8. The Queue Data Structure | 队列数据结构
A queue is a collection that follows the First In, First Out (FIFO) principle. Picture a line of people waiting for a bus: the person who has been waiting the longest is the first to board. Similarly, items are added at the rear of the queue and removed from the front.
队列是一种遵循先进先出（FIFO）原则的集合。想象一队等候公交车的人：等待时间最长的人最先上车。类似地，数据项被添加到队列的尾部，并从队首移除。
9. Queue Operations: Enqueue and Dequeue | 队列操作：入队和出队
The enqueue operation adds an item to the rear of the queue. The dequeue operation removes and returns the item at the front of the queue. Attempting to dequeue from an empty queue causes a queue underflow error. Just like stacks, queues often provide peek to look at the front item without removal, as well as isEmpty and isFull checks.
入队操作将一个项目添加到队列的尾部。出队操作移除并返回位于队首的项目。试图从空队列中执行出队操作会导致队列下溢错误。与栈一样，队列通常也提供查看操作来查看队首项目而不将其移除，同时还提供 isEmpty 和 isFull 检查。
For the IGCSE Edexcel exam, remember to describe the movement of two pointers: the front pointer (pointing to the first occupied slot/the item to be dequeued next) and the rear pointer (pointing to the last occupied slot/the position where the next item will be enqueued).
对于 IGCSE Edexcel 考试，要记得描述两个指针的移动：队首指针（指向第一个已占用位置/下一个将要出队的项目）和队尾指针（指向最后一个已占用位置/下一个项目将要入队的位置）。
10. Implementing a Queue Using an Array (Linear and Circular) | 用数组实现队列（线性与循环）
A simple linear array implementation uses a fixed-size array with a front and rear index. However, as items are dequeued, the front moves forward, leaving empty spaces at the beginning that cannot be reused. This leads to a false overflow condition where the queue appears full even though free spaces exist at the front.
一个简单的线性数组实现使用一个固定大小的数组，并配有队首索引和队尾索引。然而，随着项目不断出队，队首不断前移，导致数组开头留下不可再利用的空位。这会导致假溢出情况，即队列看起来已满，但实际上队首处仍然存在空闲位置。
The solution is a circular queue, where the array is treated as a circle. When the rear pointer reaches the end of the array, it wraps around to index 0 if that position is free. The queue is full only when the next slot for the rear is the front pointer (or a count variable is used). The IGCSE specification expects you to understand the circular queue concept and the condition for full vs. empty states.
解决方法就是循环队列，即将数组视作一个环形。当队尾指针到达数组末尾时，如果索引 0 的位置空闲，它就会绕回至索引 0。只有当队尾的下一个位置就是队首指针时（或者使用计数变量），队列才为满。IGCSE 大纲要求你理解循环队列的概念以及判满和判空的条件。
| State | Condition (using count) | Condition (without count) |
| Queue empty | count = 0 | front = rear (often set to -1 initially) |
| Queue full | count = array size | (rear + 1) mod size = front |
Circular Queue State Conditions
循环队列状态判断条件
11. Implementing a Queue Using a Linked List | 用链表实现队列
With a linked list, a queue is built from nodes where the list maintains both a head pointer (front) and a tail pointer (rear). Enqueue creates a new node at the tail and updates the tail pointer. Dequeue removes the node at the head and updates the head pointer. This implementation has no fixed capacity limitation and naturally avoids the wasted space problem of a linear array.
使用链表时，队列由节点构建而成，链表同时维护一个头指针（队首）和一个尾指针（队尾）。入队在尾部创建一个新节点并更新尾指针。出队移除头部的节点并更新头指针。这种实现方式没有固定的容量限制，并从根本上避免了线性数组的空间浪费问题。
When drawing or describing a linked-list queue for an exam answer, always label the head (front) and tail (rear) clearly and show how enqueue and dequeue adjust these pointers. The linked-list approach is efficient because both enqueue and dequeue take constant time, O(1).
在为考试作答而绘制或描述链表队列时，务必清晰地标出头指针（队首）和尾指针（队尾），并展示入队和出队如何调整这些指针。链表方法非常高效，因为入队和出队都只需要常数时间，即 O(1)。
12. Applications of Queues | 队列的应用
Queues are used extensively in operating systems and networking. A print spooler keeps print jobs in a queue, processing them in the order they were submitted. Keyboard buffers store keystrokes in a queue so that even if the CPU is temporarily busy, no keystrokes are lost; they are dequeued and processed later.
队列在操作系统和网络中被广泛使用。打印后台处理程序将打印作业保留在一个队列中，按它们提交的顺序进行处理。键盘缓冲区将按键以队列形式存储，因此即使 CPU 暂时忙碌，也不会丢失任何按键；它们稍后会被出队并处理。
- CPU scheduling: processes waiting for the CPU are placed in ready queues.
- CPU 调度：等待 CPU 的进程被放入就绪队列。
- Breadth-first search (BFS) in graphs uses a queue to explore nodes level by level.
- 图的广度优先搜索（BFS）使用队列逐层探索节点。
- Simulations of real-world lines: banks, supermarkets, and call centres model customer waiting lines using queues.
- 对现实世界排队场景的模拟：银行、超市和呼叫中心都使用队列来对顾客等候队伍进行建模。
For your IGCSE exam, be able to suggest a suitable data structure for a given scenario. If data must be processed in the order it arrives, a queue is the correct choice. If the most recently added item must be processed first, a stack is the appropriate ADT.
在你的 IGCSE 考试中，要能够为给定的场景建议合适的数据结构。如果数据必须按照到达顺序进行处理，队列是正确的选择。如果最近添加的项必须最先被处理，栈就是适合的 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课程辅导，国外大学本科硕士研究生博士课程论文辅导