跳转至

Chapter 3 Lists, Stacks, and Queues

§1 Abstract Data Type(ADT)

【定义】数据类型（Data Type） = { 数据对象集（Data Objects） } ∪ { 操作集（Operations） }

示例：int类型 - 数据对象：{ 0, ±1, ±2, … , INT_MAX（整型最大值）, INT_MIN（整型最小值） } - 操作集：{ +（加）, -（减）, ×（乘）, ÷（除）, %（取余）, … }

【定义】抽象数据类型（Abstract Data Type, ADT） 是一种数据类型，其组织方式使得数据对象的规范（Specification on the Objects）、对象上操作的规范（Specification of the Operations），与数据对象的底层表示（Representation of the Objects）、操作的具体实现（Implementation of the Operations）完全分离。

核心思想：接口与实现解耦（Decouple Interface and Implementation），封装（Encapsulation）数据与操作，上层调用仅需关注操作规范，无需关心底层实现细节。

§2 The List ADT

Definition

  • 数据对象：有限元素（Item）序列 ( item₀, item₁, … , item_{N-1} )，N为线性表长度；N=0时为空表（Empty List）。

  • 核心操作集：

  • 求线性表的长度N（Finding the length, N, of a list）
  • 打印线性表中的所有元素（Printing all the items in a list）
  • 创建一个空表（Making an empty list）
  • 查找线性表中第k个元素（Finding the k-th item from a list, 0 ≤ k < N）
  • 在线性表的第k个元素后插入一个新元素（Inserting a new item after the k-th item of a list, 0 ≤ k < N）
  • 从线性表中删除一个元素（Deleting an item from a list）
  • 查找当前元素的后继元素（Finding next of the current item from a list）
  • 查找当前元素的前驱元素（Finding previous of the current item from a list）

1. Simple Array Implementation of Lists

用连续的内存空间（Continuous Memory Space，数组）存储线性表元素，通过数组下标（Array Index）与元素位置直接映射：array[i] = item_i，元素item_i的存储地址为array + i，物理地址连续，属于顺序映射（Sequential Mapping），即顺序存储结构（Sequential Storage Structure）。

优势 缺陷
随机访问（Random Access）效率极高，Find_Kth（按位查找）操作仅需O(1) 时间 必须提前预估数组最大长度MaxSize，无法动态扩容（Dynamic Expansion）
实现逻辑简单，无需复杂的指针（Pointer）操作 插入（Insertion）、删除（Deletion）操作需要移动大量元素，最坏时间复杂度O(N)，效率低下

2. Linked Lists

用不连续的独立节点（Node）存储元素，每个节点包含数据域（Data Field，存储元素）和指针域（Pointer Field，指向后继节点），通过指针串联节点形成线性结构，无需连续的物理内存，属于链式存储结构（Linked Storage Structure）。

Node Structure Definition（C） 

// 单链表节点结构定义
// typedef：给数据类型起别名；struct：结构体
typedef  struct  list_node  *list_ptr;  // list_ptr：链表指针（list pointer）
typedef  struct  list_node  {
      char        data[4];  // 数据域，存储元素
      list_ptr    next;     // 指针域，指向后继节点（Successor Node）
} list_node;

list_ptr   ptr;  // 头指针（Head Pointer），指向链表第一个节点

Node Linking Example 实现两个节点ZHAO、QIAN的链接： 

list_ptr   N1,  N2;
// 向系统申请节点内存，malloc：Memory Allocation（动态内存分配）
// sizeof：计算数据类型占用的字节数（Byte）
N1 = (list_ptr)malloc(sizeof(struct list_node));
N2 = (list_ptr)malloc(sizeof(struct list_node));
// 赋值数据域
strcpy(N1->data, "ZHAO");
strcpy(N2->data, "QIAN");
// 链接节点，形成链表
N1->next = N2;
N2->next = NULL;  // 空指针（Null Pointer），标记链表结束
ptr = N1;  // 头指针指向链表首节点

注意：程序不同运行环境下，节点的内存地址（Memory Address）可能不同，不影响链表的逻辑结构。

