📚 GCSE Edexcel Computer Science: Stacks and Queues Exam Essentials | GCSE Edexcel 计算机：栈与队列 考点精讲
Stack and queue are fundamental data structures in computer science, and they form a key topic in the GCSE Edexcel Computer Science specification. Understanding the Last-In-First-Out (LIFO) behaviour of a stack and the First-In-First-Out (FIFO) behaviour of a queue is crucial for solving practical problems and answering exam questions. This revision guide breaks down the essential concepts, operations, applications, and common pitfalls, with clear examples and bilingual explanations to help you achieve top marks.
栈和队列是计算机科学中基本的数据结构，也是 GCSE Edexcel 计算机课程的核心考点。理解栈的后进先出（LIFO）行为和队列的先进先出（FIFO）行为，对于解决实际问题和应对考试至关重要。本复习指南将拆解基本概念、操作、应用以及常见错误，通过清晰的示例和双语解释，帮助你取得高分。
1. Introduction to Abstract Data Types (ADTs) | 抽象数据类型简介
An abstract data type (ADT) is a model for a data structure that defines the type of data it can hold and the operations that can be performed on it, without specifying how these operations are implemented. Stacks and queues are two classic examples of ADTs that can be implemented using arrays or linked lists. In an exam, you need to focus on their logical behaviour, not the underlying code.
抽象数据类型（ADT）是一种数据结构的模型，它定义了可以保存的数据类型以及可以执行的操作，但不指定这些操作的实现方式。栈和队列就是两个典型的 ADT 例子，它们可以用数组或链表实现。考试中，你需要关注它们的逻辑行为，而不是底层代码。
2. What is a Stack? | 什么是栈？
A stack is an ordered collection of items where the addition of new items and the removal of existing items always take place at the same end. This end is called the ‘top’ of the stack. You can think of a stack like a pile of plates: you can only take the top plate or place a new plate on top. Because the last item added is the first item removed, a stack follows the Last-In-First-Out (LIFO) principle.
栈是一个有序的集合，其中新元素的加入和已有元素的移除总是在同一端点进行。这个端点称为栈“顶”。你可以把栈想象成一叠盘子：只能拿走最上面的盘子，或者在顶部放一个新盘子。由于最后加入的元素最先被移除，栈遵循后进先出（LIFO）原则。
A stack typically has a maximum capacity; if you try to add an element to a full stack, a stack overflow error occurs. Similarly, trying to remove an element from an empty stack results in a stack underflow.
栈通常有最大容量；如果试图向已满的栈添加元素，会发生栈溢出错误。类似地，试图从空栈移除元素会导致栈下溢。
3. Stack Operations: Push, Pop, Peek/Top | 栈的操作：压入、弹出、查看栈顶
Push – Adds an element to the top of the stack. The stack must not be full; otherwise, an overflow occurs.
Push（压入）- 将一个元素添加到栈顶。栈不能是满的，否则会发生溢出。
Pop – Removes and returns the element at the top of the stack. The stack must not be empty; otherwise, an underflow error occurs.
Pop（弹出）- 移除并返回栈顶元素。栈不能为空，否则会发生下溢错误。
Peek (or Top) – Returns the top element without removing it. This allows you to inspect the next element to be popped, but does not change the stack.
Peek（或 Top，查看栈顶）- 返回栈顶元素但不移除它。这样可以查看将要弹出的元素，而不改变栈。
4. LIFO Principle and Stack Examples | 后进先出原理与栈示例
Consider the following operations on an initially empty stack: Push 5, Push 3, Push 8, Pop, Push 2, Pop, Pop. The table below tracks the stack contents after each operation, where the rightmost element is the top.
考虑对初始为空的栈执行以下操作：Push 5, Push 3, Push 8, Pop, Push 2, Pop, Pop。下表追踪每次操作后的栈内容，其中最右侧元素为栈顶。
| Operation | Stack (top → right) |
|---|---|
| Start | [ ] |
| Push 5 | [5] |
| Push 3 | [5, 3] |
| Push 8 | [5, 3, 8] |
| Pop | [5, 3] (returns 8) |
| Push 2 | [5, 3, 2] |
| Pop | [5, 3] (returns 2) |
| Pop | [5] (returns 3) |
Notice that the last element pushed (8) is the first to be popped, confirming the LIFO behaviour. Such tracing questions are common in Edexcel exams.
请注意，最后压入的元素（8）最先被弹出，这证实了 LIFO 行为。这类追踪题在 Edexcel 考试中很常见。
5. Stack Applications | 栈的应用
The call stack is used by programs to manage function calls. When a function is called, its return address and local variables are pushed onto the stack; when the function returns, this information is popped. This is why stack overflow errors often occur in infinite recursion.
调用栈被程序用来管理函数调用。当调用一个函数时，其返回地址和局部变量被压入栈；当函数返回时，这些信息被弹出。这就是为什么无限递归经常导致栈溢出错误。
Undo functionality in applications uses a stack to record actions. Each action is pushed onto the stack; the ‘undo’ command pops the most recent action and reverses it.
应用程序中的撤销功能利用栈来记录操作。每次操作被压入栈；“撤销”命令会弹出最近的操作并反转它。
Compilers and interpreters use a stack to check for balanced parentheses, brackets, and braces by pushing opening symbols and popping when closing symbols appear.
编译器和解释器使用栈来检查括号、方括号和大括号是否匹配，通过将开符号压入栈并在遇到闭符号时弹出。
6. Implementing a Stack with an Array | 用数组实现栈
A stack can be implemented using a one-dimensional array and an integer variable ‘top’ that holds the index of the top element. Initially, top is set to -1 indicating an empty stack. The maximum capacity is defined by the array size.
栈可以用一维数组和一个整数变量“top”来实现，top 保存栈顶元素的索引。初始时，top 被设为 -1，表示空栈。最大容量由数组大小决定。
The push operation: Check if the stack is full (top == maxSize – 1). If not, increment top and store the new item at array[top]. If full, report overflow.
压入操作：检查栈是否已满（top == maxSize – 1）。如果未满，将 top 加 1，并将新元素存储到 array[top]。如果已满，报告溢出。
The pop operation: Check if the stack is empty (top == -1). If not, copy the element at array[top], decrement top, and return the copied element. If empty, report underflow.
弹出操作：检查栈是否为空（top == -1）。如果不为空，复制 array[top] 处的元素，将 top 减 1，并返回复制的元素。如果为空，报告下溢。
7. What is a Queue? | 什么是队列？
A queue is an ordered collection of items where items are added at one end (called the ‘rear’ or ‘back’) and removed from the other end (called the ‘front’). This is analogous to a line of people waiting: the first person to join the queue is the first person to be served. Hence, a queue follows the First-In-First-Out (FIFO) principle.
队列是一个有序的集合，其中元素在一端（称为“队尾”或“后端”）添加，在另一端（称为“队首”或“前端”）移除。这类似于排队等候的人群：第一个加入队伍的人第一个得到服务。因此，队列遵循先进先出（FIFO）原则。
Like stacks, queues have a limited capacity. Trying to enqueue into a full queue results in an overflow; trying to dequeue from an empty queue leads to an underflow.
和栈一样，队列也有容量限制。试图在已满的队列入队会导致溢出；从空队列出队会导致下溢。
8. Queue Operations: Enqueue, Dequeue, Peek | 队列操作：入队、出队、查看队首
Enqueue – Adds an element to the rear of the queue, provided it is not full. The rear pointer is updated to point to the new element.
Enqueue（入队）- 将一个元素添加到队尾，前提是队列未满。rear 指针会更新为指向新元素。
Dequeue – Removes and returns the element at the front of the queue, provided the queue is not empty. The front pointer is then advanced (or wrapper in a circular queue).
Dequeue（出队）- 移除并返回队首元素，前提是队列非空。然后 front 指针向前移动（或在循环队列中绕回）。
Peek (or Front) – Returns the front element without removing it, allowing a check on what will be dequeued next. This does not move any pointers.
Peek（或 Front，查看队首）- 返回队首元素但不移除它，以便查看下一个将要出队的元素。这不会移动任何指针。
9. FIFO Principle and Queue Examples | 先进先出原理与队列示例
Perform these operations on an initially empty linear queue with capacity 5: Enqueue 5, Enqueue 3, Dequeue, Enqueue 8, Dequeue, Dequeue. The table below shows the queue contents and the front/rear pointers after each step. The front element is the leftmost in the stored sequence.
对初始为空且容量为5的线性队列执行以下操作：Enqueue 5, Enqueue 3, Dequeue, Enqueue 8, Dequeue, Dequeue。下表显示了每一步后的队列内容及 front/rear 指针。队首元素是存储序列中最左边的。
| Operation | Queue contents | front index | rear index |
|---|---|---|---|
| Start | [ ] | 0 | -1 |
| Enqueue 5 | [5] | 0 | 0 |
更多咨询请联系16621398022（同微信）
CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导