📚 GCSE AQA Computer Science: Stacks and Queues | GCSE AQA 计算机：栈与队列 考点精讲
Data structures are fundamental to computer science, and the AQA GCSE specification requires a clear understanding of stacks and queues. These two abstract data types (ADTs) manage collections of elements with specific rules for adding and removing items. Mastering stacks and queues will not only help you answer exam questions but also deepen your appreciation of how software manages data efficiently.
数据结构是计算机科学的基础，AQA GCSE 大纲要求清楚地理解栈和队列。这两种抽象数据类型（ADT）按照特定的规则管理元素集合，用于添加和移除数据项。掌握栈和队列不仅能帮助你解答考试题目，还能加深你对软件如何高效管理数据的理解。
1. Introduction to Abstract Data Types | 抽象数据类型简介
An abstract data type (ADT) is a logical description of how data can be viewed and the operations that can be performed on it, without specifying how these operations are implemented. Stacks and queues are examples of ADTs because they define behaviour (LIFO and FIFO) independently of the underlying programming language or hardware.
抽象数据类型（ADT）是一种逻辑描述，定义了如何看待数据以及可以对数据执行哪些操作，而无需指定这些操作的具体实现方式。栈和队列就是 ADT 的例子，因为它们定义了行为（后进先出和先进先出），与底层的编程语言或硬件无关。
In an exam, you may be asked to identify the ADT from a description of operations or to explain what makes an ADT different from a concrete data structure like an array.
在考试中，你可能会被要求根据操作描述识别 ADT，或者解释 ADT 与数组等具体数据结构的区别。
2. Stacks: Last In, First Out | 栈：后进先出
A stack is a collection of items that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates: you can only take the top plate off, and you can only add a new plate to the top. This restricted access makes stacks suitable for certain problem-solving scenarios.
栈是一种遵循后进先出（LIFO）原则的数据项集合。想象一叠盘子：你只能拿走最顶上的盘子，也只能把新盘子放在最顶上。这种受限的访问方式使栈适用于某些特定问题的解决场景。
The main operations on a stack are push (add an item), pop (remove and return the top item), and peek or top (look at the top item without removing it).
栈上的主要操作有 push（压入，添加一个数据项）、pop（弹出，移除并返回顶部数据项）和 peek 或 top（查看顶部数据项但不移除）。
3. Stack Operations: Push, Pop, and Peek | 栈操作：压入、弹出和查看
Push adds a new element to the top of the stack. Before pushing, you should check that the stack is not full to avoid an overflow error. In a stack implemented with an array, a stack pointer (top) is incremented before or after storing the item depending on the convention.
Push 将一个新增元素添加到栈顶。在执行压入操作之前，应检查栈是否已满，以避免溢出错误。在用数组实现的栈中，根据惯例，会在存储数据项之前或之后递增栈指针（top）。
Pop removes the element currently at the top of the stack and returns it. The stack pointer is decremented. If you try to pop from an empty stack, an underflow error occurs.
Pop 移除当前栈顶的元素并返回它。栈指针会递减。如果试图从一个空栈中弹出元素，则会发生下溢错误。
Peek (or Top) returns the value of the top element without modifying the stack. This is useful when you need to examine the next item to be removed without affecting the stack’s state.
Peek（或 Top）返回栈顶元素的值而不修改栈。当你需要检查即将被移除的下一项而不影响栈的状态时，这个操作非常有用。
4. Implementing a Stack Using an Array | 用数组实现栈
A stack can be implemented using a one-dimensional array and a variable that acts as the stack pointer. Initially, the stack pointer is set to -1 (or 0, depending on the implementation) to indicate an empty stack. When pushing, the pointer is incremented and the new item is placed at that index. When popping, the item at the pointer index is read, then the pointer is decremented.
栈可以使用一维数组和一个作为栈指针的变量来实现。初始时，栈指针通常设置为 -1（或 0，取决于具体实现）以表示空栈。压入时，指针递增，新数据项放在该索引位置。弹出时，读取指针索引处的数据项，然后指针递减。
The array-based stack is simple but has a fixed maximum size, which can lead to overflow if too many items are pushed. A dynamic implementation using a linked list can grow as needed, but AQA GCSE focuses mainly on the static array implementation.
基于数组的栈实现起来很简单，但最大容量是固定的，如果压入的数据项过多，就可能导致溢出。使用链表的动态实现可以根据需要增长，但 AQA GCSE 主要关注静态数组实现。
5. Applications of Stacks | 栈的应用
Stacks are used in many computing contexts. The call stack keeps track of active subroutines or function calls; each time a function is called, a new frame is pushed onto the stack, and when it returns, the frame is popped. This enables recursion and local variable management.
栈在计算领域的许多场景中都有使用。调用栈用于跟踪活动的子程序或函数调用；每次调用一个函数时，就会有一个新的帧被压入栈中，当函数返回时，该帧被弹出。这使得递归和局部变量管理成为可能。
Another common application is the undo feature in applications. Each action you perform is pushed onto a stack; when you press undo, the most recent action is popped and reversed. Syntax parsing, expression evaluation (e.g., reverse Polish notation), and backtracking algorithms also rely on stacks.
另一个常见的应用是应用程序中的撤销功能。你执行的每个操作都被压入栈中；当你按下撤销时，最近的操作被弹出并逆转。语法分析、表达式求值（例如，逆波兰表示法）和回溯算法也依赖于栈。
6. Queues: First In, First Out | 队列：先进先出
A queue is an ADT that works on the First In, First Out (FIFO) principle, exactly like a real-world queue at a checkout. Items join the queue at the back (tail) and leave from the front (head). This ensures fair ordering: the first element added will be the first element removed.
队列是一种按照先进先出（FIFO）原则工作的 ADT，就像现实世界中收银台前的排队一样。数据项在队尾（末尾）加入队列，从队首（头部）离开。这确保了公平的顺序：最先加入的元素将最先被移除。
The key operations are enqueue (add an item to the rear) and dequeue (remove and return the item at the front). You may also see front or peek to inspect the front element without removing it.
关键操作是 enqueue（入队，将一个数据项添加到队尾）和 dequeue（出队，移除并返回队首的数据项）。你还可能见到 front 或 peek，用于查看队首元素而不移除它。
7. Queue Operations: Enqueue, Dequeue, and Front | 队列操作：入队、出队和队首
Enqueue: before adding a new item, check whether the queue is full (if using a static array). If there is space, the rear pointer is updated (often incremented, accounting for wrapping in a circular queue), and the item is stored. The first time an item is enqueued, both front and rear pointers may be set to point to the same location.
Enqueue（入队）：在添加新数据项之前，检查队列是否已满（如果使用静态数组）。如果有空间，则更新队尾指针（通常递增，并考虑到循环队列中的回绕），然后存储该数据项。第一次入队时，队首和队尾指针可能会指向同一个位置。
Dequeue: the item at the front pointer is read and removed, and the front pointer is moved to the next item. If the queue becomes empty after dequeuing, the pointers are reset to indicate an empty state. Dequeuing from an empty queue causes an underflow error.
Dequeue（出队）：读取并移除队首指针处的数据项，然后将队首指针移动到下一个数据项。如果出队后队列变空，则指针
Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导