本章重点

栈和队列 - 图1

栈和队列的定义和特点

栈和队列是两种常用的、重要的数据结构。
栈和队列是限定插入和删除只能在表的”端点”进行的线性表。
线性表中插入和删除算法中的i：Insert(L, i, e) 中 1 <= i < n+1；Delete(L, i) 中 1 <= i < n
栈：
栈中插入和删除算法中的i：Insert(L, i, e) 中 i = n+1；Delete(L, i) 中 i = n
也就是元素只能插入到最后，而最后插入的元素也只能被最先删除，简称为后进先出。
由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具。另外，如果问题求解过程具有后进先出的天然特性的话，则求解的算法中也必然需要利用到”栈”。
队列：
队列中插入和删除算法中的i：Insert(L, i, e) 中 i = n+1；Delete(L, i) 中 i = 1
也就是元素只能插入在最后，而最先进入的元素最先被删除，简称为先进先出。
由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。
结论：栈和队列是线性表的子集(是插入和删除受限的线性表)

栈的定义和特点

栈(stack)是一种特殊的线性表，是限定仅在一端(通常是表尾/栈顶)进行插入和删除操作的线性表。又称为后进先出的线性表，简称LIFO结构。
栈的相关概念
表尾(即an端)称为栈顶Top；表头(即a1端)称为栈底Base
插入元素到栈顶的操作，称为入栈(PUSH)。
从栈顶删除最后一个元素的操作，称为出栈(POP)。

栈与一般线性表的区别：仅在于运算规则不同

线性表&栈	一般线性表	栈
逻辑结构	一对一	一对一
存储结构	顺序表、链表	顺序栈、链栈
运算规则	随机存取	后进先出(LOFO)

队列的定义和特点

队列(queue)是一种先进先出的线性表，简称FIFO结构。
队列的相关概念
在表一端插入(表尾/队尾)，在另一端删除(表头/队头)。

队列与一般线性表的区别：仅在于运算规则不同

线性表&队列	一般线性表	队列
逻辑结构	一对一	一对一
存储结构	顺序表、链表	顺序队、链队
运算规则	随机存取	先进先出(FIFO)

案例引入

【例1】进制转换
十进制整数N向其他进制数d(2、8、16)的转换是计算机实现计算的基本问题。
转换法则：除以d倒取余
该转换法则对应于一个简单的算法原理：n = (n div d) * d + n mod d，其中：div为整除运算，mod为取余运算。

【例2】括号匹配的检验
假设表达式中允许两种括号：圆括号和方括号。
其嵌套的顺序随意，即：

( [] () ) 或 [ ( [] [] ) ] 为正确格式；
[ (] ) 为错误格式；
( [ () ) 或 ( () ] ) 为错误格式；

括号.png

【例3】表达式求值
表达式求值是程序设计语言编译中的一个最基本问题，它的实现也需要运用栈。
这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法——算符优先算法。
表达式的组成：

操作数：常量、变量
运算符：算术、关系、逻辑运算符
界限符：左右括号和表达式结束符

例如：# 3 * ( 7 - 2 ) #

为了实现表达式求值，需要两个栈：

一个算符栈OPTR，用于寄存运算符。
一个操作数栈OPND，用于寄存运算数和运算结果。

求值的处理过程是自左至右扫描表达式的每一个字符

当扫描到运算数，将其压入栈OPND。
当扫描到运算符
- 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
- 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
继续处理当前字符，直到遇到结束符”#”。

栈的表示和操作的实现

栈的抽象数据类型的类型定义

InitStack(&S)

操作结果：构造一个空栈S。

DestoryStack(&S)

初始条件：栈S已存在。
操作结果：栈S被销毁。

StackEmpty(S)

初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。

StackLength(S)

初始条件：栈S已存在。
操作结果：返回栈S的元素个数，即栈的长度。

GetTop(S, &e)

初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。

ClearStack(&S)

初始条件：栈S已存在。
操作结果：将栈S清空。

Push(&s, e)

初始条件：栈S已存在。
操作结果：插入元素e作为新的栈顶元素。

Pop(&s, &e)

初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。

栈的表示和实现

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式

栈的顺序存储—顺序栈
栈的链式存储—链栈

存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。

top指针：指示栈顶元素在顺序栈中的位置。
base指针：只是栈顶元素在顺序栈中的位置。

