A-Level CIE Computer Science: Stacks and Queues | 栈与队列考点精讲

📚 A-Level CIE Computer Science: Stacks and Queues | 栈与队列考点精讲

Stacks and queues are fundamental abstract data types (ADTs) in computer science, crucial for managing data in a structured order. In CIE A-Level Computer Science, you need to master their principles, operations, implementation, and applications. This guide covers all essential exam points.

栈与队列是计算机科学中基础的抽象数据类型(ADT)，对于按特定顺序管理数据至关重要。在 CIE A-Level 计算机科学中，你需要掌握它们的原理、操作、实现方式和应用。本指南涵盖所有核心考点。

1. Data Structures Overview | 数据结构概述

An abstract data type (ADT) defines a logical model for data and the allowed operations, without specifying the underlying implementation. The stack and queue are two classic ADTs that organise data in collections with restricted access patterns. Understanding these structures is vital because they appear in everything from recursion and expression evaluation to scheduling and buffering.

抽象数据类型(ADT)定义数据的逻辑模型和允许的操作，而不指定底层实现。栈和队列是两种经典的ADT，它们以受限访问模式组织集合中的数据。理解这些结构至关重要，因为它们出现在递归、表达式求值、调度和缓冲等方方面面。

The CIE syllabus expects you to differentiate between static and dynamic implementations, trace algorithms, and convert between infix, prefix, and postfix expressions. Both stacks and queues can be implemented using arrays or linked lists, each with trade-offs in memory and performance.

CIE 大纲要求你区分静态和动态实现，追踪算法，并在中缀、前缀和后缀表达式之间进行转换。栈和队列都可以用数组或链表实现，各有内存和性能上的权衡。

2. Stack: Definition and LIFO Principle | 栈：定义与后进先出原则

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of a stack of plates: you can only take the top plate off without disturbing the rest. In a stack, all insertions and deletions occur at one end, called the top. The other end is the base. Only the top element is directly accessible.

栈是一种遵循后进先出(LIFO)原则的线性数据结构。最后加入栈的元素第一个被移除。想象一叠盘子：你只能取下最上面的盘子，而不影响下面的。在栈中，所有插入和删除操作都在称为栈顶的一端进行，另一端是栈底。只有栈顶元素可以直接访问。

This restriction makes stacks useful for reversing data, backtracking, and managing nested structures. The LIFO behaviour can be visualised by pushing items onto the stack and popping them off. If we push A, B, C in order, popping will yield C, B, A.

这种限制使得栈在反转数据、回溯和管理嵌套结构方面非常有用。LIFO 行为可以通过向栈中压入元素和弹出元素来可视化。如果我们依次压入 A、B、C，弹出顺序将是 C、B、A。

3. Stack Operations | 栈的基本操作

The standard operations defined for a stack ADT 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 whether the stack is empty; isFull() checks whether the stack has reached its capacity (relevant for fixed-size array implementations). All these operations have a time complexity of O(1) when implemented properly, making stacks extremely efficient.

栈 ADT 定义的标准操作有：push(元素) 将元素添加到栈顶；pop() 移除并返回栈顶元素；peek() 或 top() 返回栈顶元素但不移除；isEmpty() 检查栈是否为空；isFull() 检查栈是否已满（针对固定大小实现）。当实现得当时，所有这些操作的时间复杂度均为 O(1)，使得栈非常高效。

If pop() or peek() is called on an empty stack, an error (underflow) occurs. Similarly, pushing onto a full static stack raises an overflow error. The CIE exam may ask you to write pseudocode for these operations or to state the contents of a stack after a sequence of commands.

如果在空栈上调用 pop() 或 peek()，将发生错误（下溢）。同样，向已满的静态栈压入元素会引发溢出错误。CIE 考试可能会要求你为这些操作编写伪代码，或者叙述一系列命令后栈的内容。

4. Implementing a Stack with an Array | 用数组实现栈

A stack can be implemented using a static array, where a pointer (variable) keeps track of the top index. Initially, top is set to -1 to indicate an empty stack. Pushing increments top and stores the item; popping retrieves the item at top and then decrements top.

栈可以用静态数组实现，其中用一个指针（变量）记录栈顶索引。初始化时，top 设置为 -1 表示空栈。入栈操作增加 top 并存储元素；出栈取回 top 处的元素，然后将 top 减1。

Pseudocode for push on an array-based stack of size MAX:

基于数组的栈（大小为 MAX）的入栈伪代码：

PROCEDURE push(item)
    IF top = MAX-1 THEN
        OUTPUT "Stack Overflow"
    ELSE
        top ← top + 1
        stack[top] ← item
    ENDIF
ENDPROCEDURE

Pseudocode for pop:

出栈伪代码：

FUNCTION pop() RETURNS DataType
    IF top = -1 THEN
        OUTPUT "Stack Underflow"
        RETURN null
    ELSE
        item ← stack[top]
        top ← top - 1
        RETURN item
    ENDIF
ENDFUNCTION

The main disadvantage of an array-based stack is its fixed maximum size. If we need to grow beyond the limit, dynamic allocation is necessary. Otherwise, this implementation is simple and memory-efficient.

基于数组的栈的主要缺点是固定最大容量。如果需要超出限制，则需要动态分配。除此之外，这种实现简单且内存效率高。

5. Implementing a Stack with a Linked List | 用链表实现栈

A dynamic stack can be implemented using a singly linked list, where the top pointer points to the head node. Pushing creates a new node, inserts it at the head, and updates the top pointer. Popping removes the head node and updates top to the next node. This implementation does not suffer from overflow limits (apart from memory exhaustion), and all operations remain O(1).

动态栈可以使用单链表实现，其中栈顶指针指向头节点。入栈创建新节点，将其插入头部，并更新 top 指针。出栈移除头节点，并将 top 更新为下一个节点。这种实现不受溢出限制（除内存耗尽外），所有操作仍为 O(1)。

However, a linked-list stack requires extra memory for node pointers and is slightly slower due to dynamic memory allocation. Common exam questions ask you to draw the state of a linked list stack after a series of push/pop operations or to write pseudocode for node manipulation. Ensure you can manage the top pointer correctly when nodes are added or removed.

然而，链表栈需要额外的内存来存储节点指针，并且由于动态内存分配，速度略慢。常见的考题要求你画出经过一系列压入/弹出操作后链表栈的状态，或编写节点操作的伪代码。确保在添加或移除节点时能正确管理 top 指针。

6. Applications of Stacks | 栈的应用

Stacks are used in many areas of computing:

栈在计算的许多领域都有应用：

Function Call Stack: When a function is called, its parameters, return address, and local variables are pushed onto the call stack. When the function returns, this frame is popped. This enables recursion and nested subroutine calls.

函数调用栈： 当函数被调用时，其参数、返回地址和局部变量被压入调用栈。当函数返回时，该帧被弹出。这使得递归和嵌套子程序调用成为可能。

Expression Evaluation: Stacks are used to convert infix expressions (e.g., 3+5×

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

A-Level CIE Computer Science: Stacks and Queues | 栈与队列考点精讲