📚 Stacks and Queues in GCSE OCR Computer Science | GCSE OCR 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types (ADTs) covered in the GCSE OCR Computer Science specification. They provide ordered ways of storing and retrieving data, but they differ in the order in which elements are processed. Mastering these concepts is essential for understanding how programs manage memory, control flow, and data buffering. This article provides a thorough breakdown of stacks and queues, their operations, implementations, and typical exam-style applications, presented in a clear bilingual format to support your revision.
栈和队列是 GCSE OCR 计算机科学课程中的基础抽象数据类型 (ADT)。它们提供了有序存储和检索数据的方式，但处理元素的顺序不同。掌握这些概念对于理解程序如何管理内存、控制流程和数据缓冲至关重要。本文将以清晰的双语形式，全面解析栈和队列、它们的操作、实现方式以及典型的考试应用，为你的复习提供支持。
1. Abstract Data Types (ADTs) | 抽象数据类型
An abstract data type is a logical description of how data is viewed and the operations that can be performed on it, without specifying how the data is actually stored in memory. Stacks and queues are both ADTs because they define a set of operations (like push or enqueue) but not the underlying implementation details. You might implement them using arrays or linked lists, but the user only interacts with the defined operations.
抽象数据类型是对数据如何被看待以及可以对其执行哪些操作的逻辑描述，而不指定数据在内存中的实际存储方式。栈和队列都是 ADT，因为它们定义了一组操作（如 push 或 enqueue），但不涉及底层的实现细节。你可以使用数组或链表来实现它们，但使用者只与定义好的操作交互。
2. What is a Stack? | 什么是栈？
A stack is a 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 imagine it like a stack of plates: you can only take the top plate off and you can only add a new plate to the top. In a stack, the top is the only accessible position.
栈是一种遵循后进先出 (LIFO) 原则的数据结构。最后加入栈的元素是第一个被移除的。你可以把它想象成一叠盘子：你只能取走最上面的盘子，也只能把新盘子放在最上面。在栈中，栈顶是唯一可访问的位置。
3. Stack Operations | 栈的操作
The GCSE OCR specification expects you to know five key stack operations:
- push(item) – add an item to the top of the stack.
- pop() – remove and return the item from the top of the stack.
- peek() or top() – return the value of the top item without removing it.
- isEmpty() – check if the stack contains no items; returns true/false.
- isFull() – check if the stack has reached its maximum capacity (relevant for static array implementations).
GCSE OCR 考试大纲要求你了解五个关键的栈操作：
- push(item) – 将一个元素添加到栈顶。
- pop() – 移除并返回栈顶的元素。
- peek() 或 top() – 返回栈顶元素的值但不移除它。
- isEmpty() – 检查栈是否为空；返回 true/false。
- isFull() – 检查栈是否已满（与静态数组实现相关）。
4. Stack Pointer and Underflow/Overflow | 栈指针与下溢/上溢
When a stack is implemented using an array, a variable called the stack pointer often holds the index of the top element. Initially, for an empty stack, the pointer might be set to -1. Stack overflow occurs when you try to push an item onto a full stack. Stack underflow occurs when you try to pop from an empty stack. Both are runtime errors that programmers must avoid by using `isEmpty` and `isFull` checks.
当使用数组实现栈时，一个称为栈指针的变量通常保存栈顶元素的索引。初始时，对于空栈，指针可能设置为 -1。栈上溢发生在试图向已满的栈压入元素时。栈下溢发生在试图从空栈弹出元素时。这两种都是运行时错误，程序员必须通过使用 `isEmpty` 和 `isFull` 检查来避免。
5. Simple Stack Implementation Using an Array | 使用数组的简单栈实现
Here is a conceptual representation of a stack using an array of size 5, along with pseudocode-style operations.
| Operation | Before | After | Pointer |
| push(‘A’) | [] | [‘A’] | 0 |
| push(‘B’) | [‘A’] | [‘A’,’B’] | 1 |
| pop() | [‘A’,’B’] | [‘A’] | 0 |
Pseudocode for push on an array-implemented stack:
if topPointer < maxSize - 1 then
topPointer = topPointer + 1
stack[topPointer] = item
else
‘overflow error’
endif
下图是数组实现栈的理论模型，表格展示了操作前后状态。上面给出了压入操作的伪代码：如果栈未满，增加指针并赋值；否则报上溢错误。
6. What is a Queue? | 什么是队列？
A queue is a 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 – just like people waiting in line. The front of the queue is where items are removed, and the rear is where new items are added.
队列是一种遵循先进先出 (FIFO) 原则的数据结构。第一个加入队列的元素是第一个被移除的——就像人们排队等候一样。队列的前端是移除元素的位置，后端是添加新元素的位置。
7. Queue Operations | 队列的操作
The key operations for a queue are:
- enqueue(item) – add an item to the rear of the queue.
- dequeue() – remove and return the item from the front of the queue.
- peek() or front() – return the value of the front item without removing it.
- isEmpty() – check if the queue has no items.
- isFull() – check if the queue is at maximum capacity.
队列的关键操作包括：
- enqueue(item) – 将一个元素添加到队列的后端。
- dequeue() – 移除并返回队列前端的元素。
- peek() 或 front() – 返回队列前端元素的值但不移除。
- isEmpty() – 检查队列是否为空。
- isFull() – 检查队列是否已满。
8. Circular Queues to Avoid Wasted Space | 循环队列避免空间浪费
In a linear array implementation of a queue, after several enqueue and dequeue operations, the front and rear both move forward, leaving unused spaces at the start of the array. A circular queue solves this by treating the array as circular: when the rear pointer reaches the end, it wraps around to the beginning if space is available. This requires careful pointer management:
rear = (rear + 1) MOD maxSize
front = (front + 1) MOD maxSize
在队列的线性数组实现中，经过多次入队和出队操作后，前端和后端都会向前移动，导致数组起始位置出现未使用的空间。循环队列通过将数组视为环状来解决这个问题：当后端指针到达末尾时，如果有可用空间，它会绕回到开头。这需要小心的指针管理，使用取模运算：rear = (rear + 1) MOD maxSize，front 同理。
9. Queue Implementation and Example | 队列实现与示例
Let’s model a circular queue of size 5. Initially front = 0, rear = -1, count = 0. ‘Count’ helps distinguish between full and empty states.
| Step | Operation | Array (0-4) | front | rear | count |
| 1 | enqueue(X) | [X, _, _, _, _] | 0 | 0 | 1 |
| 2 | enqueue(Y) | [X, Y, _, _, _] | 0 | 1 | 2 |
| 3 | dequeue() | [_, Y, _, _, _] | 1 | 1 | 1 |
| 4 | enqueue(Z) | [_, Y, Z, _, _] | 1 | 2 | 2 |
Notice how after dequeue, front moves to 1, leaving index 0 free for future wrap-around. The count ensures we know when the queue is full (count == maxSize) or empty (count == 0).
注意出队之后，front 移到了 1，索引 0 空闲出来以备将来绕回时使用。计数器确保我们知道队列何时满（count == maxSize）或空（count == 0）。
10. Applications of Stacks in Computing | 栈在计算中的应用
Stacks appear in many areas of computing:
- Call stack: when a function is called, its return address and local variables are pushed onto the call stack. When the function returns, they are popped off.
- Undo features: each action is pushed onto a stack; undo pops the last action to reverse it.
- Reverse Polish Notation (RPN) evaluation: operands are pushed; when an operator is encountered, operands are popped, calculated, and the result pushed back.
- Backtracking algorithms: such as navigating a maze, where choices are pushed and popped when dead ends are reached.
栈在计算的许多领域中出现：
- 调用栈：当函数被调用时，其返回地址和局部变量被压入调用栈。函数返回时，它们被弹出。
- 撤销功能：每个操作被压入栈中；撤销操作弹出最后一个操作来反转它。
- 逆波兰表示法 (RPN) 求值：操作数被压入；当遇到操作符时，弹出操作数，计算，并将结果压回。
- 回溯算法：例如迷宫导航，将选择压入栈中，当遇到死胡同时弹出。
11. Applications of Queues in Computing | 队列在计算中的应用
Queues are used whenever we need to process items in the order they arrive:
- Print spooler: documents are enqueued and printed in the order they were sent.
- Keyboard buffer: keystrokes are stored in a queue so they are processed in the correct sequence, even if the CPU is busy.
- CPU scheduling: processes waiting for the CPU are often held in queues (ready queue).
- Breadth-first search: in graph algorithms, nodes to visit are managed with a queue.
当需要按照到达顺序处理项目时，就会使用队列：
- 打印后台处理程序：文档入队并按发送顺序打印。
- 键盘缓冲区：按键被存储在队列中，以便即使 CPU 忙碌也能按正确顺序处理。
- CPU 调度：等待 CPU 的进程通常保存在队列中（就绪队列）。
- 广度优先搜索：在图算法中，要访问的节点用队列管理。
12. Key Differences and Exam Tips | 关键区别与考试技巧
It is crucial to remember the fundamental difference: stacks are LIFO, queues are FIFO. Exam questions often ask you to trace the state of a stack or queue after a series of operations, or to write pseudocode for push/pop or enqueue/dequeue while handling overflow/underflow. Make sure you can draw a table showing pointer movements and understand when to use `MOD` for circular queues. Always check for empty and full conditions before popping/dequeuing or pushing/enqueuing.
记住根本区别至关重要：栈是 LIFO，队列是 FIFO。考试题目经常要求你跟踪一系列操作后栈或队列的状态，或者编写处理上溢/下溢的 push/pop 或 enqueue/dequeue 伪代码。确保你能画出展示指针移动的表格，并理解何时对循环队列使用 `MOD` 运算。在弹出/出队或压入/入队之前，始终检查空和满的条件。
Both stacks and queues are simple yet powerful structures. A stack gives you the most recently added item first, making it perfect for reversing order or tracking nested operations. A queue gives you the oldest item first, preserving the original order. Understanding their operations and applications is a key part of the GCSE OCR Computer Science paper. Practice tracing through steps carefully, and you’ll be ready for any stack or queue question that comes your way.
栈和队列都是简单却强大的结构。栈让你最先访问最近添加的元素，非常适合逆序或跟踪嵌套操作。队列则让你最先访问最早添加的元素，保留了原始顺序。理解它们的操作和应用是 GCSE OCR 计算机科学考试的关键部分。通过仔细练习逐步跟踪，你将准备好应对任何有关栈或队列的问题。
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