当前位置：首页 > news >正文

数据结构进阶 - 第三章栈与队列

news 2025/6/27 9:04:42

数据结构进阶 - 第3章栈与队列

3.1 栈

栈的基本概念

栈特性：

FILO（先进后出） 或 LIFO（后进先出）
n个元素依次进栈，如果进栈和出栈可以交替进行，则出栈元素的排列个数为 Catalan数

栈的基本操作：

InitStack() - 初始化栈
Push() - 入栈
Pop() - 出栈
GetTop() - 获取栈顶元素
IsEmpty() - 判断栈是否为空
IsFull() - 判断栈是否已满

栈的存储结构

1. 顺序栈

typedef struct {int data[MAXSIZE];int top;
} SqStack;

栈满条件： top == MAXSIZE - 1

2. 两栈共享

typedef struct {int data[MAXSIZE];int top[2];  // 两个栈的栈顶指针
} DStack;

初始化：

top[0] = -1
top[1] = MAXSIZE

栈满条件： top[0] + 1 == top[1]

栈空条件：

1号栈空：top[0] == -1
2号栈空：top[1] == MAXSIZE

3. 链栈

typedef struct StackNode {int data;struct StackNode *next;
} StackNode, *LinkStack;

栈与递归

递归的特点

优点：

算法简单、结构清晰
正确性容易证明

适用条件：

原问题可以层层分解为类似子问题
最小子问题有解
子问题的解可以容易合并为原问题的解

缺点：

时空效率低
无法得到递归过程的某中间状态

递归过程

递归进层：

保留本层参数与返回地址（保存断点，进栈）
为被调函数的局部变量分配存储空间，给下层参数赋值
转移到被调函数入口

递归退层：

保存被调函数计算结果
释放被调函数的数据区，恢复上层参数（出栈）
转入到保存的返回地址继续执行

栈的应用

栈适用于符合数据先产生后处理的情况：

进制转换
回文判断
括号匹配
表达式求值
中缀转后缀表达式
后缀表达式计算

重要算法实现

1. 判断操作序列是否合法

问题： 判断由I（入栈）和O（出栈）组成的操作序列是否合法

算法思想：

方法1：设置计数器numI和numO，依次读入字符
方法2：设置变量sum=0，遇到I则sum++，遇到O则sum–

int Judge(char A[]) {int i = 0, numI = 0, numO = 0;while(A[i] != '\0') {if(A[i] == 'I') numI++;else numO++;if(numO > numI) return 0;i++;}if(numO == numI) return 1;else return 0;
}

2. 判断出栈序列是否合法

问题： 判断给定序列是否为合理的出栈顺序

int IsLegal(int a[], int n) {Stack s; initStack(&s);for(int i = 1, k = 1; i <= n; i++) {while(a[i] > k) push(&s, k++);if(a[i] == k) { k++; continue; }if(a[i] < getTop(&s)) break;}if(isEmpty(&s)) return true;else return false;
}

3. 中缀表达式转后缀表达式

基本思想：

初始化栈，'#'入栈
顺序扫描表达式str
如果是操作数，直接存入backExp
如果是操作符op2，与栈顶操作符op1比较：
- 若op2 > op1，则op2入栈
- 若op2 <= op1，则op1出栈并存入backExp

char* change(char *str) {int i = 0, j = 0; Stack S;char *backExp = (char *)malloc(sizeof(char) * strlen(str));InitStack(&S); Push(&S, '#');while(GetTop(&S) != '#' || str[i] != '#') {if(str[i]是运算数) { backExp[j] = str[i]; i++; j++;}else {op1 = GetTop(&S); op2 = str[i];result = compare(op2, op1);if(result == '>') {Push(&S, op2); i++;}else {Pop(&S, &op1); backExp[j] = op1; j++;}}}backExp[j] = '\0';return backExp;
}

4. 括号匹配问题

问题： 给定字符串，计算需要添加多少个括号才能使其匹配

算法步骤：

