📚 Stacks and Queues: IGCSE OCR Computer Science Exam Focus | IGCSE OCR 计算机：栈与队列 考点精讲
Data structures are the backbone of efficient algorithm design, and for IGCSE OCR Computer Science, stacks and queues are two of the most fundamental abstract data types you must master. This article breaks down every key concept, from LIFO and FIFO principles to implementation methods and real-world applications, complete with tracing exercises and exam-focused tips.
数据结构是高效算法设计的基石，对 IGCSE OCR 计算机科学来说，栈和队列是你必须掌握的最基本的两种抽象数据类型。本文拆解每一个关键概念，从LIFO和FIFO原理到实现方法及实际应用，并配以跟踪练习和考试重点技巧。
1. Abstract Data Types vs Data Structures | 抽象数据类型与数据结构
In OCR exams, it is crucial to distinguish between an abstract data type (ADT) and a concrete data structure. A stack is an ADT defined by its behaviour (LIFO), whereas an array or linked list is a physical data structure used to implement it.
在OCR考试中，区分抽象数据类型（ADT）与具体数据结构至关重要。栈是由其行为（后进先出）定义的ADT，而数组或链表则是用于实现它的物理数据结构。
An ADT specifies what operations can be performed, but not how they are implemented. A data structure describes the actual storage organisation in memory. Stacks and queues are both ADTs that can be implemented using arrays or linked lists.
ADT规定了可以执行哪些操作，而不规定如何实现。数据结构描述了内存中的实际存储组织。栈和队列都是ADT，都可以用数组或链表实现。
This distinction often appears in definition questions: “State the difference between a stack and an array.” The answer lies in the ADT versus implementation perspective.
这种区别经常出现在定义题中：“说明栈和数组的区别。”答案就在于ADT与实现视角的不同。
2. The Stack: LIFO Principles and Core Operations | 栈：后进先出原理与核心操作
A stack follows the Last-In-First-Out (LIFO) rule. The last item added (pushed) onto the stack is the first one removed (popped). You can only access the top element directly.
栈遵循后进先出（LIFO）规则。最后加入（压入）栈的项最先被移除（弹出）。你只能直接访问栈顶元素。
The five standard stack operations are: push(item) – adds an item to the top; pop() – removes and returns the top item; peek() or top() – returns the top item without removing it; isEmpty() – checks if the stack has no items; isFull() – checks if the stack has reached its capacity (required when implemented with a static array).
五个标准栈操作是：push(项) – 将项添加至顶部；pop() – 移除并返回顶部项；peek() 或 top() – 返回顶部项但不移除；isEmpty() – 检查栈是否为空；isFull() – 检查栈是否已满（使用静态数组实现时需要）。
When a pop is attempted on an empty stack, a “stack underflow” error occurs. Pushing to a full stack causes “stack overflow”. These error conditions are examinable.
当对空栈执行弹出操作时，会发生“栈下溢”错误。对已满栈压入则导致“栈上溢”。这些错误条件是考点。
| Operation | Description | 中文说明 |
| push(x) | Insert x on top | 将x插入顶部 |
| pop() | Remove and return top item | 移除并返回顶部项 |
| peek() | Return top without removal | 返回顶部项但不移除 |
| isEmpty() | True if stack is empty | 栈空则返回真 |
| isFull() | True if stack has no space | 栈无空间则返回真 |
3. Stack Implementation: Arrays and Linked Lists | 栈的实现：数组与链表
Using an array: A fixed-size array holds the stack elements, and an integer variable ‘top’ acts as an index pointer. Initially, top = -1 (empty). On push, top increments; on pop, top decrements. The maximum size must be declared.
使用数组实现：一个固定大小的数组保存栈元素，一个整数变量“top”作为索引指针。初始时 top = -1（空）。压入时 top 递增；弹出时 top 递减。必须声明最大大小。
Using a linked list: Each node contains data and a pointer to the next node. The ‘top’ pointer references the head node. Push adds a new head; pop removes the head. No fixed size – dynamic memory allocation, avoiding overflow (unless heap memory exhausted).
使用链表实现：每个节点包含数据和指向下一节点的指针。“top”指针引用头节点。压入即添加新头节点；弹出即移除头节点。无固定大小——动态内存分配，可避免上溢（除非堆内存耗尽）。
OCR may ask you to describe or draw a stack after a series of operations, so be comfortable tracing state changes with both representations. Pay attention to when the pointer moves and what happens to the “removed” element (it stays in memory but becomes inaccessible).
OCR可能会要求你描述或绘制一系列操作后的栈，因此要能熟练跟踪两种表示方式的状态变化。注意指针何时移动以及“被移除”元素的情况（它在内存中仍然存在，但变得不可访问）。
4. Stack Applications in Computing | 栈在计算中的应用
One classic application is the call stack in program execution. When a function is called, its return address and local variables are pushed onto the call stack. When the function returns, the frame is popped, and control returns to the calling code.
一个经典应用是程序执行中的调用栈。调用函数时，其返回地址和局部变量被压入调用栈。函数返回时，该帧被弹出，控制权返回调用代码。
Another application is the undo feature in software. Each action is pushed onto a stack; pressing undo pops the most recent action and reverses it. Stacks are also used for checking balanced brackets in expressions: push opening brackets, pop on matching closing brackets.
另一个应用是软件中的撤销功能。每一步操作都被压入栈中；按撤销会弹出最近操作并逆转它。栈还用于检查表达式中的括号匹配：遇到开括号压入，遇到匹配的闭括号则弹出。
Reverse Polish Notation (RPN) evaluation also relies heavily on stacks. Operands are pushed; when an operator is encountered, operands are popped, the operation performed, and the result pushed back.
逆波兰表示法（RPN）求值也严重依赖栈。操作数被压入；遇到运算符时，弹出操作数，执行运算，结果重新压入。
5. The Queue: FIFO Principles and Core Operations | 队列：先进先出原理与核心操作
A queue follows the First-In-First-Out (FIFO) rule. The first item added (enqueued) is the first to be removed (dequeued). Elements join at the rear and leave from the front, like a line of people.
队列遵循先进先出（FIFO）规则。最先加入（入队）的项最先被移除（出队）。元素在队尾加入，从队头离开，就像排队的人群。
Core operations: enqueue(item) – adds an item to the rear; dequeue() – removes and returns the item at the front; front() – views the front item; isEmpty() and isFull() serve the same role as in stacks. In a linear array implementation, two pointers, front and rear, are maintained.
核心操作：enqueue(项) – 将项添加至队尾；dequeue() – 移除并返回队头的项；front() – 查看队头项；isEmpty() 和 isFull() 的作用与栈中相同。在线性数组实现中，需要维护 front 和 rear 两个指针。
In OCR pseudocode questions, you must be precise about how these pointers are updated. Crucially, a linear queue suffers from the “drifting” problem where space at the front becomes unusable after dequeues.
在OCR伪代码题中，你必须精确描述这些指针如何更新。关键一点是，线性队列存在“漂移”问题：出队多次后，队头前的空间变得不可用。
6. Circular Queues: Solving the Drifting Problem | 循环队列：解决漂移问题
A linear queue implemented with an array appears to become full even when free space exists at the front. The circular queue solves this by treating the array as a circle: when rear reaches the end, it wraps around to index 0 if space is available.
用数组实现的线性队列即使队头前有空闲空间，也似乎已满。循环队列通过将数组视为一个环来解决此问题：当 rear 到达末尾时，如果有空位就回绕到索引 0。
To implement a circular queue, you need front, rear, and a count or a flag to distinguish full from empty when front equals rear. Typically, you sacrifice one slot to differentiate: when (rear + 1) mod size == front, the queue is full.
实现循环队列需要 front、rear 和一个计数变量或标志位，以便在 front 等于 rear 时区分队列是空还是满。通常牺牲一个槽位来区分：当 (rear + 1) mod 大小 == front 时，队列已满。
Modulo arithmetic is essential here: rear = (rear + 1) MOD maxSize on enqueue, front = (front + 1) MOD maxSize on dequeue. This ensures indexes wrap correctly.
这里取模运算至关重要：入队时 rear = (rear + 1) MOD 最大大小，出队时 front = (front + 1) MOD 最大大小。这确保索引正确回绕。
OCR often sets tracing questions where you must update pointers for a circular queue of given size. Practice with small sizes like 4 or 5 to avoid off-by-one errors.
OCR常出跟踪题，要求你为给定大小的循环队列更新指针。用大小如4或5进行练习，避免差一错误。
7. Queue Applications in Real Systems | 队列在真实系统中的应用
A printer spooler uses a queue to hold print jobs. Documents are added to the queue in the order they were sent, and the printer processes them one by one, maintaining FIFO order.
打印机后台处理程序使用队列来保存打印作业。文档按发送顺序加入队列，打印机逐个处理，保持FIFO顺序。
Keyboard buffers in operating systems also employ queues. Keystrokes are stored as they are typed, even if the CPU is busy; the buffer ensures no characters are lost and they are processed chronologically.
操作系统中的键盘缓冲区也使用队列。击键被依次存储，即使CPU繁忙；缓冲区确保字符不丢失并按时间顺序处理。
Breadth-first search (BFS) in graphs uses a queue to explore nodes level by level. The current node’s neighbours are enqueued, and the algorithm dequeues the next node to visit, guaranteeing shortest paths in unweighted graphs.
图的广度优先搜索（BFS）使用队列逐层探索节点。当前节点的邻居被入队，算法出队下一个访问节点，从而保证在无权图中的最短路径。
8. Comparison of Stacks and Queues | 栈与队列对比
| Aspect | Stack | Queue |
| Principle | LIFO (Last In First Out) | FIFO (First In First Out) |
| Insertion point | Top | Rear |
| Removal point | Top | Front |
| Number of pointers | 1 (top) | 2 (front and rear) |
| Overflow condition | top = maxSize – 1 | (rear + 1) mod size = front |
| Underflow condition | top = -1 | front = -1 (or front = rear, depending) |
| Key usage | Reverse order, backtracking | Order preservation, sequential processing |
These differences are frequently tested in OCR multiple-choice and short-answer sections. Remember: a stack reverses order (the last item in is the first out), while a queue preserves order.
这些区别经常在OCR选择题和简答题中考查。记住：栈反转顺序（最后入的最先出），而队列保持顺序。
9. Pseudocode Conventions in OCR Exams | OCR考试中的伪代码规范
OCR uses a specific pseudocode style. For stacks: myStack.push(value), value = myStack.pop(), if myStack.isEmpty() then. For queues: myQueue.enqueue(value), value = myQueue.dequeue(), front = myQueue.front(). You must follow these conventions to avoid losing marks.
OCR使用特定的伪代码风格。栈：myStack.push(value)、value = myStack.pop()、if myStack.isEmpty() then。队列：myQueue.enqueue(value)、value = myQueue.dequeue()、front = myQueue.front()。你必须遵循这些规范以避免失分。
In tracing questions, you might be asked to show the state of the structure after a sequence of operations. Always draw a clear table with the operation and the resulting content (or output). Label stack top/ queue front and rear explicitly.
在跟踪题中，你可能需要展示一系列操作后结构的状态。始终绘制清晰的表格，列出操作和结果内容（或输出）。明确标注栈顶/队列的 front 和 rear。
Example trace for stack: start empty; push(5); push(8); pop() returns 8; push(2); stack now contains [5, 2] with top at 2.
栈跟踪示例：初始为空；push(5)；push(8)；pop() 返回 8；push(2)；栈现在包含 [5, 2]，top 指向 2。
10. Common Pitfalls and How to Avoid Them | 常见错误及如何避免
Pitfall 1: Forgetting that pop removes the item. If the question asks “what does pop() return?”, always answer the value removed, and separately note the stack’s new state. Some students confuse this with peek.
错误1：忘了pop会移除项。如果题目问“pop()返回什么？”，始终回答被移除的值，并单独注明栈的新状态。一些学生将此与peek混淆。
Pitfall 2: In circular queues, miscounting the empty/full condition. When front equals rear, the queue is empty. When (rear + 1) mod size equals front, the queue is full. Using a count variable simplifies this but OCR expects the modulo method.
错误2：在循环队列中，误判空/满条件。当 front 等于 rear 时，队列为空。当 (rear + 1) mod 大小等于 front 时，队列为满。使用计数变量可简化此问题，但OCR期望使用取模方法。
Pitfall 3: Assuming a fixed-size array implementation automatically prevents overflow. Always check isFull() before push/enqueue unless the question explicitly allows dynamic sizing (e.g., linked list).
错误3：认为固定大小数组实现会自动防止溢出。除非题目明确允许动态调整大小（如链表），否则必须在 push/enqueue 前检查 isFull()。
Pitfall 4: Incorrect pointer updates after dequeue in a linear queue. While many textbooks show front incrementing, some questions require shifting elements. Read the question’s context carefully.
错误4：线性队列出队后指针更新不正确。虽然许多教科书显示 front 递增，但有些问题要求移动元素。仔细阅读题目上下文。
11. Sample Exam-Style Tracing Question | 考试风格跟踪题示例
A stack S and a queue Q are initially empty. Perform the following operations in order: S.push(4); Q.enqueue(7); S.push(9); Q.enqueue(S.pop()); S.push(2); Q.enqueue(S.peek()); Q.dequeue(). What are the final contents of S and Q? (Answer walkthrough below.)
栈 S 和队列 Q 初始为空。按顺序执行以下操作：S.push(4)；Q.enqueue(7)；S.push(9)；Q.enqueue(S.pop())；S.push(2)；Q.enqueue(S.peek())；Q.dequeue()。S 和 Q 的最终内容是什么？（解答见下文。）
Step-by-step: S empty, Q empty. -> S: [4] (top=4). -> Q: [7] (front=7, rear=7). -> S: [4,9] (top=9). -> S.pop() returns 9, S becomes [4] (top=4); Q now [7,9] rear=9. -> S.push(2) -> S: [4,2] (top=2). -> S.peek() returns 2; Q.enqueue(2) -> Q: [7,9,2] rear=2. -> Q.dequeue() removes 7, Q becomes [9,2] front=9. Final S: [4,2], Q: [9,2]. This kind of multi-structure question is common.
逐步分析：S空，Q空。-> S: [4] (top=4)。-> Q: [7] (front=7, rear=7)。-> S: [4,9] (top=9)。-> S.pop() 返回9，S变为 [4] (top=4)；Q: [7,9] rear=9。-> S.push(2) -> S: [4,2] (top=2)。-> S.peek() 返回2；Q.enqueue(2) -> Q: [7,9,2] rear=2。-> Q.dequeue() 移除7，Q变为 [9,2] front=9。最终 S: [4,2], Q: [9,2]。这类多结构综合题很常见。
12. Revision Checkpoints and Final Tips | 复习检查点与最后提示
Ensure you can: define LIFO and FIFO with examples; list all five operations for each ADT; trace pointer values in array-based implementations; explain the circular queue mechanism; compare stack and queue applications; and write correct OCR pseudocode.
确保你能：用例子定义LIFO和FIFO；列出每种ADT的所有五个操作；跟踪基于数组实现中的指针值；解释循环队列机制；比较栈和队列的应用；并写出正确的OCR伪代码。
When drawing diagrams, label the top/front/rear clearly. If a stack is drawn vertically, the top should be at the highest index or at the head of the list. Queues should show the direction of movement (front towards rear).
绘制图表时，清晰标注 top/front/rear。如果栈垂直绘制，top 应在最高索引处或链表头部。队列应显示移动方向（从front到rear）。
Finally, always link back to the ADT principle. A question about “why a stack is used for undo” must reference LIFO: the most recent action must be reversed first. A question about “why a queue is used for a print spooler” must reference FIFO: first-come, first-printed.
最后，始终回归ADT原理。关于“为什么撤销要用栈”的问题必须引用LIFO：最近的操作必须最先被撤销。关于“为什么打印后台处理程序要用队列”的问题必须引用FIFO：先来先打印。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导