📚 GCSE CCEA Computer Science: Stacks and Queues Explained | GCSE CCEA 计算机：栈与队列 考点精讲
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last element added to the stack is the first one to be removed. You can think of it as a stack of plates: you can only take the top plate off and you can only add a new plate to the top. In programming, a stack is an abstract data type (ADT) with a fixed set of operations such as push, pop, and peek. Understanding stacks is fundamental for your GCSE CCEA Computer Science exam because they model memory management, expression evaluation, and undo mechanisms.
栈是一种遵循后进先出（LIFO）原则的线性数据结构。最后加入的元素最先被移除。你可以把它想象成一摞盘子：只能从顶部取走盘子，也只能把新盘子放在顶部。在编程中，栈是一种抽象数据类型（ADT），拥有一组固定的操作，比如压入（push）、弹出（pop）和查看栈顶（peek）。理解栈对于你的 GCSE CCEA 计算机科学考试至关重要，因为栈被用于模拟内存管理、表达式求值和撤销机制。
1. What is a Stack? | 什么是栈？
A stack is a collection of elements with two principal operations: push, which adds an item to the collection, and pop, which removes the most recently added item. The LIFO behaviour means that elements are accessed in reverse order of their insertion. In memory terms, a stack can be implemented using a static array, where the maximum size is fixed, or a dynamic structure such as a linked list, which can grow as needed. For GCSE CCEA, you will typically work with a stack implemented as an array with a pointer called ‘top’ that tracks the index of the most recent element.
栈是一个元素的集合，主要有两种操作：压入（push）将一个元素加入集合，弹出（pop）移除最近加入的元素。后进先出的行为意味着元素的访问顺序与插入顺序相反。从内存角度看，栈可以用静态数组实现（最大容量固定），也可以用动态结构（如链表）实现，链表可以根据需要动态增长。在 GCSE CCEA 考试中，你通常需要处理用数组实现的栈，并用一个名为 ‘top’ 的指针来跟踪最新元素的索引。
2. Stack Operations and Their Pseudocode | 栈的操作及其伪代码
The core operations on a stack are: push(item) – adds an item to the top of the stack, pop() – removes and returns the top item, peek() – returns the top item without removing it, isEmpty() – returns true if the stack contains no elements, and isFull() – returns true if the stack has reached its maximum capacity. In pseudocode, a stack can be represented with an array named ‘stack’ and an integer ‘top’ initialised to –1. Before pushing, you must check isFull() to avoid overflow; before popping, you must check isEmpty() to avoid underflow.
栈的核心操作包括：push(item) – 将一个元素添加到栈顶，pop() – 移除并返回栈顶元素，peek() – 返回栈顶元素但不移除，isEmpty() – 如果栈中没有元素则返回 true，isFull() – 如果栈已达到最大容量则返回 true。在伪代码中，栈可以用一个名为 ‘stack’ 的数组和一个初始值为 –1 的整数 ‘top’ 来表示。在压入之前，必须检查 isFull() 以避免溢出；在弹出之前，必须检查 isEmpty() 以避免下溢。
3. Stack Push and Pop Step‑by‑Step | 栈的压入与弹出逐步示例
Imagine a stack of maximum size 5 implemented as an array. Initially, top = –1. When you push(10), top becomes 0 and stack[0] = 10. Push(20): top = 1, stack[1] = 20. Push(30): top = 2, stack[2] = 30. Now the stack contains [10, 20, 30] from bottom to top. If you call pop(), the value 30 is returned and top is decremented to 1, effectively removing 30 from the stack. Pop again returns 20, top becomes 0. The order of removal is the reverse of insertion, perfectly demonstrating LIFO.
设想一个最大容量为 5 的栈，用数组实现。初始时，top = –1。当你执行 push(10) 后，top 变为 0，stack[0] = 10。push(20)：top = 1，stack[1] = 20。push(30)：top = 2，stack[2] = 30。此时栈从底到顶包含 [10, 20, 30]。如果调用 pop()，返回值 30，top 减为 1，相当于从栈中移除了 30。再次 pop 返回 20，top 变为 0。移除的顺序与插入顺序相反，完美展示了后进先出。
4. Real‑World Applications of Stacks | 栈的实际应用
Stacks are used extensively in computer systems. One key application is the call stack in program execution, where function calls are pushed onto the stack when invoked, and popped when they return, preserving local variables and return addresses. Another common use is the undo feature in text editors and graphic software: each action is pushed onto a stack, and undo pops the last action to reverse it. Stacks are also employed in evaluating mathematical expressions, especially in converting infix to postfix notation and in browsing history where the back button pops the previous page.
栈在计算机系统中被广泛使用。一个关键应用是程序执行中的调用栈，函数调用时被压入栈，返回时被弹出，从而保存局部变量和返回地址。另一个常见用途是文本编辑器和图形软件中的撤销功能：每个操作都被压入栈，撤销操作则弹出最后的操作以将其还原。栈还用于数学表达式求值，特别是在将中缀表达式转换为后缀表达式时，以及浏览器历史记录中，后退按钮会弹出上一个页面。
5. What is a Queue? | 什么是队列？
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The first element added to the queue is the first one to be removed, much like a line of people waiting at a bus stop. A queue has a front pointer, indicating the next element to leave, and a rear pointer, indicating where new elements are added. In CCEA GCSE Computer Science, queues are important for simulations, scheduling tasks, and managing data streams. You need to understand both linear queues and the more efficient circular queue implementation.
队列是一种遵循先进先出（FIFO）原则的线性数据结构。最先加入队列的元素最先被移除，就像人们在公交站排队一样。队列有一个 front 指针，指向下一个将要离开的元素，还有一个 rear 指针，指向新元素加入的位置。在 CCEA GCSE 计算机科学中，队列对于模拟系统、任务调度和管理数据流非常重要。你需要理解线性队列，以及更高效的循环队列实现。
6. Queue Operations and Essential Checks | 队列操作与必要检查
The fundamental queue operations are: enqueue(item) – adds an item to the rear of the queue, dequeue() – removes and returns the item at the front, peekFront() – returns the front item without removing it, isEmpty() – checks if the queue is empty, and isFull() – checks if the queue has no available space. In a linear queue implemented with an array, pointers front and rear are often initialised to –1. When the first element is enqueued, both front and rear become 0. After several operations, the rear may reach the maximum index even if front has moved forward, creating the problem of unused space at the beginning of the array.
队列的基本操作包括：enqueue(item) – 将一个元素加入队列的尾部，dequeue() – 移除并返回队首的元素，peekFront() – 返回队首元素但不移除，isEmpty() – 检查队列是否为空，isFull() – 检查队列是否已无可用空间。在用数组实现的线性队列中，指针 front 和 rear 通常初始化为 –1。当第一个元素入队时，front 和 rear 都变为 0。经过若干次操作后，即使 front 已经前移，rear 可能还是到达了数组的最大索引，导致数组开始处出现未使用的空间，造成浪费。
7. Linear Queue Example with an Array | 使用数组的线性队列示例
Consider a queue that can hold up to 5 integers. Initially, front = –1, rear = –1. Enqueue(5): front = 0, rear = 0, queue[0] = 5. Enqueue(8): rear = 1, queue[1] = 8. Enqueue(3): rear = 2, queue[2] = 3. The queue stores [5, 8, 3] with front at index 0 and rear at index 2. Now dequeue(): the value 5 is returned and front becomes 1. After another dequeue (returns 8), front is 2, rear remains 2. The element 3 is still at index 2, but the space at indices 0 and 1 is now free but cannot be reused unless we shift elements or use a circular queue.
考虑一个最多可容纳 5 个整数的队列。初始时，front = –1，rear = –1。Enqueue(5)：front = 0，rear = 0，queue[0] = 5。Enqueue(8)：rear = 1，queue[1] = 8。Enqueue(3)：rear = 2，queue[2] = 3。队列存储了 [5, 8, 3]，front 在索引 0，rear 在索引 2。现在 dequeue()：返回值 5，front 变为 1。再一次 dequeue（返回 8）后，front 为 2，rear 仍为 2。元素 3 仍在索引 2，但索引 0 和 1 的空间现在空闲，却无法被重新利用，除非我们将元素移位或使用循环队列。
8. Circular Queues – Solving Linear Queue Limitations | 循环队列 —— 解决线性队列的局限
A circular queue connects the rear of the array back to the front, forming a circle. The rear pointer wraps around to index 0 when it reaches the end, provided there is available space. This reuses the freed slots without moving elements. The formula for advancing the rear pointer after an enqueue is: rear = (rear + 1) MOD size. For the front pointer after a dequeue: front = (front + 1) MOD size. The queue is empty when front = –1 (or when front equals rear after a reset), but often a count variable is used to distinguish between full and empty states, as front and rear values alone can be ambiguous.
循环队列将数组的尾部和头部连接起来，形成一个环状。当 rear 指针到达数组末尾时，如果还有可用空间，它会绕回到索引 0。这样就无需移动元素即可重用已释放的槽位。入队后 rear 指针前进的公式为：rear = (rear + 1) MOD size。出队后 front 指针前进的公式为：front = (front + 1) MOD size。当 front = –1（或者在重置后 front 等于 rear）时队列为空，但通常使用一个计数器变量来区分队列是满还是空，因为仅凭 front 和 rear 的值可能会产生歧义。
9. Comparing Stacks and Queues | 栈与队列的比较
Both stacks and queues are linear data structures that store elements sequentially, but they differ in access policy. Stack is LIFO, while queue is FIFO. Stacks use a single pointer (top), whereas queues require two pointers (front and rear). In practice, stacks are preferred for depth‑first search and backtracking; queues are used for breadth‑first search and buffering. Stacks are simpler to implement and are often built into the processor hardware (the stack pointer register). Queues are fundamental in operating systems for job scheduling and print spooling.
栈和队列都是线性数据结构，按顺序存储元素，但它们的访问策略不同。栈是 LIFO，而队列是 FIFO。栈只使用一个指针（top），而队列需要两个指针（front 和 rear）。在实际应用中，栈常用于深度优先搜索和回溯算法；队列则用于广度优先搜索和缓冲。栈实现起来更简单，且往往被内置于处理器硬件中（堆栈指针寄存器）。队列在操作系统中对于作业调度和打印池来说是基础性的。
10. Exam‑Style Practice Question and Worked Solution | 真题风格练习题与解答
Question: A queue is implemented as a circular array of size 4. Initially the queue is empty. The following operations are performed in order: enqueue(7), enqueue(2), dequeue(), enqueue(9), enqueue(4), enqueue(1). The circular queue uses the convention that the queue is full when (rear + 1) MOD size = front. Show the state of the array and the values of front and rear after each operation, and identify whether any operations fail.
问题：一个队列被实现为大小为 4 的循环数组。初始时队列为空。按顺序执行下列操作：enqueue(7), enqueue(2), dequeue(), enqueue(9), enqueue(4), enqueue(1)。该循环队列约定，当 (rear + 1) MOD size = front 时队列为满。给出每次操作后数组的状态以及 front 和 rear 的值，并指出是否有操作失败。
Solution: Start with front = 0, rear = 0 (or front = rear = 0 indicating empty). After enqueue(7): rear becomes 1, queue[0]=7, front=0, rear=1. Enqueue(2): rear=2, queue[1]=2. Dequeue(): removes element at front=0 (value 7), front becomes 1. Enqueue(9): rear=(2+1) mod 4 = 3, queue[2]=9. Enqueue(4): rear=(3+1) mod 4 = 0, queue[3]=4. Now front=1, rear=0. Check full condition before enqueue(1): (rear+1) mod 4 = (0+1)=1, which equals front (1). So the queue is full and the enqueue(1) operation fails with an overflow error. The final array holds [7 (unused), 2, 9, 4] where index 0 still holds 7 but is not part of the logical queue.
解答：开始时 front = 0, rear = 0（或者 front = rear = 0 表示空）。enqueue(7) 后：rear 变为 1，queue[0]=7，front=0，rear=1。Enqueue(2)：rear=2，queue[1]=2。Dequeue()：移除 front=0 处的元素（值 7），front 变为 1。Enqueue(9)：rear=(2+1) mod 4 = 3，queue[2]=9。Enqueue(4)：rear=(3+1) mod 4 = 0，queue[3]=4。此时 front=1，rear=0。在 enqueue(1) 之前检查满的条件：(rear+1) mod 4 = (0+1)=1，等于 front (1)，因此队列已满，enqueue(1) 操作失败并产生溢出错误。最终的数组存储了 [7（未使用）, 2, 9, 4]，其中索引 0 仍存有 7 但不属于逻辑队列。
11. Common Pitfalls and How to Avoid Them | 常见错误与避免方法
Students often confuse the stack pointer update order. When pushing, remember to increment top first, then assign the value (or assign then increment depending on the convention, but be consistent). With queues, forgetting to use modular arithmetic in a circular queue leads to index‑out‑of‑bounds errors. Another mistake is not resetting pointers when a queue becomes empty after a dequeue; many implementations require setting both front and rear to –1 (or another sentinel value) to mark the empty state. Also, always draw a diagram and trace operations one by one in the exam to avoid logical slips.
学生常常混淆栈指针的更新顺序。压入时，记住要先递增 top，再赋值（或是先赋值再递增，这取决于约定，但务必保持一致）。对于队列，在循环队列中忘记使用模运算会导致索引越界错误。另一个错误是当出队后队列变空时没有重置指针；许多实现要求将 front 和 rear 都设置为 –1（或其他哨兵值）以标记空状态。此外，在考试中一定要画图并逐步跟踪操作，以避免逻辑失误。
12. Summary and Revision Tips | 总结与复习建议
Stacks and queues are simple yet powerful abstract data types that appear in many computing contexts. For your CCEA exam, make sure you can write and interpret pseudocode for push, pop, enqueue, and dequeue operations on both static and circular structures. Practise drawing the state of an array after a sequence of operations, and be comfortable with the LIFO and FIFO concepts. Remember that stacks are essential for recursion and expression evaluation, while queues model fair waiting lines and buffered I/O. Use past CCEA papers to test your ability to spot overflow/underflow conditions and pointer updates under pressure.
栈和队列是简单但强大的抽象数据类型，出现在许多计算场景中。为应对 CCEA 考试，确保你能编写并解释在静态和循环结构上的 push、pop、enqueue 和 dequeue 的伪代码。练习绘制一系列操作后数组的状态，并熟练掌握 LIFO 和 FIFO 概念。记住，栈对于递归和表达式求值至关重要，而队列则模拟公平的排队和缓冲输入输出。使用 CCEA 历年真题来检验你在压力下识别溢出 / 下溢条件和指针更新的能力。
Published by TutorHao | Computing Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导