初始化栈S，计数器count=0
依次扫描每个字符ch[i]：
- 如果是左括号，进栈
- 如果是右括号：
  - 栈为空：需添加左括号，count++
  - 栈顶与ch[i]匹配：出栈
  - 栈顶与ch[i]不匹配：需添加右括号，count++，出栈

3.2 队列

队列的基本概念

队列特性：FIFO（先进先出）

基本操作：

InitQueue() - 初始化队列
EnQueue() - 入队
DeQueue() - 出队
GetHead() - 获取队头元素
IsEmpty() - 判断队列是否为空

队列的存储结构

1. 顺序存储 - 循环队列

假溢出问题： 队列的顺序存储中，随着进队和出队的进行，出现队尾溢出，但队头仍有空位置的情况

解决方案：循环队列

区分空和满的三种方法：

方法1：少用一个存储单元

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

空：Q.front == Q.rear
满：Q.front == (Q.rear + 1) % MAXSIZE

方法2：增设辅助标志

typedef struct {int data[MAXSIZE];int front, rear, flag;
} SqQueue;

空：Q.front == Q.rear && Q.flag == 0
满：Q.front == Q.rear && Q.flag == 1

方法3：增设计数器

typedef struct {int data[MAXSIZE];int front, rear, count;
} SqQueue;

空：Q.count == 0
满：Q.count == MAXSIZE

2. 链式存储 - 链队列

typedef struct QueueNode {int data;struct QueueNode *next;
} QueueNode;typedef struct {QueueNode *front, *rear;
} LinkQueue;

双端队列

双端队列是一种两端都可以进行插入和删除操作的线性表。

输入受限的双端队列

一端只能插入，另一端既能插入又能删除

输出受限的双端队列

一端只能删除，另一端既能插入又能删除

重要性质：

对于输出受限的双端队列：

出队序列可拆分为：出栈子序列（前端）+ 出队子序列（后端）
出栈子序列先于出队子序列

对于输入受限的双端队列：

需要：出队严格递增子序列 + 出栈严格递减子序列
且出队子序列的最大下标 < 出栈子序列的最小下标

队列的应用

1. 基本应用

缓冲： 快慢设备速度匹配
排队： 多用户的资源竞争，先来先服务

2. 优先级队列

最大优先级队列 - 用堆来实现

int EnterQ(Queue *Q, ElemType x);  // 入队操作
int DeleteQ(Queue *Q, ElemType *x); // 出队操作

重要算法实现

1. 带标志的循环队列

typedef struct {elemType element[MAXSIZE];int front, rear, tag;
} SeqQueue;void InitQueue(SeqQueue *Q) {Q->front = Q->rear = Q->tag = 0;
}int EnterQueue(SeqQueue *Q, elemType x) {if(Q->rear == Q->front && Q->tag == 1) return FALSE;Q->element[Q->rear] = x; Q->rear = (Q->rear + 1) % MAXSIZE;if(Q->front == Q->rear) Q->tag = 1;return TRUE;
}int DeleteQueue(SeqQueue *Q, elemType *x) {if(Q->rear == Q->front && Q->tag == 0) return FALSE;*x = Q->element[Q->front]; Q->front = (Q->front + 1) % MAXSIZE;if(Q->front == Q->rear) Q->tag = 0;return TRUE;
}

2. 循环单链表实现的队列

typedef struct LinkQueueNode {elemType data;struct LinkQueueNode *next;
} LinkQueueNode, *LinkQueue;int InitLinkQueue(LinkQueue *Q) {*Q = (LinkQueue)malloc(sizeof(LinkQueueNode));if((*Q) == NULL) return 0;(*Q)->next = (*Q);return 1;
}int EnterQueue(LinkQueue *Q, elemType x) {LinkQueueNode *temp = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));if(temp == NULL) return 0;temp->data = x;temp->next = (*Q)->next;(*Q)->next = temp; (*Q) = temp;return 1;
}int DeleteQueue(LinkQueue *Q, elemType *x) {if((*Q)->next == (*Q)) return 0;LinkQueueNode *temp = (*Q)->next->next;if((*Q) == temp) (*Q) = temp->next;(*Q)->next->next = temp->next; *x = temp->data;free(temp); return 1;
}