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

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

目录

• 3.1 栈
  • 栈的基本概念
  • 栈的存储结构
  • 栈与递归
  • 栈的应用
• 3.2 队列
  • 队列的基本概念
  • 队列的存储结构
  • 双端队列
  • 队列的应用

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. 保留本层参数与返回地址（保存断点，进栈）
2. 为被调函数的局部变量分配存储空间，给下层参数赋值
3. 转移到被调函数入口

递归退层：

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

栈的应用

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

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

重要算法实现

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. 中缀表达式转后缀表达式

基本思想：

1. 初始化栈，'#'入栈
2. 顺序扫描表达式str
3. 如果是操作数，直接存入backExp
4. 如果是操作符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. 括号匹配问题

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

算法步骤：

1. 初始化栈S，计数器count=0
2. 依次扫描每个字符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;
}

重要公式与性质

卡特兰数

n个元素依次进栈，进栈和出栈可以交替进行时，出栈元素的排列个数为第n个卡特兰数：
$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

循环队列元素个数计算

循环队列中元素的个数：(rear - front + m) % m

其中m为队列容量，front为队首元素位置，rear为队尾元素的下一个位置。

408考研要点总结

1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
3. 栈和队列的链式存储结构
4. 栈与递归的关系
5. 栈在表达式求值中的应用
6. 双端队列的性质和判断
7. 优先级队列的实现
8. 各种存储结构的算法实现