但是为了方便操作，通常top指示真正的栈顶元素之上的下标地址。
另外，用stacksize表示栈可使用的最大容量。

base == top是栈空标志。
top-base==stacksize是栈满标志，表示不能再入栈了。

栈满的处理方法：

报错，返回操作系统
分配更大的空间

顺序栈的表示

#define MAXSIZE 100
typedef int SElemType;
typedef struct {
    SElemType* base;    // 栈底指针
    SElemType* top;        // 栈顶指针
    int stacksize;        // 栈可用最大容量
};

顺序栈基本操作实现

【InitStack】顺序栈的初始化

Status InitStack(SqStack* S) {
    S->base = (SElemType*)malloc(sizeof(SElemType) * MAXSIZE);
    if (!S->base) {
        exit(OVERFLOW);
    }
    S->top = S->base;
    S->stacksize = MAXSIZE;
    return OK;
}

【StackEmpty】判断顺序栈是否为空

Status StackEmpty(SqStack* S) {
    return S->top == S->base ? TRUE : FALSE;
}

【StackLength】求顺序栈的长度

Status StackLength(SqStack* S) {
    return S->top - S->base;
}

【ClearStack】清空顺序栈

Status ClearStack(SqStack* S) {
    if (S->base) S->top = S->base;
    return OK;
}

【DestoryStack】销毁顺序栈

Status DestoryStack(SqStack* S) {
    if (S->base) {
        free(S->base);
        S->stacksize = 0;
        S->base = S->top = NULL;
    }
    return OK;
}

【Push】顺序栈的入栈

// 1. 判断是否栈满
// 2. 元素e压入栈顶
// 3. 栈顶指针+1
Status Push(SqStack* S, SElemType e) {
    if (StackLength(S) == S->stacksize) return ERROR;
    *(S->top++) = e;
    return OK;
}

【Pop】顺序栈的出栈

// 1. 判断是否栈空
// 2. 获取栈顶元素e
// 3. 栈顶指针-1
Status Pop(SqStack* S, SElemType* e) {
    if (S->top == S->base) return ERROR;
    *e = *(--S->top);
    return OK;
}

链栈的表示

链栈是运算受限的单链表，只能在链表头部进行操作

链表的头指针就是栈顶
不需要头节点
基本不存在栈满的情况
空栈相当于头指针指向空

插入和删除仅在栈顶处执行

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

链栈的基本操作实现

【InitStack】链栈的初始化

Status InitStack(LinkStack* S) {
  *S = NULL;
  return OK;
}

【StackEmpty】判断链栈是否为空

Status StackEmpty(LinkStack* S) {
  return !(*S) ? TRUE : FALSE;
}

【Push】链栈的入栈

Status Push(LinkStack* S, SElemType e) {
  LinkStack p = (LinkStack)malloc(sizeof(StackNode));
  p->data = e;
  p->next = *S;
  *S = p;
  return OK;
}

【Pop】链栈的出栈

Status Pop(LinkStack* S, SElemType* e) {
  if (!(*S)) return ERROR;
  *e = (*S)->data;
  LinkStack p = *S;
  *S = (*S)->next;
  free(p);
  return OK;
}

【GetTop】取栈顶元素

SElemType GetTop(LinkStack* S) {
  if (*S) return (*S)->data;
}

栈与递归

递归的定义

若一个对象部分的包含它自己，或用它自己给自己定义，则称这个对象时递归的。
若一个过程直接或间接的调用自己，则称这个过程是递归的过程

以下三种情况常常用到递归函数

递归定义的数学函数
具有递归特性的数据结构
可递归求解的问题

递归问题——用分治法求解

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的，且解法相同或类似的子问题来求解。
必备的三个条件：

能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的是处理的对象，且这些处理对象是变化有规律的。
可以通过上述转化而使问题简化
必须有一个明确的递归出口，或递归边界。

分治法递归的一般形式

void p(参数) {
    if (递归结束条件)
        可直接求解步骤;
    else 
        p(改变参数);
}

例如：求n的阶乘

long Fact(long n) {
    if (n == 0) retrun 1;
    return n * Fact(n-1);
}

递归过程

递归的优缺点

优点：结构清晰，程序易读
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大。

