【无标题】【2025年软考中级】第三章数据结构3.2 栈与队列

栈与队列

栈和队列是两种操作受限制的线性表数据结构，它们在计算机科学中应用广泛。理解它们的特性和实现原理是掌握数据结构的基础。

栈

**LIFO（后进先出）**原则：最后进入的元素最先被移除

顺序栈

动态演示

顺序栈使用数组实现栈结构：

typedef struct{ 
    Elemtype data[Maxsize]; 
    int top; // 栈顶指针
}SqStack;

核心操作

• 栈空（初始化）：s->top == -1
• 栈满：s->top == Maxsize-1
• 进栈：指针先加1，再放入元素
• 出栈：先取出元素，指针再减1

重要特性：

• 入栈出栈时间复杂度均为 O(1)
• n个元素的合法出栈序列个数为卡特兰数：
  $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$
  例如 n=4 时，有14种合法序列

注意：某些实现可能让栈空时 top==0，此时：

• 入栈：先放入元素，指针再加1
• 出栈：指针先减1，再取出元素

顺序共享栈

为节省空间，两个栈共享同一数组空间

typedef struct{ 
    Elemtype data[Maxsize]; 
    int top1, top2; // top1从0开始，top2从Maxsize-1开始
}SqStack;

核心操作

• 栈空：
  • 栈1空：top1 == -1
  • 栈2空：top2 == Maxsize
• 栈满：top1 == top2 - 1
• 进栈：先动指针，再放入元素
• 出栈：先取出元素，再动指针

链栈

动态演示

使用链表实现的栈结构：

typedef struct linknode{ 
    Elemtype data; 
    struct linknode *next; 
}LinkStNode;

核心操作

• 栈空（初始化）：s->next == NULL
• 栈满：理论上不会栈满
• 进栈：使用头插法添加新节点
• 出栈：取出头节点数据并删除节点

  p = head->next;
  e = p->data;
  head->next = p->next;
  free(p);
  

特点：栈底节点的 next 指针为 NULL

栈的应用

常见应用场景

1. 括号匹配：检查表达式中的括号是否成对出现
2. 表达式求值：将中缀表达式转换为后缀/前缀表达式
3. 函数调用栈：实现递归调用和局部变量存储
4. 进制转换：十进制转二进制/八进制/十六进制
5. 迷宫求解：记录路径和回溯点

表达式求值详解

• 前缀表达式（波兰式）：运算符在操作数之前 + 1 * 2 3
• 中缀表达式：运算符在操作数之间 1 + 2 * 3
• 后缀表达式（逆波兰式）：运算符在操作数之后 1 2 3 * +

转换规则：

• 操作数相对位置不变
• 运算符位置根据就近原则调整
• 后缀表达式从左到右入栈计算
• 前缀表达式从右到左入栈计算

示例：中缀 1+2*3 转换：

• 前缀：+ 1 * 2 3
• 后缀：1 2 3 * +

队列

**FIFO（先进先出）**原则：最先进入的元素最先被移除
尾进头出：入队操作在尾部，出队操作在头部

顺序队列

动态演示

typedef struct{ 
    elemtype data[Maxsize]; 
    int rear, front; // 尾指针和头指针
}SqQueue;

核心操作

• 初始化：q->rear = q->front = -1
• 队空：q->front == q->rear
• 队满：q->rear == Maxsize-1
• 入队：++rear 后放入元素
• 出队：取出元素后 ++front

注意：

• front 总是指向队首元素的前一个位置
• 含n个空间的队列最多执行n-1次入队操作
• 入队出队时间复杂度均为 O(1)

循环队列

解决顺序队列的"假溢出"问题

typedef struct{ 
    elemtype data[Maxsize]; 
    int rear, front;
}SqQueue;

核心操作

• 初始化：q->front = q->rear = 0
• 队空：q->rear == q->front
• 队满：(q->rear + 1) % Maxsize == q->front（浪费一个空间区分空/满）
• 入队：q->rear = (q->rear + 1) % Maxsize
• 出队：front = (front + 1) % Maxsize

关键计算

• 元素个数：count = (rear - front + Maxsize) % Maxsize
• 队头位置：front = (rear - count + Maxsize) % Maxsize
• 队尾位置：rear = (front + count) % Maxsize（仅当有减号时需加Maxsize）

链式队列

typedef struct qnode{ 
    elemtype data; 
    struct qnode *next; 
}Datanode;

typedef struct{ 
    Datanode *front; 
    Datanode *rear; 
}Linkqunode;

核心操作

• 初始化：q->front = q->rear = NULL
• 队空：q->front == NULL 或 q->rear == NULL
• 入队：在尾部插入新节点（空队列需特殊处理）
• 出队：删除头节点（只有一个节点需特殊处理）
• 判断单节点：q->front == q->rear != NULL

队列的应用

常见应用场景

1. 缓冲区管理：操作系统中的I/O缓冲区
2. CPU调度：进程就绪队列
3. 打印队列：管理打印任务
4. 广度优先搜索：图的层次遍历
5. 页面替换算法：操作系统内存管理
6. 迷宫求解：记录待探索的路径

栈与队列的区别