Insertion Operation - 核心需求：在节点node后插入新节点temp（数据为b）

  • 操作步骤（顺序不可颠倒！）： ① temp->next = node->next; 新节点先指向原node的后继节点，保留后续链表地址 ② node->next = temp; 再将node的后继指向新节点，完成插入

  • 时间复杂度：O(1)，仅需修改2个指针，无需移动任何元素。

  • 关键问题：

  • 若两步顺序颠倒，会发生什么？ A：先执行node->next = temp会直接丢失原node后继节点的地址，导致链表断裂（List Break），后续节点完全无法访问。
  • 如何插入新的表头节点？ A：直接插入需要修改头指针，与中间节点插入逻辑不统一。解决方案是引入哑表头节点（Dummy Head Node，也叫哨兵节点 Sentinel Node），让首节点成为哑表头的后继节点，所有插入操作逻辑完全统一。

Deletion Operation - 核心需求：删除节点node，pre为node的前驱节点（Predecessor Node）

  • 操作步骤： ① pre->next = node->next; 前驱节点跳过待删除节点，直接指向其后继，完成链表逻辑上的移除 ② free(node); 释放待删除节点的内存，避免内存泄漏（Memory Leak）

  • 时间复杂度：O(1)，仅需修改指针和释放内存。

  • Q:如何删除链表的第一个节点？ A：无哑表头时，删除首节点需要修改头指针，与中间节点删除逻辑不统一。引入哑表头后，首节点变为哑表头的后继节点，删除逻辑与中间节点完全一致，无需特殊处理。

3. Doubly Linked Circular Lists

单链表只能顺链向后遍历，若需要访问节点的前驱节点，必须从头遍历整个链表，时间复杂度O(N)。例如删除指定节点时，单链表需要先遍历找到其前驱节点，而双向链表可直接访问前驱，解决这一痛点。

Node Structure Definition（C） 每个节点包含左指针、数据域、右指针三个部分： 

// 双向链表节点结构定义
typedef  struct  node  *node_ptr;  // node_ptr：节点指针（node pointer）
typedef  struct  node  {
       node_ptr  llink;  // 左指针（Left Link），指向前驱节点
       element   item;   // 数据域，存储元素
       node_ptr  rlink;  // 右指针（Right Link），指向后继节点
} node;

  • 核心恒等式：ptr = ptr->llink->rlink = ptr->rlink->llink，即节点的后继的前驱、前驱的后继都是节点自身。

  • 带哑表头的双向循环链表结构：

  • 空表（Empty List）：仅包含哑表头节点H，H的llink和rlink都指向自身。
  • 非空表：哑表头H的rlink指向第一个元素节点，最后一个元素节点的rlink指向H；H的llink指向最后一个元素节点，第一个元素节点的llink指向H，形成闭环（Circular Loop）。

Advantages 1. 可直接访问节点的前驱和后继，查找前驱的时间复杂度从O(N)降为O(1)。 2. 插入、删除操作无需提前查找前驱节点，逻辑更简洁，尤其适合频繁双向遍历的场景。

4. Cursor Implementation of Linked Lists

Applicable Scenarios 不支持指针和动态内存分配的编程语言，用数组模拟链表的核心功能，实现与指针链表完全一致的操作接口。

Core Design Ideas 复刻链表的核心特性： 1. 数据存储在一组结构体中，每个结构体包含数据和指向下一个结构体的“指针”（游标Cursor，即数组下标）。 2. 用数组模拟系统全局内存，通过自定义的malloc和free函数管理数组空间，替代C语言的系统内存管理调用。

Cursor Space Structure 定义结构体数组CursorSpace（游标空间），数组的每个元素包含两个字段：

  • Element：数据域，存储元素值

  • Next：游标域，存储下一个元素的数组下标，相当于指针；下标0为空闲空间的管理头节点，Next=0表示链表结束（相当于NULL）。

初始化规则：游标空间下标0~S-1（S为数组最大长度），初始时CursorSpace[i].Next = i+1，CursorSpace[S-1].Next = 0，形成空闲链表（Free List）。

Operation Implementation 1. Customized malloc (Node Application) 

// 模拟malloc，返回空闲节点的数组下标，无空闲节点返回0
int cursor_malloc() {
    int p = CursorSpace[0].Next;  // 取空闲链表的第一个节点
    if (p != 0) {
        CursorSpace[0].Next = CursorSpace[p].Next;  // 更新空闲链表头
    }
    return p;
}
逻辑：从空闲链表头部取出可用节点，更新空闲链表头，返回该节点的下标。

  1. Customized free (Node Release) 
    // 模拟free，将下标为p的节点放回空闲链表
void cursor_free(int p) {
    CursorSpace[p].Next = CursorSpace[0].Next;  // 节点插入空闲链表头部
    CursorSpace[0].Next = p;
}
    将待释放节点插入空闲链表头部，完成内存回收。

Features 1. 接口一致性（Interface Consistency）：游标实现的操作接口与指针实现完全一致，上层调用无需修改任何代码。 2. 性能优势：无需调用系统内存管理函数，运行速度通常显著更快。

Applications of the List ADT

The Polynomial ADT

  • 数据对象：多项式 \(P(x) = a_1 x^{e_1} + a_2 x^{e_2} + \dots + a_n x^{e_n}\)，由一组有序对 <e_i, a_i> 组成，其中a_i为系数（Coefficient），e_i为非负整数指数（Exponent）。

  • 核心操作集：

  • 求多项式的次数（Finding degree, max { ei }, of a polynomial）
  • 两个多项式相加（Addition of two polynomials）
  • 两个多项式相减（Subtraction between two polynomials）
  • 两个多项式相乘（Multiplication of two polynomials）
  • 多项式求导（Differentiation of a polynomial）
Array Implementation

  • 结构定义：用数组下标表示指数，数组值表示对应指数的系数，同时记录多项式的最高次幂。 

    #define MaxDegree 1000  // 预设多项式最大指数（Maximum Degree）
typedef struct {
    int CoeffArray[MaxDegree + 1];  // 系数数组，下标为指数
    int HighPower;                   // 多项式的最高次幂（Highest Power）
} *Polynomial;

  • 优缺点： 优点：实现简单，多项式加减乘的逻辑直观易懂。 缺陷：

  • 必须提前预设最大指数，无法处理超界的高次多项式。
  • 对稀疏多项式（Sparse Polynomial）（非零项极少、指数跨度极大）会造成严重的内存浪费。例如多项式 \(P1(x) = 10x^{1000}+5x^{14}+1\)，需要长度1001的数组，仅3个位置非零，其余全为0。
  • 两个最高次为N1和N2的多项式相乘，时间复杂度为O(N1×N2)，对高次稀疏多项式效率极低。
Linked List Implementation

  • 核心逻辑：每个节点存储多项式的一个非零项，包含系数（Coefficient）、指数（Exponent）、指向后继节点的指针，节点按指数降序（或升序）排列，仅存储非零项，无内存浪费。

  • 节点结构定义： 

    // 多项式节点结构定义
typedef  struct  poly_node   *poly_ptr;  // poly_ptr：多项式指针（polynomial pointer）
struct  poly_node  {
      int       Coefficient;  // 系数（假设为整数）
      int       Exponent;     // 指数
      poly_ptr  Next;         // 指向下一个项的节点
};
typedef  poly_ptr  Polynomial;  // 多项式链表头指针

  • 核心优势：
  • 仅存储非零项，极大节省稀疏多项式的内存空间，无冗余存储。
  • 无需预设最大指数，可动态申请节点，支持任意高次的稀疏多项式。
  • 多项式加减操作仅需遍历两个链表，时间复杂度为O(M+N)（M、N为两个多项式的非零项个数），效率远高于数组表示。

Multilists

假设有40000名学生、2500门课程，需要实现两个核心功能： 1. 打印每门课程的选课学生名单 2. 打印每个学生的选课课程名单

Two-dimensional Array Implementation

定义二维数组int Array[40000][2500]，数组元素为1表示学生选了对应课程，0表示未选。 - 核心缺陷： 1. 内存占用极大：40000×2500=1亿个元素，即使每个元素1字节，也需要100MB内存；而实际选课场景是稀疏的，大部分元素为0，内存浪费极其严重。 2. 遍历效率低：打印单门课程的学生名单需要遍历40000个元素，打印单个学生的选课名单需要遍历2500个元素，效率低下。

