📚 Stack and Queue Complete Revision for IGCSE CIE Computer Science | IGCSE CIE 计算机：栈与队列 考点精讲
Stack and queue are fundamental linear data structures that every IGCSE CIE Computer Science student must master. A clear understanding of how they operate, their differences, and their practical uses will not only help you answer theory questions accurately but also tackle trace table and pseudocode problems with confidence. This article breaks down all essential concepts, operations, and exam strategies for the stack and queue topic.
栈和队列是每位IGCSE CIE计算机科学学生必须掌握的基础线性数据结构。清晰地理解它们的工作方式、区别以及实际用途，不仅能帮助你准确回答理论题，还能让你自信地应对跟踪表和伪代码问题。本文逐一剖析栈与队列的所有核心概念、操作和考试策略。
1. Introduction to Data Structures | 数据结构简介
In computer science, a data structure is a specialized format for organizing, processing, retrieving and storing data. Linear data structures, such as stacks and queues, arrange elements in a sequential manner where every element is related to its previous and next neighbour. The IGCSE syllabus focuses on these two abstract data types and their typical array-based implementations.
在计算机科学中，数据结构是组织、处理、检索和存储数据的一种专用格式。线性数据结构，如栈和队列，以顺序方式排列元素，每个元素与其前后相邻元素相关联。IGCSE 考纲着重考察这两种抽象数据类型及其基于数组的典型实现。
2. What is a Stack? | 什么是栈？
A stack is a last-in, first-out (LIFO) data structure. Imagine a pile of plates in a cafeteria: the last plate placed on top is the first one taken off. In a stack, elements can only be added to the top and removed from the top. This constrained access makes stacks simple yet powerful for certain kinds of data processing, like tracking function calls or reversing data.
栈是一种后进先出（LIFO）的数据结构。想象一下食堂里的一摞盘子：最后放上去的盘子最先被取走。在栈中，元素只能从栈顶添加，也只能从栈顶移除。这种受限的访问方式使栈结构简单，但在某些数据处理中却非常强大，例如跟踪函数调用或反转数据。
3. Stack Operations – Push and Pop | 栈操作——压栈与出栈
The two primary operations on a stack are push and pop. Push adds a new element to the top of the stack, while pop removes the element currently at the top and returns it. Many exam boards also mention a peek (or top) operation, which allows you to view the top element without removing it. The IGCSE CIE specification expects students to write pseudocode for push and pop using an array and a stack pointer.
栈的两种主要操作是压栈和出栈。压栈将新元素添加到栈顶，而出栈则移除当前栈顶元素并返回其值。许多考试局还提及查看（peek 或 top）操作，它允许查看栈顶元素而不将其移除。CIE IGCSE 规范要求学生使用数组和栈指针编写压栈与出栈的伪代码。
4. Stack Pointer and Overflow/Underflow | 栈指针与溢出/下溢
A stack is usually implemented with a one-dimensional array and a variable called the stack pointer (SP), which holds the index of the current top element. Before pushing, we check if the stack is full; if SP equals the maximum index, a stack overflow occurs, and no more data can be added. Before popping, we check if the stack is empty; if SP is a sentinel value like 0 or -1 (depending on convention), a stack underflow error occurs because there is nothing to remove. Handling these conditions is a common exam requirement.
栈通常使用一维数组和一个名为栈指针（SP）的变量来实现，栈指针保存当前栈顶元素的索引。压栈之前，需要检查栈是否已满；如果 SP 等于最大索引，则发生栈溢出，无法再添加数据。出栈之前，需要检查栈是否为空；如果 SP 为哨兵值，如 0 或 -1（取决于约定），则发生栈下溢错误，因为没有元素可以移除。处理这些情况是常见的考试要求。
5. What is a Queue? | 什么是队列？
A queue is a first-in, first-out (FIFO) data structure. It behaves like a line of people waiting at a ticket counter: the first person to join the queue is the first person to be served. In a linear queue, elements are added at the rear and removed from the front. The queue structure is essential in many real-time computing scenarios where tasks must be processed in the order they arrive.
队列是一种先进先出（FIFO）的数据结构。它的行为类似于在售票窗口排队的人群：第一个加入队伍的人最先得到服务。在线性队列中，元素从队尾添加，从队首移除。队列结构在许多实时计算场景中至关重要，因为任务必须按照到达顺序进行处理。
6. Queue Operations – Enqueue and Dequeue | 队列操作——入队与出队
The fundamental operations for a queue are enqueue (adding an item to the rear) and dequeue (removing an item from the front). IGCSE CIE often requires students to manipulate two pointers: a front pointer, which indicates the position of the next item to be removed, and a rear pointer, which points to the last added item. Pseudocode for enqueue increments the rear pointer and places the new value; for dequeue, it retrieves the element at the front pointer and then increments the front pointer.
队列的基本操作是入队（将元素添加到队尾）和出队（从队首移除元素）。IGCSE CIE 经常要求学生操作两个指针：队首指针，指示下一个将被移除元素的位置；以及队尾指针，指向最后添加的元素。入队的伪代码递增队尾指针并存入新值；出队的伪代码则取出队首指针所指的元素，然后递增队首指针。
7. Types of Queues: Linear vs Circular | 队列的类型：线性队列与循环队列
In a linear queue implemented with an array, repeatedly enqueuing and dequeuing can create a situation where the rear pointer reaches the end of the array while there is still free space at the front — this is called a ‘phantom overflow’. To solve this, circular queues reuse vacant slots by wrapping both pointers around to the beginning of the array. Circular queues are more efficient in memory usage but require careful handling of pointer wrap-around and the condition for a full queue, often leaving one free slot to distinguish full from empty.
在用数组实现的线性队列中，反复入队和出队可能导致这样一种情况：队尾指针已达到数组末尾，而数组前端仍有空闲空间——这被称为“假溢出”。为解决这一问题，循环队列将两个指针回绕到数组起始位置，从而重用空闲槽位。循环队列在内存使用上更为高效，但需要小心处理指针回绕以及队列已满的条件，通常留出一个空闲槽位来区分队列满与空。
8. Applications of Stacks | 栈的应用
Stacks are used in many areas of computing. One classic application is reverse Polish notation (RPN) evaluation, where operands are pushed onto a stack and operators pop them off and push the result back. Another is bracket matching in programming language compilers, where each opening bracket is pushed and popped when a corresponding closing bracket appears. Stacks are also crucial for managing subroutine calls through the call stack, storing return addresses and local variables.
栈在计算领域有许多应用。一个经典应用是逆波兰表示法求值，操作数被压入栈，运算符将其弹出并将结果压回。另一个应用是编程语言编译器中的括号匹配，每遇到一个左括号就压栈，遇到匹配的右括号则出栈。栈对于通过调用栈管理子程序调用也至关重要，用于存储返回地址和局部变量。
9. Applications of Queues | 队列的应用
Queues are ubiquitous in operating systems and networking. Print spooling uses a queue to store documents waiting to be printed, ensuring they are handled on a first-come, first-served basis. Keyboard buffers also use a circular queue to store keystrokes until the processor is ready to handle them. In CPU scheduling, ready queues hold processes awaiting execution. Any scenario that requires buffering or inter-process communication often relies on the FIFO nature of queues.
队列在操作系统和网络中无处不在。打印假脱机使用队列存储等待打印的文档，确保按先到先服务的原则处理。键盘缓冲区也利用循环队列存储击键，直到处理器准备好处理它们。在 CPU 调度中，就绪队列保存等待执行的进程。任何需要缓冲或进程间通信的场景，往往都依赖队列的 FIFO 特性。
10. Implementation Using Arrays vs Linked Lists | 数组实现与链表实现对比
IGCSE CIE primarily deals with array-based implementations because of their simplicity. With arrays, stack and queue sizes are fixed at compile time, making overflow handling crucial. However, dynamic data structures like linked lists can also be used. A linked-list stack has no predefined capacity, but each node requires extra memory for a pointer. The syllabus may ask about the advantages and disadvantages of each: arrays offer direct index access and simplicity, while linked lists provide flexibility and no overflow unless memory is exhausted.
IGCSE CIE 主要涉及基于数组的实现，因为它们较为简单。使用数组时，栈和队列的大小在编译时即固定，因此溢出处理非常关键。然而，也可以使用链表等动态数据结构。链表实现的栈没有预定义的容量，但每个节点需要额外的指针内存。考纲可能会问到每种实现的优缺点：数组提供直接索引访问和简单性，而链表提供灵活性，除非内存耗尽，否则不会溢出。
11. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧
When tracing stack or queue operations, always update the pointer values carefully. A common mistake is to pop without checking for underflow, or to push onto an already full structure. In pseudocode questions, remember to increment or decrement pointers in the correct order; for instance, with a stack starting at SP = 0, you should first increment SP, then store the item. For a queue, do not confuse front and rear pointers. In circular queue problems, remember to use modulo arithmetic to wrap around the index: rear = (rear + 1) MOD maxSize. Practice drawing diagrams and trace tables to visualize pointer movements.
在跟踪栈或队列操作时，务必仔细更新指针值。一个常见错误是未检查下溢就出栈，或者向已满的结构压栈。在伪代码题中，要记住以正确顺序递增或递减指针；例如，对于从 SP = 0 开始的栈，应先递增 SP，再存储元素。对于队列，不要混淆队首指针和队尾指针。在循环队列问题中，记得使用取模运算回绕索引：rear = (rear + 1) MOD maxSize。通过绘制图表和跟踪表来可视化指针移动，多加练习。
12. Summary and Key Differences | 总结与关键区别
Both stacks and queues store data sequentially but differ fundamentally in their access policies: LIFO vs FIFO. The table below summarises their key attributes, operations, and typical applications. Understanding these differences not only prepares you for direct comparison questions but also helps you choose the right structure for a given algorithmic problem.
栈和队列都按顺序存储数据，但在访问策略上有根本区别：LIFO 与 FIFO。下表总结了它们的关键属性、操作和典型应用。理解这些区别不仅有助于你回答直接比较类问题，还能帮助你在给定算法问题中选择正确的结构。
| Attribute | 属性 | Stack | 栈 | Queue | 队列 |
|---|---|---|
| Principle | 原则 | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Insertion | 插入 | Push at the top | Enqueue at the rear |
| Removal | 移除 | Pop from the top | Dequeue from the front |
| Pointers | 指针 | Stack pointer (SP) | Front pointer and rear pointer |
| Overflow check | 溢出检查 | SP = maxSize | (rear + 1) MOD maxSize = front (circular) |
| Underflow check | 下溢检查 | SP = 0 or -1 (base convention) | front = rear (or similar sentinel) |
| Key Uses | 主要用途 | Expression evaluation, backtracking, undo, call stack | Print spooler, keyboard buffer, process scheduling |
By internalizing the operations and border cases outlined above, and by practising past paper trace exercises, you will be fully equipped to tackle any IGCSE CIE question on stacks and queues. The key is to visualize the data movement and always think in terms of the LIFO or FIFO principle.
通过牢记上述操作和边界情况，并通过练习历年真题中的跟踪练习，你将完全有能力应对任何有关栈和队列的 IGCSE CIE 考题。关键在于将数据移动可视化，并始终以 LIFO 或 FIFO 原则进行思考。
Published by TutorHao | IGCSE CIE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导