📚 Stacks and Queues: AQA IGCSE Computer Science Revision | 栈与队列考点精讲
Data structures organise and store data efficiently, and for IGCSE AQA Computer Science, stacks and queues are fundamental abstract data types. This article explains their principles, operations, implementations and applications, exactly as you need them for the exam.
数据结构可以高效地组织和存储数据，在 IGCSE AQA 计算机科学中，栈和队列是两种基本的抽象数据类型。本文将从考试要求出发，详细讲解它们的原理、操作、实现方式和应用场景。
1. What Is a Stack? | 什么是栈？
A stack is a linear data structure that follows the Last‑In‑First‑Out (LIFO) principle. The last item added to the stack is the first item removed. Imagine a stack of plates: you can only take the top plate away, and you can only place a new plate on top. The main operations are push (add an item) and pop (remove an item). A pointer called top tracks the most recently added element.
栈是一种遵循后进先出（LIFO）原则的线性数据结构。最后加入的元素会最先被移除。就像一叠盘子，只能从顶部取走盘子，也只能把新盘子放在顶部。栈的主要操作是推入（push）和弹出（pop），并用一个叫作栈顶（top）的指针记录最新加入的元素。
In the exam, you must be able to draw stack diagrams showing the state after each push and pop. Stacks are often implemented using a one‑dimensional array with a maximum size.
考试中你需要能够画出每次 push 和 pop 之后栈的状态图。栈通常用一维数组实现，并设定最大容量。
2. Stack Operations in Detail | 栈操作详解
The essential stack operations are push(item), pop(), peek(), isEmpty() and isFull(). Push adds an item to the top of the stack and increments the top pointer. Pop removes and returns the top item, then decrements the top pointer. Peek returns the top item without changing the stack. isEmpty checks if top equals –1 (no items), and isFull checks if top has reached the array’s last index.
栈的核心操作有push(item)、pop()、peek()、isEmpty()和isFull()。Push 将元素加入栈顶并使 top 指针加 1；pop 移除并返回栈顶元素，之后 top 指针减 1；peek 仅返回栈顶元素而不修改栈；isEmpty 检查 top 是否为 –1（栈空）；isFull 检查 top 是否已到达数组最后一个下标。
An attempt to push onto a full stack causes stack overflow. Popping from an empty stack causes stack underflow. Both must be checked with appropriate conditions before performing the operation.
对已满的栈执行 push 会导致栈上溢（stack overflow）；对空栈执行 pop 则导致栈下溢（stack underflow）。执行操作前必须检查相应的条件。
3. Implementing a Stack Using an Array | 用数组实现栈
A typical array‑based stack holds elements of a fixed size. The top pointer is initialised to –1. When pushing, first check that top + 1 is less than the array length; if so, increment top and store the item at stack[top]. When popping, if top is not –1, retrieve stack[top] and decrement top.
基于数组的栈通常容量固定，top 指针初始化为 –1。Push 时，先判断 top + 1 是否小于数组长度；如果是，top 加 1，再将元素存入 stack[top]。Pop 时，若 top 不为 –1，取出 stack[top] 的值，然后将 top 减 1。
The algorithm in pseudocode is straightforward. You should be comfortable tracing it for any AQA exam question that provides a sequence of operations.
其伪代码算法非常直观。你需要能够熟练跟踪任何 AQA 考题中给出的一系列操作。
top ← –1
PROCEDURE push(item)
IF top = MAX_SIZE – 1 THEN OUTPUT “overflow” ELSE top ← top + 1; stack[top] ← item
PROCEDURE pop()
IF top = –1 THEN OUTPUT “underflow” ELSE item ← stack[top]; top ← top – 1; RETURN item
4. Applications of Stacks | 栈的应用
Stacks appear in many areas of computing. Function call management uses a call stack: when a function is called, its return address and local variables are pushed; when it returns, they are popped. This is why recursion works. Expression evaluation uses stacks for postfix (Reverse Polish) notation, pushing operands until an operator pops them. Undo features in editors save each action on a stack; undo pops the last action. Backtracking algorithms, such as navigating a maze, use a stack to remember path choices.
栈在计算机领域应用广泛。函数调用管理使用调用栈：调用函数时，返回地址和局部变量被压入栈中；函数返回时再弹出。这也是递归能够实现的原因。表达式求值利用栈处理后缀（逆波兰）表达式：遇到操作数压栈，遇到运算符则弹出所需操作数。撤销（Undo）功能在编辑器中将每一步操作存入栈中，撤销时弹出最近一步。回溯算法（如走迷宫）使用栈记录路径选择。
When tracing recursive functions, draw the call stack to show the state before each call and after each return. This is a favourite exam task.
跟踪递归函数时，请画出调用栈，展示每次调用前和每次返回后的状态，这是考试中常见的任务。
5. What Is a Queue? | 什么是队列？
A queue is a linear data structure that obeys the First‑In‑First‑Out (FIFO) principle. Items join at the rear and leave from the front, just like a real queue of people. The main operations are enqueue (add to rear) and dequeue (remove from front). Two pointers are needed: front points to the first item, and rear points to the last item.
队列是一种遵循先进先出（FIFO）原则的线性数据结构。元素从队尾加入，从队首离开，就像现实中的排队。队列的主要操作是入队（enqueue）和出队（dequeue），需要两个指针：front 指向队首第一个元素，rear 指向队尾最后一个元素。
AQA expects you to understand both linear and circular queue implementations, and to recognise the problems of a simple linear queue.
AQA 要求你理解线性队列和循环队列两种实现方式，并认识到简单线性队列存在的问题。
6. Queue Operations in Detail | 队列操作详解
The standard queue operations are enqueue(item), dequeue(), isEmpty() and isFull(). Enqueue places an item at the rear and updates the rear pointer. Dequeue removes the item at the front and updates the front pointer. For a linear queue, after many dequeue operations, the front pointer moves forward, leaving unused spaces behind. Eventually, even if the queue is not full, enqueue may be impossible – this is known as a queue overflow caused by false‑full condition.
标准的队列操作有enqueue(item)、dequeue()、isEmpty()和isFull()。入队将元素加入队尾并更新 rear 指针；出队从队首移除元素并更新 front 指针。在简单线性队列中，多次出队后 front 指针向前移动，后面留下的空间无法再利用。最终即便队列并未真正满员，也可能无法入队，这种情况称为由“假满”引发的队列上溢。
Checking for an empty queue normally involves comparing front and rear pointers; for a full linear queue, you compare rear with the maximum index.
判断空队列通常是比较 front 和 rear 指针；判断线性队列已满则比较 rear 与最大下标。
7. Circular Queue Implementation | 循环队列实现
A circular queue solves the wasted‑space problem by wrapping the rear pointer back to the beginning when it reaches the array’s end. Both front and rear move around the array using modulo arithmetic: rear ← (rear + 1) MOD size. The queue is empty when front = rear. It is full when the next position after rear equals front, i.e. when (rear + 1) MOD size = front. This means one position must remain unused to distinguish between empty and full states.
循环队列通过让指针在数组末尾绕回到起始位置，解决了空间浪费问题。front 和 rear 指针都使用模运算在数组中循环移动：rear ← (rear + 1) MOD size。当 front = rear 时队列为空；当 rear 的下一个位置等于 front，也就是(rear + 1) MOD size = front 时，队列为满。这意味着必须牺牲一个元素空间，才能区分空和满两种状态。
Many AQA questions will ask you to draw the state of a circular queue after a series of enqueue and dequeue operations. Pay close attention to the order of pointer updates.
很多 AQA 考题会要求你画出一系列入队与出队操作后循环队列的状态。请特别留意指针更新的顺序。
8. Applications of Queues | 队列的应用
Queues are widely used where jobs or data must be processed in the order they arrive. Print spooling stores documents in a queue so the printer handles them sequentially. Keyboard buffers use a queue to hold keystrokes until the CPU can process them. Operating system scheduling employs queues to manage processes waiting for CPU time. Breadth‑first search in graph algorithms explores nodes level by level using a queue.
队列广泛用于需要按到达顺序处理数据或任务的场景。打印假脱机将文档存入队列，使打印机顺序处理。键盘缓冲区用队列暂存按键，直到 CPU 能够处理。操作系统调度利用队列管理等待 CPU 时间的进程。图的广度优先搜索使用队列逐层探索节点。
For the exam, be ready to explain why a queue is appropriate for a given scenario, focusing on the need for fair, first‑come‑first‑served ordering.
考试中要准备好解释为什么某一场景适合使用队列，重点强调需要公平的“先到先服务”顺序。
9. Stack vs Queue: Key Differences | 栈与队列的核心区别
Understanding the contrast between stacks and queues is essential. The table below summarises the most important distinctions you must know for AQA IGCSE.
理解栈与队列的差异至关重要。下表总结了 AQA IGCSE 需要掌握的最重要区别。
| Feature | 特性 | Stack | 栈 | Queue | 队列 |
|---|---|---|
| Ordering principle | 排序原则 | LIFO (Last‑In‑First‑Out) | FIFO (First‑In‑First‑Out) |
| Insertion operation | 插入操作 | Push (at top) | Enqueue (at rear) |
| Removal operation | 移除操作 | Pop (from top) | Dequeue (from front) |
| Pointers | 指针 | Single top pointer | Two pointers: front & rear |
| Primary applications | 主要应用 | Function calls, undo, recursion | Print spooling, buffering, scheduling |
In the exam, comparison questions often ask you to recommend one data structure over the other for a specific task. The answer must refer to the ordering need (LIFO or FIFO) and not simply name benefits.
在考试中，比较类题目常会让你为特定任务推荐一种数据结构。答案必须提到顺序需求（LIFO 或 FIFO），而不是仅仅罗列优点。
10. Exam Tips and Common Mistakes | 考试技巧与常见错误
Many marks are lost on pointer values and boundary conditions. Remember: when you initialise a stack, top is –1; for an empty linear queue, front and rear are often both set to –1 or 0 depending on the implementation given in the question. Always read the question’s starting pointer values. When popping or dequeueing, do not forget to update the relevant pointer. For circular queues, check the wrap‑around condition carefully; students often miscount the number of used slots.
关于指针值和边界条件，很多学生会丢分。要记住：栈初始化时 top 为 –1；空线性队列的 front 和 rear 通常都设为 –1 或 0，具体取决于题目给出的实现说明。一定要仔细阅读题目中的指针初始值。出栈或出队时不要忘记更新相应的指针。对于循环队列，请仔细检查绕回条件；学生经常数错已使用的槽位数量。
When tracing algorithms, draw a new diagram after each operation. Label pointers clearly. If a push causes overflow or pop causes underflow, state it explicitly in your answer. AQA expects precise use of terminology; do not write ‘add’ instead of ‘push’ or ‘remove’ instead of ‘pop’ when the question uses those terms.
跟踪算法时，每执行一个操作就画一幅新图，并清楚标出指针。如果 push 造成上溢或 pop 造成下溢，要在答案中明确说明。AQA 期待你准确使用术语；当题目使用了 push 和 pop 时，不要用 “add” 或 “remove” 来代替。
11. Worked Example & Practice | 范例与练习
Consider a stack implemented with an array of size 5. Initially the stack is empty. Trace the following sequence: push(10), push(20), pop(), push(30), push(40), push(50), push(60). The final stack should contain [10,30,40,50] from bottom to top, with top pointing to index 3. The push(60) attempt should trigger an overflow message. This tracing exercise tests both pointer management and overflow detection.
假设用一个大小为 5 的数组实现栈。初始栈为空，跟踪操作序列：push(10), push(20), pop(), push(30), push(40), push(50), push(60)。最终栈从底到顶应为 [10,30,40,50]，top 指向索引 3。push(60) 应触发上溢消息。这道跟踪题既考察指针管理，也考察上溢检测。
Now try a circular queue of size 5 (positions 0–4) starting with front = 0, rear = 0. Enqueue 1, Enqueue 2, Dequeue, Enqueue 3, Enqueue 4, Enqueue 5, Enqueue 6. After these steps, front should be 1, rear should be 0, and the queue should hold [2,3,4,5] with one empty slot. Attempting to enqueue 6 should be impossible because (rear+1) MOD size equals front. This is a classic exam‑style question; practise until you can do it quickly.
再尝试一个大小为 5（槽位 0–4）的循环队列，初始 front = 0, rear = 0。执行：Enqueue 1, Enqueue 2, Dequeue, Enqueue 3, Enqueue 4, Enqueue 5, Enqueue 6。操作后，front 应为 1，rear 应为 0，队列应为 [2,3,4,5]，留有一个空槽。试图 Enqueue 6 时会因为 (rear+1) MOD size 等于 front 而失败。这是典型的考试题型，请反复练习直到熟练。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导