📚 Mastering Operations on Stacks, Queues and Linked Lists | 精通栈、队列和链表操作
Linear data structures form the backbone of efficient algorithm design, and understanding their core operations is essential for success in Edexcel A-Level Computer Science. This revision guide breaks down the standard operations on stacks, queues and linked lists, using clear pseudocode, real-world analogies and exam-focused explanations.
线性数据结构是高效算法设计的基础，掌握它们的核心操作对 Edexcel A-Level 计算机科学考试至关重要。这份复习指南通过清晰的伪代码、现实类比和紧扣考点的解释，详细拆解了栈、队列和链表的标准操作。
1. Introduction to Linear Data Structures | 线性数据结构简介
A linear data structure organises elements in a sequential order where each element, except the first and last, has a unique predecessor and successor. The three fundamental linear structures examined in Edexcel are stacks, queues and linked lists. They differ in how elements are inserted and removed, which directly affects their use cases and algorithm efficiency.
线性数据结构将元素按顺序组织，除第一个和最后一个外，每个元素都有唯一的前驱和后继。Edexcel 考试涉及的三种基本线性结构是栈、队列和链表。它们在元素的插入和删除方式上各不相同，这直接影响了它们的应用场景和算法效率。
2. The Stack – LIFO Principle | 栈 —— 后进先出原则
A stack follows the Last-In-First-Out (LIFO) rule: the most recently added element is the first to be removed. Think of a stack of plates in a cafeteria – you take the top plate first. In computer science, stacks are used for tracking function calls, undo mechanisms, and expression evaluation.
栈遵循后进先出 (LIFO) 规则：最近添加的元素最先被移除。想象自助餐厅里的一叠盘子 —— 你总是先拿最上面的那个。在计算机科学中，栈用于跟踪函数调用、实现撤销功能以及表达式求值。
3. Stack Operations: Push, Pop, Peek | 栈操作：压入、弹出、窥视
The primary stack operations are push, pop and peek (or top). Push adds an element to the top of the stack; if the stack is implemented with a fixed-size array, a push on a full stack causes overflow. Pop removes and returns the top element; attempting to pop from an empty stack results in underflow. Peek returns the top element without removing it, allowing you to inspect the stack’s state. All three operations run in O(1) constant time because no shifting is needed.
主要的栈操作是 push（压入）、pop（弹出）和 peek（窥视）。Push 将一个元素添加到栈顶；如果用固定大小的数组实现栈，对已满的栈执行 push 会导致溢出。Pop 移除并返回栈顶元素；试图从空栈中弹出元素会导致下溢。Peek 返回栈顶元素但不移除它，让你能查看栈的状态。这三种操作都在 O(1) 常数时间内完成，因为不需要移动其他元素。
- Push(item): top <- top + 1; stack[top] <- item
- Pop(): IF top = -1 THEN UNDERFLOW; item <- stack[top]; top <- top - 1; RETURN item
- Peek(): IF top = -1 THEN UNDERFLOW; RETURN stack[top]
4. Applications of Stacks | 栈的应用场景
Stacks are used extensively in system software. The call stack stores return addresses when functions are called, and local variables are destroyed in LIFO order when functions return. In compilers, stacks help convert infix expressions like (A + B) * C to postfix notation A B + C * for easier evaluation. The depth-first search algorithm also relies on a stack – either explicitly or via recursion.
栈在系统软件中广泛应用。调用栈在函数调用时存储返回地址，局部变量在函数返回时按 LIFO 顺序销毁。在编译器中，栈有助于将中缀表达式如 (A + B) * C 转换为后缀表达式 A B + C *，以便于求值。深度优先搜索算法也依赖栈 —— 无论是显式地使用栈还是通过递归。
5. The Queue – FIFO Principle | 队列 —— 先进先出原则
A queue operates on the First-In-First-Out (FIFO) principle. Elements enter at the rear and leave from the front, much like a line of people waiting for a bus. Queues are essential for buffering data streams, managing print jobs, and scheduling processes in an operating system.
队列遵循先进先出 (FIFO) 原则。元素从队尾进入，从队首离开，就像排队等公交车的人群。队列对于缓冲数据流、管理打印作业以及操作系统中的进程调度至关重要。
6. Queue Operations: Enqueue, Dequeue | 队列操作：入队、出队
The two fundamental queue operations are enqueue and dequeue. Enqueue adds an item to the rear pointer and increments it; dequeue removes the item at the front pointer and increments that pointer. In a linear array implementation without optimisation, the queue can suffer from ‘drifting’ where unused slots appear at the front, causing a false overflow even when space is available. Both operations should be O(1).
队列的两个基本操作是 enqueue（入队）和 dequeue（出队）。Enqueue 将元素添加到队尾指针处，并递增该指针；dequeue 移除队首指针处的元素，并递增该指针。在不优化的线性数组实现中，队列会出现“漂移”现象，队首出现未使用的空位，导致在有空间的情况下出现假溢出。两种操作都应为 O(1)。
- Enqueue(item): IF rear = maxSize-1 THEN OVERFLOW; rear <- rear + 1; queue[rear] <- item
- Dequeue(): IF front > rear THEN UNDERFLOW; item <- queue[front]; front <- front + 1; RETURN item
7. Circular Queues and Priority Queues | 循环队列与优先队列
A circular queue overcomes the drift problem by connecting the rear and front of the array in a circular buffer. When the rear reaches the end, it wraps around to index 0 if space exists. This maximises storage use. A priority queue assigns each element a priority; the dequeue operation removes the element with the highest priority, not necessarily the oldest. Priority queues are commonly implemented using a heap data structure for O(log n) insertion and removal.
循环队列通过将数组的队尾和队首连接成一个环形缓冲区来克服漂移问题。当队尾指针到达末尾时，如果有空间，它会绕回到索引 0 处。这最大限度地利用了存储空间。优先队列为每个元素分配一个优先级；出队操作移除优先级最高的元素，而不一定是最早加入的元素。优先队列通常使用堆数据结构实现，以获得 O(log n) 的插入和删除性能。
8. Linked Lists – Dynamic Memory | 链表 —— 动态内存
Unlike arrays, a linked list stores each element in a separate node that contains a data field and a pointer (or link) to the next node. This dynamic structure can grow and shrink at runtime without the need for contiguous memory. Linked lists form the basis of many advanced data structures and are heavily examined in Edexcel A-Level.
与数组不同，链表将每个元素存储在一个单独的节点中，节点包含数据域和一个指向下一节点的指针（或链接）。这种动态结构可以在运行时增长和收缩，无需连续内存。链表是许多高级数据结构的基础，且在 Edexcel A-Level 考试中是重点考查内容。
9. Singly Linked List Operations: Insertion, Deletion, Traversal | 单向链表操作：插入、删除、遍历
In a singly linked list, each node points only to its successor. The three core operations are insertion (at head, tail, or a given position), deletion (removing a node by value or position), and traversal (visiting each node from head to tail). Insertion at the head is O(1): create a new node, set its next pointer to the current head, then update head. Deletion finds the predecessor of the target node, updates its next pointer to bypass the target, and then frees memory. Traversal uses a temporary pointer that moves stepwise until it becomes null.
在单向链表中，每个节点只指向其后继。三个核心操作是插入（在头部、尾部或指定位置）、删除（按值或位置移除节点）和遍历（从头到尾访问每个节点）。在头部插入是 O(1)：创建新节点，将其 next 指针指向当前 head，然后更新 head。删除操作需要找到目标节点的前驱，更新其 next 指针以绕过目标节点，然后释放内存。遍历用一个临时指针逐步移动，直到变为 null。
- InsertAtHead(list, data): newNode <- new Node(data); newNode.next <- list.head; list.head <- newNode
- DeleteNode(list, target): IF list.head is null RETURN; IF list.head.data = target THEN list.head <- list.head.next; RETURN; ELSE prev <- list.head; WHILE prev.next != null AND prev.next.data != target DO prev <- prev.next; IF prev.next != null THEN prev.next <- prev.next.next
10. Doubly Linked Lists and Their Operations | 双向链表及其操作
A doubly linked list node has two pointers: one to the next node and one to the previous node. This bidirectional traversal enables more efficient deletion when only the node to be deleted is given – no need to scan for the predecessor. Insertion and deletion require updating both the next and previous pointers of adjacent nodes. The memory overhead is higher, but operations like reversing the list become simpler.
双向链表的节点有两个指针：一个指向下一个节点，一个指向前一个节点。这种双向遍历使得在只知道要删除的节点时，删除操作更高效 —— 无需遍历查找前驱。插入和删除需要同时更新相邻节点的 next 和 previous 指针。内存开销更大，但像反转列表这样的操作变得更简单。
11. Comparing Stacks, Queues and Linked Lists | 栈、队列与链表的比较
Each linear structure excels in specific scenarios. Stacks provide strict LIFO access ideal for recursive backtracking. Queues enforce FIFO and are indispensable for fair scheduling. Linked lists offer flexible dynamic storage with fast insertions and deletions, but at the cost of extra pointer memory and no random access. In A-Level exams, you may be asked to justify choosing a stack over a queue for parsing or to compare the trade-offs between array-based and linked-list-based implementations.
每种线性结构都在特定场景下表现出色。栈提供严格的 LIFO 访问，非常适合递归回溯。队列强制遵循 FIFO，对于公平调度不可或缺。链表提供灵活的动态存储，插入和删除速度快，但代价是额外的指针内存且不支持随机访问。在 A-Level 考试中，你可能需要说明在解析任务中为什么选择栈而不是队列，或者比较基于数组和基于链表的实现之间的权衡。
| Operation | Stack (Array) | Queue (Array) | Singly Linked List |
|---|---|---|---|
| Access | O(1) top only | O(1) front/rear | O(n) for arbitrary |
| Insert | O(1) push | O(1) enqueue | O(1) at head/tail |
| Delete | O(1) pop | O(1) dequeue | O(1) at head (tail O(n)) |
| Memory | Fixed size | Fixed size | Dynamic, extra pointers |
12. Exam Tips for Edexcel A-Level | Edexcel A-Level 考试技巧
When tackling structured programming questions, always begin by clearly identifying the data structure required. Draw a diagram to track pointer changes step by step. Write pseudocode using consistent indentation and variable names like ‘top’, ‘front’, ‘rear’, ‘head’ as defined in the Edexcel specification. If a question asks about overflow or underflow, always state the condition explicitly. Finally, practice tracing code for mixed operations – pushing and popping on a stack, or inserting and deleting in a linked list – to build fluency with pointer logic.
解答结构化编程题时，首先要明确所需的数据结构。用图示逐步跟踪指针的变化。书写伪代码时使用一致的缩进和符合 Edexcel 规范的变量名，如 ‘top’、’front’、’rear’、’head’。如果题目涉及溢出或下溢，务必明确陈述条件。最后，多练习混合操作的代码追踪 —— 如在栈上连续压入和弹出，或在链表中插入和删除 —— 以熟练掌握指针逻辑。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply