bittern.cn
3数据结构与算法分析：C语言描述（第2版）

表、栈和队列

线性数据结构

链表栈队列双端队列

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第3章：表、栈和队列（Lists, Stacks, and Queues）

一、导读

1.1 本章学习目标

第3章介绍三种最基本的线性数据结构：表（List）、栈（Stack）和队列（Queue）。它们是构建更复杂数据结构的基石，也是实际编程中使用最频繁的数据结构。本章将深入讲解它们的抽象定义、不同实现方式（数组和链表），以及各种操作的复杂度分析。

本章的核心学习目标包括：

  • 理解表的抽象概念：表是一种支持在任意位置进行插入和删除的线性结构，它的数组实现和链表实现各有什么优缺点？
  • 掌握链表的各种变体：单链表、双链表、循环链表的结构特点和适用场景分别是什么？
  • 深入理解栈的LIFO特性：栈的"后进先出"原则如何应用于函数调用、表达式求值和括号匹配？
  • 深入理解队列的FIFO特性：队列的"先进先出"原则如何应用于广度优先搜索和任务调度？
  • 学会用数组和链表分别实现栈和队列：两种实现方式在性能上有什么差异？
  • 了解游标实现：如何用数组模拟链表，避免指针操作的开销？

1.2 为什么第三章如此重要

表、栈和队列是数据结构世界的"三块基石"。几乎所有后续的数据结构——树、图、散列表、优先队列——都可以看作是这三种基本结构的扩展或组合。

更重要的是，这三种数据结构在实际编程中的应用无处不在：

  • 栈：浏览器的后退按钮、编辑器的撤销功能、编译器的语法分析、函数调用管理
  • 队列：操作系统的进程调度、打印队列、BFS搜索、消息队列
  • 链表：操作系统的内存管理、LRU缓存、音乐播放列表

掌握它们的实现细节和性能特点，是成为合格程序员的基本功。

1.3 核心问题引导

在阅读本章时，请带着以下问题思考：

数组和链表在插入、删除、访问操作上的时间复杂度各是多少？为什么？

为什么单链表不适合按位置随机访问？如何改进？

如何用两个栈实现一个队列？如何用两个队列实现一个栈？

栈在函数调用中扮演什么角色？递归调用时栈发生了什么？

如何用栈将中缀表达式转换为后缀表达式？如何计算后缀表达式的值？

循环队列如何解决"假溢出"问题？

二、核心概念详解

3.1 表（List）

表是最基本的线性数据结构，它包含零个或多个元素 a₁, a₂, ..., aₙ。表的长度是元素的个数，空表长度为0。除第一个元素外，每个元素有唯一的前驱；除最后一个元素外，每个元素有唯一的后继。

3.1.1 表的数组实现

数组实现使用一块连续的内存空间存储表的元素。

c
#define MAX_SIZE 1000

typedef struct ArrayList {
    int data[MAX_SIZE];
    int size;
} ArrayList;

void init(ArrayList *L) {
    L->size = 0;
}

int get(ArrayList *L, int pos) {
    if (pos < 0 || pos >= L->size) return -1;
    return L->data[pos];
}

// 在位置pos插入元素 - O(n)
void insert(ArrayList *L, int pos, int val) {
    if (L->size >= MAX_SIZE) return;
    if (pos < 0 || pos > L->size) return;
    for (int i = L->size; i > pos; i--)
        L->data[i] = L->data[i - 1];
    L->data[pos] = val;
    L->size++;
}

// 删除位置pos的元素 - O(n)
void delete(ArrayList *L, int pos) {
    if (pos < 0 || pos >= L->size) return;
    for (int i = pos; i < L->size - 1; i++)
        L->data[i] = L->data[i + 1];
    L->size--;
}

// 按位置访问 - O(1)
// 这是数组实现的最大优势
int access(ArrayList *L, int pos) {
    return L->data[pos];
}

数组实现的优缺点：

  • 优点：随机访问 O(1)，内存连续利用率高
  • 缺点：插入和删除需要移动大量元素 O(n)，容量固定（除非动态扩容）

3.1.2 表的链表实现

链表使用节点（Node）存储元素，每个节点包含数据和指向下一个节点的指针。

c
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct LinkedList {
    Node *head;
    int size;
} LinkedList;

void init(LinkedList *L) {
    L->head = NULL;
    L->size = 0;
}

// 在头部插入 - O(1)
void insertFront(LinkedList *L, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = L->head;
    L->head = newNode;
    L->size++;
}

// 在位置pos插入 - O(n)（需要遍历到pos-1）
void insert(LinkedList *L, int pos, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    
    if (pos == 0) {
        newNode->next = L->head;
        L->head = newNode;
    } else {
        Node *curr = L->head;
        for (int i = 0; i < pos - 1; i++)
            curr = curr->next;
        newNode->next = curr->next;
        curr->next = newNode;
    }
    L->size++;
}

// 删除值为val的第一个节点 - O(n)
void delete(LinkedList *L, int val) {
    if (L->head == NULL) return;
    if (L->head->data == val) {
        Node *tmp = L->head;
        L->head = L->head->next;
        free(tmp);
        L->size--;
        return;
    }
    Node *curr = L->head;
    while (curr->next != NULL && curr->next->data != val)
        curr = curr->next;
    if (curr->next != NULL) {
        Node *tmp = curr->next;
        curr->next = tmp->next;
        free(tmp);
        L->size--;
    }
}

// 按位置访问 - O(n)
int get(LinkedList *L, int pos) {
    Node *curr = L->head;
    for (int i = 0; i < pos; i++) {
        if (curr == NULL) return -1;
        curr = curr->next;
    }
    return curr ? curr->data : -1;
}

// 释放整个链表
void destroy(LinkedList *L) {
    Node *curr = L->head;
    while (curr != NULL) {
        Node *tmp = curr;
        curr = curr->next;
        free(tmp);
    }
    L->head = NULL;
    L->size = 0;
}

链表实现的优缺点：

  • 优点：插入和删除（已知位置时）只需修改指针 O(1)，动态大小
  • 缺点：随机访问 O(n)，每个节点额外存储指针，缓存不友好

3.1.3 双链表和循环链表

c
// 双链表节点
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// 双链表支持向前和向后遍历
// 删除操作更方便：已知节点指针时，删除为O(1)
void deleteNode(DNode **head, DNode *node) {
    if (*head == node) *head = node->next;
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    free(node);
}

// 循环链表：最后一个节点的next指向头节点
// 适用于需要循环遍历的场景（如轮转调度）
typedef struct CircList {
    Node *head;
} CircList;

void initCirc(CircList *L) {
    L->head = NULL;
}

void insertCirc(CircList *L, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    if (L->head == NULL) {
        newNode->next = newNode;
        L->head = newNode;
    } else {
        Node *tail = L->head;
        while (tail->next != L->head)
            tail = tail->next;
        tail->next = newNode;
        newNode->next = L->head;
    }
}

3.2 栈（Stack）

栈是只允许在一端（称为"栈顶"）进行插入和删除操作的线性表。栈的核心特征是后进先出（LIFO, Last In First Out）。

栈的两个核心操作：

  • push：在栈顶插入元素
  • pop：从栈顶删除并返回元素
c
// 栈的链表实现
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct Stack {
    StackNode *top;
    int size;
} Stack;

void initStack(Stack *S) {
    S->top = NULL;
    S->size = 0;
}

int isEmpty(Stack *S) {
    return S->top == NULL;
}

// push - O(1)
void push(Stack *S, int val) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    newNode->data = val;
    newNode->next = S->top;
    S->top = newNode;
    S->size++;
}

// pop - O(1)
int pop(Stack *S) {
    if (isEmpty(S)) {
        fprintf(stderr, "Stack underflow\n");
        exit(1);
    }
    int val = S->top->data;
    StackNode *tmp = S->top;
    S->top = S->top->next;
    free(tmp);
    S->size--;
    return val;
}

// peek - O(1)
int peek(Stack *S) {
    if (isEmpty(S)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    return S->top->data;
}

3.2.1 栈的应用：括号匹配

c
// 检查括号是否匹配
int isBalanced(const char *expr) {
    Stack S;
    initStack(&S);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&S, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&S)) return 0;
            char top = pop(&S);
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return 0;
        }
    }
    return isEmpty(&S);
}
// isBalanced("({[]})") → 1（匹配）
// isBalanced("({[})")  → 0（不匹配）

3.2.2 栈的应用：后缀表达式求值

c
// 计算后缀表达式（逆波兰表达式）
int evalPostfix(const char *expr) {
    Stack S;
    initStack(&S);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c >= '0' && c <= '9') {
            push(&S, c - '0');
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            int b = pop(&S);
            int a = pop(&S);
            switch (c) {
                case '+': push(&S, a + b); break;
                case '-': push(&S, a - b); break;
                case '*': push(&S, a * b); break;
                case '/': push(&S, a / b); break;
            }
        }
    }
    return pop(&S);
}
// evalPostfix("23+4*") → (2+3)*4 = 20

3.3 队列（Queue）

队列是只允许在一端（队尾）插入、另一端（队头）删除的线性表。队列的核心特征是先进先出（FIFO, First In First Out）。

队列的两个核心操作：

  • enqueue：在队尾插入元素
  • dequeue：从队头删除并返回元素
c
// 队列的链表实现
typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
    int size;
} Queue;

void initQueue(Queue *Q) {
    Q->front = Q->rear = NULL;
    Q->size = 0;
}

int isQueueEmpty(Queue *Q) {
    return Q->front == NULL;
}

// enqueue - O(1)
void enqueue(Queue *Q, int val) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->data = val;
    newNode->next = NULL;
    if (Q->rear == NULL) {
        Q->front = Q->rear = newNode;
    } else {
        Q->rear->next = newNode;
        Q->rear = newNode;
    }
    Q->size++;
}

// dequeue - O(1)
int dequeue(Queue *Q) {
    if (isQueueEmpty(Q)) {
        fprintf(stderr, "Queue underflow\n");
        exit(1);
    }
    int val = Q->front->data;
    QueueNode *tmp = Q->front;
    Q->front = Q->front->next;
    if (Q->front == NULL) Q->rear = NULL;
    free(tmp);
    Q->size--;
    return val;
}

3.3.1 循环队列的数组实现

循环队列使用固定大小的数组，通过取模运算实现"循环"效果，解决了普通数组队列的"假溢出"问题。

c
#define QUEUE_CAPACITY 100

typedef struct CircQueue {
    int data[QUEUE_CAPACITY];
    int front;
    int rear;
    int size;
} CircQueue;

void initCQ(CircQueue *Q) {
    Q->front = 0;
    Q->rear = -1;
    Q->size = 0;
}

int isCQEmpty(CircQueue *Q) {
    return Q->size == 0;
}

int isCQFull(CircQueue *Q) {
    return Q->size == QUEUE_CAPACITY;
}

void enqueueCQ(CircQueue *Q, int val) {
    if (isCQFull(Q)) return;
    Q->rear = (Q->rear + 1) % QUEUE_CAPACITY;
    Q->data[Q->rear] = val;
    Q->size++;
}

int dequeueCQ(CircQueue *Q) {
    if (isCQEmpty(Q)) return -1;
    int val = Q->data[Q->front];
    Q->front = (Q->front + 1) % QUEUE_CAPACITY;
    Q->size--;
    return val;
}

3.4 用栈实现队列

c
// 用两个栈实现队列
typedef struct StackQueue {
    Stack inStack;
    Stack outStack;
} StackQueue;

void initSQ(StackQueue *Q) {
    initStack(&Q->inStack);
    initStack(&Q->outStack);
}

// enqueue: 直接压入inStack - 摊还O(1)
void enqueueSQ(StackQueue *Q, int val) {
    push(&Q->inStack, val);
}

// dequeue: 从outStack弹出 - 摊还O(1)
int dequeueSQ(StackQueue *Q) {
    if (isEmpty(&Q->outStack)) {
        while (!isEmpty(&Q->inStack))
            push(&Q->outStack, pop(&Q->inStack));
    }
    if (isEmpty(&Q->outStack)) {
        fprintf(stderr, "Queue is empty\n");
        exit(1);
    }
    return pop(&Q->outStack);
}
// 摊还分析：每个元素最多被push两次、pop两次
// 因此每次操作的摊还代价是O(1)

三、实战案例

3.1 用链表实现多项式加法

c
typedef struct PolyNode {
    int coeff;      // 系数
    int exp;        // 指数
    struct PolyNode *next;
} PolyNode;

// 创建多项式节点
PolyNode *createPolyNode(int coeff, int exp) {
    PolyNode *node = (PolyNode *)malloc(sizeof(PolyNode));
    node->coeff = coeff;
    node->exp = exp;
    node->next = NULL;
    return node;
}

// 多项式加法
PolyNode *addPoly(PolyNode *p1, PolyNode *p2) {
    PolyNode dummy;
    PolyNode *curr = &dummy;
    dummy.next = NULL;
    
    while (p1 != NULL && p2 != NULL) {
        PolyNode *newNode;
        if (p1->exp > p2->exp) {
            newNode = createPolyNode(p1->coeff, p1->exp);
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            newNode = createPolyNode(p2->coeff, p2->exp);
            p2 = p2->next;
        } else {
            int sum = p1->coeff + p2->coeff;
            if (sum != 0) {
                newNode = createPolyNode(sum, p1->exp);
            } else {
                p1 = p1->next;
                p2 = p2->next;
                continue;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        curr->next = newNode;
        curr = newNode;
    }
    
    while (p1 != NULL) {
        curr->next = createPolyNode(p1->coeff, p1->exp);
        curr = curr->next;
        p1 = p1->next;
    }
    while (p2 != NULL) {
        curr->next = createPolyNode(p2->coeff, p2->exp);
        curr = curr->next;
        p2 = p2->next;
    }
    
    return dummy.next;
}
// 例如：(3x² + 2x + 1) + (x² + 5) = 4x² + 2x + 6
// 时间复杂度：O(m + n)，m和n分别是两个多项式的项数

3.2 中缀表达式转后缀表达式

c
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
    return 0;
}

void infixToPostfix(const char *infix, char *postfix) {
    Stack S;
    initStack(&S);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        if (c >= 'a' && c <= 'z') {
            postfix[j++] = c;
        } else if (c == '(') {
            push(&S, c);
        } else if (c == ')') {
            while (!isEmpty(&S) && peek(&S) != '(')
                postfix[j++] = (char)pop(&S);
            if (!isEmpty(&S)) pop(&S);
        } else {
            while (!isEmpty(&S) && precedence((char)peek(&S)) >= precedence(c))
                postfix[j++] = (char)pop(&S);
            push(&S, c);
        }
    }
    while (!isEmpty(&S))
        postfix[j++] = (char)pop(&S);
    postfix[j] = '\0';
}
// infixToPostfix("a+b*c") → "abc*+"
// infixToPostfix("(a+b)*c") → "ab+c*"

四、本章小结

本章系统介绍了三种基本的线性数据结构：

表是最基本的线性结构。数组实现支持 O(1) 随机访问但插入删除 O(n)；链表实现插入删除 O(1)（已知位置时）但随机访问 O(n)。选择哪种实现取决于应用场景的操作频率。

栈是LIFO结构，只允许在栈顶进行插入和删除。所有操作都是 O(1)。栈在函数调用管理、表达式求值、括号匹配、回溯算法中有广泛应用。

队列是FIFO结构，在队尾插入、队头删除。使用链表或循环数组实现时，所有操作都是 O(1)。队列在BFS、任务调度、缓冲区管理中有广泛应用。

游标实现用数组模拟链表，适用于不支持指针的语言或需要减少指针开销的场景。

栈和队列可以互相模拟：两个栈可以实现队列（摊还 O(1)），两个队列可以实现栈。

五、思考与练习

思考题

如果你需要频繁在表的中间位置插入元素，但很少随机访问，应该选择数组还是链表？为什么？

用两个队列实现一个栈，写出 push 和 pop 的代码，并分析时间复杂度。

为什么双链表在已知节点指针时可以实现 O(1) 删除，而单链表不行？

编程练习

实现一个支持 getMin() 操作的栈，getMin() 返回栈中最小元素，所有操作均为 O(1)。

用链表实现一个多项式乘法程序。

编写程序检查一个字符串中的括号是否匹配（包括 ()、[]、{}）。

3/10表、栈和
0%