📚 Implementing and Using Data Structures: Stacks, Queues, and Linked Lists | 数据结构实现与应用：栈、队列与链表
In A-Level Computer Science, mastery of fundamental data structures such as stacks, queues and linked lists is essential for solving problems efficiently and understanding how low-level memory management works. This article explores the abstract data types (ADTs) behind these structures, their combined operations and practical implementations using pseudocode and array/list representations. Each concept is broken down with paired English–Chinese explanations, mimicking the style of Pearson Edexcel’s active learning resources for the programming paper.
在 A-Level 计算机科学中，掌握栈、队列和链表等基础数据结构，对于高效解决问题、理解底层内存管理至关重要。本文将探讨这些结构背后的抽象数据类型（ADT），它们的组合操作，以及用伪代码和数组/列表表示的实际实现。每个概念都采用英中对照解释的方式，模仿 Edexcel 编程试卷中 Pearson ActiveLearn 资源的风格。
1. Abstract Data Types in Programming | 编程中的抽象数据类型
An Abstract Data Type (ADT) defines a collection of data and the set of operations that can be performed on that data, without specifying the underlying implementation. It describes what the data structure does, not how it stores the data.
抽象数据类型（ADT）定义了一组数据以及可对这些数据执行的操作集合，而不指定底层实现。它描述了数据结构能做什么，而不是怎样存储数据。
In the Edexcel specification, students must understand ADTs such as stacks, queues and linked lists separately from their physical representation in memory. This separation allows a programmer to change the internal storage (e.g. from an array to a linked list) without altering the interface.
在 Edexcel 大纲中，学生必须将栈、队列和链表等 ADT 与它们在内存中的物理表示区分开来。这种分离允许程序员更改内部存储方式（例如从数组换成链表），而无需修改接口。
Common ADT operations are expressed as function signatures: push(item), pop(), enqueue(item), dequeue(), isEmpty(), isFull(). The behaviour of these functions must remain consistent regardless of how the data structure is implemented.
常见的 ADT 操作以函数签名来表达：push(item)、pop()、enqueue(item)、dequeue()、isEmpty()、isFull()。这些函数的行为必须保持一致，不论数据结构如何实现。
2. The Stack ADT and Core Operations | 栈的 ADT 与核心操作
A stack is a Last-In-First-Out (LIFO) structure. The last element added to the stack is the first one to be removed. The key operations are push, pop, peek (or top), and checking whether the stack is empty or full.
栈是一种后进先出（LIFO）结构。最后压入栈的元素最先被移除。关键操作包括 push、pop、peek（或 top），以及检查栈空或栈满。
In a bounded stack implemented with an array, a pointer called top keeps track of the current highest index. When top equals -1, the stack is empty; when top equals the maximum index, the stack is full and push should raise an overflow error.
在用数组实现的定长栈中，一个名为 top 的指针跟踪当前最高索引。当 top 等于 -1 时栈空；当 top 等于最大索引时栈满，push 操作应引发溢出错误。
Pseudocode for push(item): if top < maxSize-1 then top ← top + 1; stack[top] ← item else output "stack overflow". Pop: if top >= 0 then item ← stack[top]; top ← top - 1; return item else output "stack underflow".
push(item) 的伪代码：if top < maxSize-1 then top ← top + 1; stack[top] ← item else output "stack overflow"。Pop: if top >= 0 then item ← stack[top]; top ← top - 1; return item else output "stack underflow"。
A stack ADT is widely used for expression evaluation, backtracking algorithms, undo mechanisms and managing function calls via a call stack.
栈 ADT 广泛用于表达式求值、回溯算法、撤销机制以及通过调用栈管理函数调用。
3. Implementing a Stack Using Linked Lists | 用链表实现栈
When a stack is implemented with a linked list, each node contains a data field and a pointer to the next node. A top pointer references the head of the list. Push inserts a new node at the head, and pop removes the head node.
当使用链表实现栈时，每个节点包含数据域和指向下一个节点的指针。top 指针引用链表的头节点。push 操作在头部插入新节点，pop 操作移除头节点。
A linked-list-based stack is dynamically sized and never suffers from a fixed-capacity overflow; however, it uses extra memory for the pointers and requires complex memory management in low-level languages.
基于链表的栈是动态大小的，不会出现固定容量导致的溢出问题；然而它需要额外的内存来存储指针，并在低级语言中需要复杂的内存管理。
Pseudocode for linked-list push: newNode ← new Node(data); newNode.next ← top; top ← newNode. Pop: if top = null then error; data ← top.data; top ← top.next; return data.
链表压栈伪代码：newNode ← new Node(data); newNode.next ← top; top ← newNode。弹栈：if top = null then error; data ← top.data; top ← top.next; return data。
This implementation highlights the ADT concept: the user of the stack sees the same interface (push, pop), regardless of whether an array or linked list is used underneath.
这种实现突显了 ADT 的概念：栈的使用者看到的接口（push、pop）相同，无论底层是数组还是链表。
4. The Queue ADT and Variations | 队列 ADT 及其变体
A queue is a First-In-First-Out (FIFO) data structure. Elements are added at the rear and removed from the front. The primary operations are enqueue and dequeue, together with isEmpty and isFull for bounded queues.
队列是一种先进先出（FIFO）的数据结构。元素在队尾添加，从队头移除。主要操作有 enqueue 和 dequeue，以及定长队列的 isEmpty 和 isFull。
A linear queue implemented with an array uses two pointers: front and rear. As items are dequeued, the front index moves forward, leading to unused space at the beginning and potentially a false "full" condition. A circular queue solves this by wrapping the pointers around an array of fixed size.
用数组实现的线性队列使用两个指针：front 和 rear。随着元素出队，front 索引前移，导致数组开头出现未用空间，可能造成“假满”现象。循环队列通过让指针在固定大小的数组上回绕来解决这个问题。
n (rear + 1) mod N = front, assuming one slot is sacrificed to distinguish the two states.
在大小为 N 的循环队列中，rear 和 front 指针以模 N 的方式移动。当 front = rear 时队列为空；当 (rear + 1) mod N = front 时队列为满，这里假设牺牲一个槽位来区分这两种状态。
5. Priority Queues and Linked Implementations | 优先队列与链表实现
A priority queue is an ADT where each element has an associated priority. The element with the highest priority is dequeued first, rather than the element that has been waiting the longest. This can be implemented with an ordered array, an unordered array, a linked list, or a heap.
优先队列是一种 ADT，其中每个元素关联一个优先级。优先级最高的元素先出队，而不是等待最久的元素。它可以用有序数组、无序数组、链表或堆来实现。
With a linked list, insertion can be done in order of descending priority by traversing the list until the correct position is found. Dequeue simply removes the head node. This gives O(n) insertion and O(1) removal.
使用链表时，可以通过遍历链表找到正确位置，按优先级降序插入。dequeue 操作只需移除头节点。这样做插入时间复杂度为 O(n)，移除为 O(1)。
Priority queues are essential in operating system process scheduling, Dijkstra’s algorithm and simulation systems where events must be processed in order of urgency.
优先队列在操作系统进程调度、Dijkstra 算法以及需要按紧急程度处理事件的仿真系统中至关重要。
6. Singly Linked Lists and Node Structures | 单链表与节点结构
A singly linked list consists of a sequence of nodes, each containing a data field and a pointer to the next node. The list is accessed via a head pointer; the last node points to null, indicating the end of the list.
单链表由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。通过头指针访问链表；最后一个节点指向 null，表示链表结束。
Traversal of a singly linked list requires starting at head and following next pointers until null is reached. This sequential access is linear, unlike the random access provided by arrays.
遍历单链表需要从头节点开始，沿着 next 指针前进直到 null。这种顺序访问是线性的，与数组提供的随机访问不同。
Dynamic memory allocation for nodes allows the list to grow and shrink at runtime. Insertion or deletion at the head is efficient (O(1)), but insertion at the tail without a tail pointer requires traversing the entire list (O(n)).
节点的动态内存分配允许链表在运行时增长和收缩。在头部插入或删除是高效的（O(1)），但如果没有尾指针，在尾部插入则需要遍历整个链表（O(n)）。
7. Doubly and Circular Linked Lists | 双向链表与循环链表
A doubly linked list adds a previous pointer to each node, enabling traversal in both directions. This supports more flexible insertion and deletion but requires extra memory and careful pointer updates.
双向链表在每个节点上增加了一个 prev 指针，支持双向遍历。这使得插入和删除更加灵活，但需要额外内存和谨慎的指针更新。
In a circular singly linked list, the last node’s next pointer points back to the head, forming a ring. This allows continuous traversal from any starting point and is useful for applications like round-robin scheduling.
在循环单链表中，最后一个节点的 next 指针回指头节点，形成一个环。这允许从任意起点连续遍历，常用于轮询调度等应用。
Edexcel exam questions often require students to trace pointer changes when inserting a node into a doubly linked list at a given position. The order of reassigning pointers is critical to avoid losing references.
Edexcel 考试中常见的一种题型是要求学生追踪在双向链表指定位置插入节点时的指针变化。指针重新赋值的顺序至关重要，以免丢失引用。
8. Combined Operations: Implementing a Stack with Two Queues | 组合操作：用两个队列实现栈
One classic algorithm that tests understanding of ADTs is implementing a stack using two queues. The idea is to simulate LIFO behaviour with FIFO queues by cleverly rearranging elements.
一个检验 ADT 理解程度的经典算法是用两个队列实现一个栈。其思路是通过巧妙地重新排列元素，用 FIFO 队列模拟 LIFO 行为。
For a pop operation, dequeue all elements from queue1 except the last one, moving them to queue2; dequeue and return the last element of queue1. Then swap the reference between queue1 and queue2 so that queue2 becomes the main storage.
对于 pop 操作，将 queue1 中除最后一个元素外的所有元素出队并移入 queue2；dequeue 并返回 queue1 的最后一个元素。然后交换 queue1 和 queue2 的引用，使 queue2 成为主存储。
Push simply enqueues the new element into queue1. This makes push O(1) and pop O(n). Alternatively, a costly push approach can make pop O(1). Both illustrate the trade-off between time complexity and operation frequency.
Push 只需将新元素入队到 queue1。这样 push 是 O(1)，pop 是 O(n)。也可以采用高代价的 push 使 pop 变成 O(1)。这两种方法均展示了时间复杂度和操作频率之间的权衡。
9. Using Stacks to Evaluate Postfix Expressions | 利用栈计算后缀表达式
A classic use of the stack ADT is the evaluation of postfix (Reverse Polish) expressions. The algorithm scans the expression from left to right: operands are pushed onto the stack; when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back.
栈 ADT 的一个经典应用是计算后缀（逆波兰）表达式。算法从左到右扫描表达式：操作数压入栈；遇到操作符时，弹出所需数量的操作数，执行运算，并将结果压回栈。
For example, evaluating "3 4 + 2 *" involves: push 3, push 4; encounter '+', pop 4 and 3, compute 7, push 7; push 2; encounter '*', pop 2 and 7, compute 14, push 14. The final answer is the top of the stack.
例如，计算 "3 4 + 2 *"：压入 3，压入 4；遇到 '+'，弹出 4 和 3，计算 7，压入 7；压入 2；遇到 '*'，弹出 2 和 7，计算 14，压入 14。最终答案即栈顶元素。
Understanding this algorithm reinforces how stacks can store intermediate results and how the order of operations is controlled without the need for brackets or precedence rules.
理解此算法能够巩固栈如何存储中间结果，以及如何在没有括号和优先级规则的情况下控制运算顺序。
10. Combined Data Structures in Memory: Static vs Dynamic | 内存中的组合数据结构：静态与动态
When comparing array-based and linked-list-based implementations, it is vital to consider memory usage. Arrays require contiguous blocks of memory, which may lead to fragmentation, while linked lists use non-contiguous nodes linked by pointers.
在比较基于数组和基于链表的实现时，考虑内存使用至关重要。数组需要连续的内存块，可能导致碎片化；而链表使用不连续的节点，通过指针链接。
A combined design can incorporate both: e.g., a static array to store priority levels and a linked list at each index to hold tasks of that priority. This hybrid structure balances space efficiency and access speed.
组合设计可以同时包含两者：例如，用静态数组存储优先级级别，并在每个索引处用链表保存该优先级的任务。这种混合结构平衡了空间效率和访问速度。
In Edexcel papers, students may be asked to justify the choice of dynamic vs static data structures for a given scenario, considering factors like maximum size predictability, insertion/deletion frequency and memory constraints.
在 Edexcel 试卷中，学生可能会被要求在给定场景下论证动态与静态数据结构的选择，考虑因素包括最大规模的可预测性、插入/删除频率以及内存限制。
11. Common Mistakes and Debugging Techniques | 常见错误与调试技巧
Pointer mismanagement is the primary source of errors when working with linked structures. Losing a reference to a node by overwriting a pointer before saving it causes memory leaks or dangling pointers. Always update pointers in the correct sequence and use temporary variables to hold references.
指针管理不当是处理链接结构时错误的主要来源。在保存引用之前覆盖指针会导致内存泄漏或悬空指针。务必按正确顺序更新指针，并使用临时变量保存引用。
Off-by-one errors appear frequently in array-based implementations of stacks and queues. For example, confusing the condition for full in a circular queue can result in either overwriting valid data or underutilising the array.
在基于数组的栈和队列实现中，越界错误经常出现。例如，混淆循环队列的满条件可能导致覆盖有效数据或数组利用率不足。
Tracing algorithms with state tables that record pointer values and array contents after each step is an invaluable exam technique. It mirrors the debugging process in a real programming environment.
使用状态表记录每一步后的指针值和数组内容来追踪算法，是一项极为宝贵的考试技巧。这模拟了真实编程环境中的调试过程。
12. Exam Tips and Summary | 考试技巧与总结
When describing ADT operations, always state the preconditions (e.g., stack not empty before pop) and postconditions (e.g., element removed and returned). Use precise pseudocode that matches the Edexcel syntax, with clear assignment arrows and consistent indentation.
在描述 ADT 操作时，务必说明前置条件（例如 pop 前栈非空）和后置条件（例如移除并返回元素）。使用符合 Edexcel 语法的精确伪代码，带有清晰的赋值箭头和一致的缩进。
Stacks, queues and linked lists form the backbone of algorithmic thinking. Combining them forces you to think about data flow and state, which is exactly the skill assessed in the programming paper. Regular practice tracing these structures will save time in exams and deepen your understanding of how higher-level programming languages manage memory.
栈、队列和链表构成了算法思维的支柱。将它们组合使用迫使你思考数据流和状态，这正是编程试卷考查的技能。经常练习追踪这些结构，不仅能为考试节省时间，还能加深你对高级编程语言如何管理内存的理解。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图