Multilists Implementation

  • 为学生和课程分别建立节点，通过交叉链表建立选课关系，仅存储实际的选课数据，避免稀疏存储的浪费。

  • 学生节点S1 ~ S5、课程节点C1 ~ C4，每个学生节点链接其选课的课程节点，每个课程节点链接选该课的学生节点，形成双向交叉链表。

  • 核心优势：

  • 仅存储实际的选课关系，无冗余数据，极大节省内存。
  • 遍历效率高：打印学生的选课名单仅需遍历该学生的链表，打印课程的选课名单仅需遍历该课程的链表，无需遍历全量数据。

自学作业：自主学习稀疏矩阵（Sparse Matrix）的表示方法。

§3 The Stack ADT

Definition

栈（Stack） 是一种后进先出（Last-In-First-Out, LIFO） 的有序线性表，其插入（入栈）和删除（出栈）操作仅能在表的一端（栈顶，Top）执行。

  • 数据对象：包含零个或多个元素的有限有序线性表。

  • 核心操作集：

  • int IsEmpty( Stack S );：判断栈是否为空
  • Stack CreateStack( );：创建一个空栈
  • DisposeStack( Stack S );：销毁栈，释放内存
  • MakeEmpty( Stack S );：将栈置空
  • Push( ElementType X, Stack S );：将元素X压入栈顶（入栈）
  • ElementType Top( Stack S );：获取栈顶元素，不改变栈结构
  • Pop( Stack S );：弹出栈顶元素（出栈）

注意： - 对空栈执行Pop或Top操作，属于栈ADT定义的错误

  • 对满栈执行Push操作，属于实现层面的错误，而非ADT定义的错误

1. Linked List Implementation of Stacks

采用单链表结构存储栈元素，表头节点作为栈的管理节点，栈顶元素始终存放在表头节点的后继节点，入栈和出栈操作均在链表头部执行，无需遍历全表。

Core Operation Implementation

  • Push Operation 核心需求：将新节点TmpCell压入栈顶 操作步骤（顺序不可颠倒）： ① TmpCell->Next = S->Next;：新节点指向原栈顶节点 ② S->Next = TmpCell;：表头节点指向新节点，新节点成为新栈顶 时间复杂度：O(1)

  • Pop Operation 核心需求：弹出栈顶节点 操作步骤： ① FirstCell = S->Next;：获取当前栈顶节点 ② S->Next = S->Next->Next;：表头节点跳过原栈顶节点，指向后继节点 ③ free( FirstCell );：释放原栈顶节点内存，避免内存泄漏 时间复杂度：O(1)

  • Top Operation 实现逻辑：直接返回S->Next->Element，时间复杂度O(1)

Advantages, Disadvantages and Optimization - 缺陷：频繁调用malloc和free进行节点申请与释放，系统开销较大 - 优化方案：维护一个额外的栈作为回收站（recycle bin），将释放的节点存入回收站，新节点申请时优先从回收站获取，避免频繁的系统内存调用

2. Array Implementation of Stacks

用连续的数组空间存储栈元素，通过TopOfStack（栈顶指针）标记栈顶位置，空栈时TopOfStack = -1；入栈时TopOfStack自增，出栈时TopOfStack自减，属于顺序存储结构。

Structure Definition (C) 

// 栈的数组实现结构定义
typedef struct StackRecord {
    int Capacity;              // 栈的最大容量
    int TopOfStack;            // 栈顶指针，-1表示空栈
    ElementType *Array;        // 存储栈元素的数组
} *Stack;

Design Specifications 1. 封装性要求：栈模型必须严格封装，除栈操作函数外，任何代码都不允许直接访问Array数组和TopOfStack变量 2. 错误检查要求：执行Push、Pop、Top操作前，必须先执行栈空/栈满的错误检查

3. Typical Applications of Stacks

Balancing Symbols

Core Requirements

校验表达式中的括号是否成对匹配，包括小括号()、中括号[]、大括号{}，是编译器语法检查的核心基础功能。

