📚 Stack and Queue Key Points for IGCSE CCEA Computer Science | IGCSE CCEA 计算机：栈与队列 考点精讲
Stacks and queues are fundamental abstract data types that frequently appear in the IGCSE CCEA Computer Science specification. This article provides a clear, bilingual breakdown of all essential concepts, operations, and typical examination tricks, helping you tackle paper questions with confidence.
栈和队列是 IGCSE CCEA 计算机科学大纲中经常出现的基本抽象数据类型。本文以清晰的双语解析所有核心概念、操作和常见考题陷阱，帮助你自信应对试卷题目。
1. Abstract Data Types (ADTs) Overview | 抽象数据类型概述
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 implementation details. Both stacks and queues are ADTs because they define behaviour rather than storage mechanics.
抽象数据类型（ADT）是对数据视图和可执行操作的逻辑描述，不规定具体实现细节。栈和队列都是 ADT，因为它们定义了行为而非存储机制。
Understanding ADTs helps you separate interface from implementation – a key idea in computer science. In CCEA papers, you may be asked to explain why a stack is an ADT.
理解 ADT 有助于你将接口与实现分离——这是计算机科学的关键思想。在 CCEA 考试中，你可能会被要求解释为什么栈是一种 ADT。
2. Stack Definition and LIFO Principle | 栈的定义与后进先出原则
A stack is a linear data structure that follows the Last In, First Out (LIFO) rule. Items are added and removed only from one end, called the top. The last element placed onto the stack is always the first one to be taken off.
栈是一种遵循后进先出（LIFO）规则的线性数据结构。元素的添加和删除只能在称为栈顶的一端进行。最后放入栈的元素总是最先被取出。
Think of a stack of plates in a canteen: you can only take the top plate, and new plates are placed on top as well. This analogy is extremely common in CCEA exam questions.
想象食堂里的一摞盘子：你只能取最上面的盘子，而新盘子也被放在最上面。这个类比在 CCEA 考题中极为常见。
3. Essential Stack Operations and States | 栈的基本操作与状态
The primary stack operations are push, pop, peek (or top), isEmpty, and isFull (if using a static array). Push adds an item to the top; pop removes and returns the top item; peek returns the top item without removing it.
栈的主要操作是入栈（push）、出栈（pop）、查看栈顶（peek/top）、判空（isEmpty）和判满（isFull，当使用静态数组时）。Push 在栈顶添加元素；pop 移除并返回栈顶元素；peek 只返回栈顶元素而不移除。
You must also be aware of stack underflow (popping from an empty stack) and stack overflow (pushing into a full stack). These errors are often tested in trace table questions.
你还必须了解栈下溢（从空栈中出栈）和栈上溢（向已满栈中入栈）。这些错误经常在跟踪表题目中考查。
The standard algorithm for push is: if stack is not full, increment top pointer and insert new item; for pop: if stack is not empty, return item at top and decrement top pointer.
入栈的标准算法是：如果栈未满，栈顶指针加一，插入新元素；出栈：如果栈非空，返回栈顶元素，栈顶指针减一。
4. Implementing a Stack with Arrays and Pointers | 使用数组和指针实现栈
In CCEA contexts, a stack is often implemented using a 1D array and a variable called top that stores the index of the highest occupied cell. When the stack is empty, top is typically set to -1.
在 CCEA 情境中，栈通常用一维数组和一个名为 top 的变量实现，该变量存储最高占用单元的索引。当栈为空时，top 通常设为 -1。
Pushing increments top by 1 and then stores the data at that index. Popping retrieves the data at top and then decrements top. This simple model allows for easy tracing of stack contents on paper.
入栈时，top 加 1，然后在该索引处存储数据。出栈时，读取 top 处的数据，然后 top 减 1。这种简单模型便于在纸上追踪栈的内容。
An example: array Stack[0..4] with top = -1. Push(‘A’) → top becomes 0, Stack[0] = ‘A’. Push(‘B’) → top = 1, Stack[1] = ‘B’. Pop returns ‘B’, top becomes 0.
示例：数组 Stack[0..4]，top = -1。Push(‘A’) → top 变为 0，Stack[0] = ‘A’。Push(‘B’) → top = 1，Stack[1] = ‘B’。Pop 返回 ‘B’，top 变回 0。
5. Queue Definition and FIFO Principle | 队列的定义与先进先出原则
A queue is a linear data structure that operates under the First In, First Out (FIFO) principle. Insertions happen at the rear (or tail), and deletions occur at the front (or head). The first element added is the first one to be removed.
队列是一种在先进先出（FIFO）原则下运行的线性数据结构。插入操作在队尾进行，删除操作在队头进行。最先加入的元素最先被移除。
Imagine a queue of people waiting for a bus – the person at the front boards first, and newcomers join at the back. This real-life model is used extensively in exam scenarios.
想象排队等公交车的人群——最前面的人先上车，新来的人加入队尾。这种现实模型在考试场景中被广泛使用。
6. Queue Operations and Pointer Management | 队列操作与指针管理
Key queue functions are enqueue (add to rear), dequeue (remove from front), peekFront, isEmpty, and isFull. Two pointers – front and rear – are maintained to track the logical boundaries of the queue.
关键的队列函数有入队（enqueue，在队尾添加）、出队（dequeue，从队头移除）、查看队头（peekFront）、判空和判满。维护两个指针——front 和 rear——来跟踪队列的逻辑边界。
When using a static array of size n, initial values are often front = 0 and rear = -1 for an empty queue. Enqueue increments rear and inserts the item; dequeue increments front after returning the item.
使用大小为 n 的静态数组时，空队列的初始值常为 front = 0 和 rear = -1。入队时 rear 加一后插入；出队时返回元素后将 front 加一。
Underflow occurs when dequeuing from an empty queue (front > rear), and overflow occurs when enqueuing to a full queue (rear = maxSize – 1 in linear implementation).
下溢发生在从空队列出队时（front > rear），上溢发生在向已满队列入队时（线性实现中 rear = maxSize – 1）。
7. Linear Queue Limitations and Circular Queue | 线性队列的局限性与循环队列
A standard linear array queue suffers from the “drifting” problem: even after dequeuing, the front index moves forward, leaving unused spaces at the beginning that cannot be reused without resetting the pointers.
标准的线性数组队列存在“漂移”问题：即使出队后，front 索引向前移动，开头留下的未用空间除非重置指针，否则无法再被利用。
The circular queue solves this by treating the array as circular: when rear or front reaches the end, it wraps around to 0 if space exists. The condition for a full circular queue is (rear + 1) mod size = front (if using one cell gap).
循环队列通过将数组视为环形来解决此问题：当 rear 或 front 到达末尾时，若有空间则回绕到 0。循环队列满的条件（当留有一个单元间隙时）是 (rear + 1) mod size = front。
CCEA questions often present a circular queue implemented in an array and ask you to trace pointer movements after several enqueue and dequeue operations. Be careful with the modulo arithmetic.
CCEA 题目经常给出一个数组实现的循环队列，要求你追踪多次入队和出队操作后的指针移动。注意模运算。
8. Comparing Stacks and Queues | 栈与队列的对比
| Aspect 方面 | Stack 栈 | Queue 队列 |
|---|---|---|
| Order 顺序 | LIFO 后进先出 | FIFO 先进先出 |
| Access point 访问点 | One end (top) 一端（栈顶） | Two ends (front & rear) 两端（队头和队尾） |
| Number of pointers 指针数量 | One (top) 一个（栈顶） | Two (front & rear) 两个（队头、队尾） |
| Typical uses 典型用途 | Undo, function calls, backtracking 撤销、函数调用、回溯 | Buffers, task scheduling, print spooling 缓冲区、任务调度、打印队列 |
While both are constrained-access structures, the order in which items leave determines their suitability for different computational problems. Examiners frequently ask you to choose the appropriate ADT for a given scenario.
虽然两者都是受限访问结构，但元素离开的顺序决定了它们对不同计算问题的适用性。考官经常要求你针对给定场景选择合适的抽象数据类型。
9. Real-World Applications Tested in CCEA | CCEA 考查的现实应用
Stacks are used in managing subroutine calls (call stack), evaluating arithmetic expressions in Reverse Polish Notation (RPN), and implementing “undo” features in text editors. For RPN, operands are pushed, and operators pop the required operands and push the result.
栈用于管理子程序调用（调用栈）、求值逆波兰表达式（RPN）以及实现文本编辑器中的“撤销”功能。对于 RPN，操作数入栈，运算符弹出所需的操作数并将结果压回栈中。
Queues appear in printer spooling (jobs printed in arrival order), keyboard buffers, and CPU process scheduling. A keyboard buffer stores keystrokes as they are typed, and the CPU reads them in the same order using a queue.
队列出现在打印机假脱机（按到达顺序打印作业）、键盘缓冲区和 CPU 进程调度中。键盘缓冲区按输入顺序存储击键，CPU 使用队列以相同顺序读取它们。
CCEA questions sometimes ask you to identify which data structure is being used in a described system. Look for clues like “first come, first served” (queue) or “most recent command reversed” (stack).
CCEA 问题有时会要求你识别所描述系统使用了哪种数据结构。寻找类似“先到先服务”（队列）或“撤销最近命令”（栈）的线索。
10. Tracing and Problem-Solving on Paper | 纸上追踪与解题技巧
Many exam questions provide a partially filled table and ask you to complete it by tracing a sequence of stack or queue operations. Always update the pointers first, then the data cells, and finally note the returned value (if any).
许多考题会给出部分填充的表格，要求你通过追踪一系列栈或队列操作来完成它。务必先更新指针，再更新数据单元，最后记录返回值（若有）。
For a stack trace, maintain a column for the instruction, the top pointer, the array contents, and any output. For a queue, track front, rear, array, and output. Use – for empty cells.
对于栈的追踪，保持一列记录指令、top 指针、数组内容和任何输出。对于队列，追踪 front、rear、数组和输出。用 – 表示空单元。
When dealing with circular queues, pay attention to the modulo arithmetic when incrementing pointers. For example, if the array size is 5 and rear is 4, enqueue sets rear = (rear + 1) MOD 5 = 0.
在处理循环队列时，注意增量指针时的模运算。例如，如果数组大小为 5 且 rear = 4，入队操作设置 rear = (rear + 1) MOD 5 = 0。
11. Common Pitfalls and How to Avoid Them | 常见误区与避免方法
Pitfall 1: Confusing LIFO with FIFO. When asked to draw the state after several operations, double-check whether the structure is a stack or a queue. Write “LIFO” or “FIFO” next to the diagram to remind yourself.
误区一：混淆 LIFO 与 FIFO。当要求绘制若干操作后的状态时，务必反复确认该结构是栈还是队列。在图旁写下“LIFO”或“FIFO”提醒自己。
Pitfall 2: Off-by-one errors with pointers. In a stack, after push, top points to the newly inserted element. In a linear queue, after dequeue, front points to the next element. Be precise with increments and decrements.
误区二：指针的差一错误。在栈中，push 后 top 指向新插入的元素。在线性队列中，出队后 front 指向下一个元素。要精确处理增减量。
Pitfall 3: Forgetting to check for underflow/overflow. Always state the condition before performing the operation, even if the question does not explicitly ask for it. This shows full understanding.
误区三：忘记检查下溢/上溢。在执行操作前，务必声明条件，即使题目没有明确要求。这展示了你对概念的完整理解。
Pitfall 4: Mixing up the full condition in circular queues. There are at least two variants: using a whole array cell to distinguish full from empty, or maintaining a separate size counter. Read the question carefully.
误区四：搞混循环队列的满条件。至少有变体：使用一个完整数组单元区分满和空，或者维护单独的计数变量。仔细读题。
12. Summary of CCEA Revision Checklist | CCEA 复习清单总结
- Explain the LIFO nature of stacks and FIFO nature of queues with everyday analogies 用日常类比解释栈的 LIFO 特性和队列的 FIFO 特性
- Write algorithms in pseudocode or high-level code for push, pop, enqueue, dequeue 写出 push、pop、enqueue、dequeue 的伪代码或高级语言算法
- Illustrate array-based implementation with pointer variables 用指针变量说明基于数组的实现
- Distinguish between linear and circular queue implementations 区分线性队列和循环队列实现
- Trace stack/queue operations through tables 通过表格追踪栈/队列操作
- Identify suitable applications for each structure 识别每种结构的适用应用场景
- Detect and correct common errors such as underflow and overflow 检测并纠正常见错误，如下溢和上溢
Mastering these points ensures strong performance on data structure questions in the IGCSE CCEA Computer Science examination.
掌握这些考点能确保你在 IGCSE CCEA 计算机科学考试的数据结构题目中表现出色。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导