递归->非递归
方法1：尾递归、单选递归 -> 循环结构
方法2：自用栈模拟系统的运行时栈

队列的表示和操作的实现

队列的抽象数据类型定义

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。相应的队列的存储方式也分为两种，即顺序队列和链式队列。

队列的顺序表示

#define MAXSIZE 100     // 最大队列长度
typedef struct {
    QElemType* base;    // 初始化的动态分配存储空间
    int front;            // 头指针
    int rear;            // 尾指针
} SqQueue;

以上图中存在一个问题，就是当Q.rear == MAXSIZE时，会发生溢出，但实际上队列中时还有空间的，我们把这种情况称为假溢出。

解决假上溢的方法

将队中元素依次向队头方向移动，缺点：浪费时间，每移动一次，队中元素都要移动。
将队空间想象成一个循环的表，即分配给队列的m个存储单元可以循环使用

当rear为MAXSIZE时，若向量的开始端空着，又可以从头使用空着的空间。
当front为MAXSIZE时，也是一样。

引入循环队列
base[0]接在base[MAXSIZE-1]之后，若rear+1 == MAXSIZE，则令rear=0。
实现方法：利用模运算(mod，C语言中：%)运算。
插入元素

Q.base[Q.rear] = x;
Q.rear = (Q.rear+1) % MAXSIZE;

删除元素

x = Q.base[Q.front];
Q.front = (Q.front+1) % MAXSIZE;

循环队列：循环使用为队列分配的存储空间。

使用循环队列后，上图中存在的问题就解决了，如下图所示：

这里还有一个问题，现在队空和队满的条件都是：front == rear，这样怎么区分队空还是队满呢？

解决方案：

另设一个标志区别队空、队满。
另设一个变量，记录元素个数。
少用一个元素空间。

本课程使用第三种方式

这时候队空的条件是：front == rear
队满的条件是：(rear+1) % MAXSIZE == front

顺序队列的基本操作实现

【InitQueue】初始化队列

Status InitQueue(SqQueue* Q) {
    Q->base = (SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);
    if (!Q->base) exit(OVERFLOW);
    Q->front = Q->rear = 0;
    return OK;
}

【QueueLength】求队列的长度

Status QueueLength(SqQueue* Q) {
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

【EnQueue】循环队列入队

Status EnQueue(SqQueue* Q, QElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return OK;
}

【DeQueue】循环队列出队

Status DeQueue(SqQueue* Q, QElemType* e) {
    if (Q->front == Q->rear) return ERROR;
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return OK;
}

【GetHead】获取队头元素

QElemType GetHead(SqQueue* Q) {
    if (Q->front == Q->rear) return ERROR;
    return Q->base[Q->front];
}

队列的链式表示

// 由两个结构体共同组成
typedef struct QNode {
    QElemType data;
    struct QNode* next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr front;    // 队头指针
    QueuePtr rear;    // 队尾指针
} *LinkQueue;

链队列.png

链队列的基本操作实现

【InitQueue】链队列的初始化

Status InitQueue(LinkQueue* Q) {
    (*Q)->front = (*Q)->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!((*Q)->front)) exit(OVERFLOW);
    (*Q)->front->next = NULL;
    return OK;
}

【DestoryQueue】链队列的销毁

Status DestoryQueue(LinkQueue* Q) {
    while ((*Q)->front) {
        (*Q)->rear = (*Q)->front->next;
        free((*Q)->front);
        (*Q)->front = (*Q)->rear;
    }
    return OK;
}

【EnQueue】链队列入队

Status EnQueue(LinkQueue* Q, QElemType e) {
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    (*Q)->rear->next = s;
    (*Q)->rear = s;
    return OK;
}

【DeQueue】链队列出队

Status DeQueue(LinkQueue* Q, QElemType* e) {
    if ((*Q)->front == (*Q)->rear) return ERROR;
    QueuePtr p = (*Q)->front->next;
    *e = p->data;
    (*Q)->front->next = p->next;
    if (p == (*Q)->rear) (*Q)->rear = (*Q)->front;
    free(p);
    return OK;
}

【GetHead】求链队列的队头元素

Status GetHead(LinkQueue* Q, QElemType* e) {
    if ((*Q)->front == (*Q)->rear) return ERROR;
    *e = (*Q)->front->next->data;
    return OK;
}