Algorithm Flow
算法：符号平衡校验
输入：待校验的字符流
输出：括号是否平衡，不平衡则报错
步骤：
1.  创建一个空栈S
2.  循环读取输入中的每个字符c：
    a.  若c是开符号（(、[、{），将c压入栈S
    b.  若c是闭符号（)、]、}）：
        i.  若栈S为空，直接报错并退出（无匹配的开符号）
        ii. 若栈顶元素与c不是匹配的括号对，直接报错并退出
        iii.若匹配成功，弹出栈顶元素
3.  循环结束后，若栈S不为空，报错（存在未闭合的开符号）
4.  所有校验通过，括号平衡
Algorithm Features
  • 时间复杂度：T(N) = O(N)，N为表达式长度，每个字符仅入栈和出栈各一次
  • 属于在线算法（on-line algorithm）：无需提前读取全部输入，可边读取边处理

Postfix Evaluation

Core Concepts
  • 中缀表达式：运算符位于两个操作数之间，如a + b * c - d / e，需依赖运算符优先级和括号决定运算顺序
  • 前缀表达式（波兰表示法）：运算符位于操作数之前，如- + a * b c / d e
  • 后缀表达式（逆波兰表示法，Reverse Polish notation）：运算符位于操作数之后，如a b c * + d e / -，无需考虑运算符优先级，仅需按顺序处理
Algorithm Flow
算法：后缀表达式求值
输入：后缀表达式的token流（操作数/运算符）
输出：表达式的计算结果
步骤：
1.  创建一个空栈S
2.  循环读取每个token：
    a.  若token是操作数，将其压入栈S
    b.  若token是运算符：
        i.  连续弹出栈顶的两个操作数（先弹出的是右操作数，后弹出的是左操作数）
        ii.执行运算符对应的计算
        iii.将计算结果压回栈S
3.  循环结束后，栈中仅剩一个元素，即为表达式的最终结果
Example and Features
  • 示例：计算后缀表达式6 2 / 3 - 4 2 * +
  • 6入栈、2入栈；遇/，弹出2和6，计算6/2=3，3入栈
  • 3入栈；遇-，弹出3和3，计算3-3=0，0入栈
  • 4入栈、2入栈；遇*，弹出2和4，计算4*2=8，8入栈
  • 遇+，弹出8和0，计算0+8=8，8入栈
  • 最终栈顶元素8即为结果
  • 时间复杂度：T(N) = O(N)，N为token数量，每个token仅处理一次
  • 核心优势：无需处理运算符优先级和括号，计算逻辑极简

Infix to Postfix Conversion

Core Rules
  1. 操作数的输出顺序，在中缀和后缀表达式中完全一致
  2. 优先级高的运算符，在后缀表达式中先输出
  3. 左括号(在栈外优先级最高，入栈后优先级最低；仅当遇到右括号)时，才弹出栈内的左括号
  4. 右结合运算符（如幂运算^）需特殊处理，避免左结合导致的运算错误（如2^2^3需转换为2 2 3 ^ ^，而非2 2 ^ 3 ^）
Algorithm Flow
算法：中缀表达式转后缀表达式
输入：中缀表达式的token流（操作数/运算符/括号）
输出：对应的后缀表达式
步骤：
1.  创建一个空栈S，用于存储运算符
2.  循环读取每个token：
    a.  若token是操作数，直接输出到后缀表达式
    b.  若token是左括号`(`，压入栈S
    c.  若token是右括号`)`：
        i.  循环弹出栈顶元素并输出，直到遇到左括号`(`
        ii.弹出左括号`(`，不输出
    d.  若token是运算符：
        i.  循环弹出栈顶优先级**大于等于**当前运算符的元素并输出（右结合运算符为大于）
        ii.将当前运算符压入栈S
3.  循环结束后，将栈中剩余的所有运算符依次弹出并输出
Example and Features
  • 示例1：中缀表达式a + b * c - d 输出后缀表达式：a b c * + d -
  • 示例2：中缀表达式a * ( b + c ) / d 输出后缀表达式：a b c + * d /
  • 时间复杂度：T(N) = O(N)，N为token数量，每个运算符仅入栈和出栈各一次

Function Calls and System Stack

Core Principle

程序运行时，系统会维护一个由栈帧（Stack Frame）组成的系统栈，每次函数调用时，将函数的返回地址、局部变量、旧帧指针等信息压入栈中；函数执行完毕返回时，弹出对应的栈帧，恢复到调用前的执行状态。

Relationship Between Recursion and Stack

递归函数的执行，本质上是通过系统栈完成多层函数调用的状态管理。 - 示例：递归遍历链表打印元素 

// 递归实现的链表打印（尾递归示例）
void PrintList ( List L )
{
    if ( L != NULL )  {
        PrintElement ( L->Element );
        PrintList( L->next );
    }
}
- 核心问题：若链表包含100万个元素，递归调用会产生100万层栈帧，超出系统栈的容量限制，导致程序崩溃 - 尾递归优化：尾递归（递归调用是函数的最后一条语句）可被编译器优化为循环结构，消除栈帧的累积开销，优化后等价代码： 
// 尾递归优化为循环
void PrintList ( List L )
{
top:
    if ( L != NULL )  {
        PrintElement ( L->Element );
        L = L->next;
        goto top;
    }
}

Comparison Between Recursion and Non-recursion
  1. 任何递归程序都可以通过栈完全消除递归，转换为非递归程序
  2. 等价的非递归程序，运行速度通常快于递归程序（无栈帧创建与销毁的开销）
  3. 递归程序的代码通常更简洁、可读性更强，更易理解和维护

§4 The Queue ADT

Definition

队列（Queue） 是一种先进先出（First-In-First-Out, FIFO） 的有序线性表，其插入（入队）操作仅能在表的一端（队尾，Rear）执行，删除（出队）操作仅能在表的另一端（队头，Front）执行。

  • 数据对象：包含零个或多个元素的有限有序线性表。
  • 核心操作集：
  • int IsEmpty( Queue Q );：判断队列是否为空
  • Queue CreateQueue( );：创建一个空队列
  • DisposeQueue( Queue Q );：销毁队列，释放内存
  • MakeEmpty( Queue Q );：将队列置空
  • Enqueue( ElementType X, Queue Q );：将元素X插入队尾（入队）
  • ElementType Front( Queue Q );：获取队头元素，不改变队列结构
  • Dequeue( Queue Q );：删除队头元素（出队）

1. Array Implementation of Queues

链表实现队列逻辑简单，因此核心讲解数组实现方案。

Core Structure Definition (C)

// 队列的数组实现结构定义
typedef struct QueueRecord {
    int Capacity;              // 队列的最大容量
    int Front;                 // 队头指针
    int Rear;                  // 队尾指针
    int Size;                  // 可选字段，记录队列当前元素个数
    ElementType *Array;        // 存储队列元素的数组
} *Queue;

Core Problem of Basic Implementation

基础数组实现中，入队操作让Rear指针后移，出队操作让Front指针后移，会出现假溢出问题： - 现象：数组仍有空闲空间，但队列被判定为满，无法继续入队 - 原因：多次入队和出队后，Front和Rear指针均移动到数组末尾，即使数组前端有空闲空间，也无法被利用

Circular Queue Solution

Core Logic

将数组的首尾逻辑上相连，形成环形结构，Front和Rear指针到达数组末尾后，可绕回数组开头，复用前端的空闲空间，彻底解决假溢出问题。

Core Design Details
  1. 空/满状态区分：
    • 方案1：牺牲数组的1个空闲空间，约定Rear指针的下一个位置是Front时，判定为队列满；Front == Rear时，判定为队列空
    • 方案2：新增Size字段记录队列当前元素个数，Size == Capacity时为满，Size == 0时为空，无需牺牲空闲空间
  2. 指针循环更新：通过取模运算实现指针的循环后移，如Rear = (Rear + 1) % Capacity

2. Typical Applications of Queues

队列的核心特性是保证元素的处理顺序与入队顺序完全一致，典型应用包括： - 操作系统的作业调度（Job Scheduling）：按作业提交顺序分配CPU资源 - 广度优先搜索（BFS）算法的核心数据结构 - 缓冲区管理、消息队列等场景

Additional Content

Bonus Problem 1: LRU-K

  • Points: 2
  • Deadline: 22:00, Tuesday, June 16th, 2026
  • Submission Address: https://pintia.cn/