数据结构第三章

3 栈和队列

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在千栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。

3.1 栈和队列的定义和特点

栈和队列是两种常用的、重要的数据结构
栈和队列是限定插入和删除只能在表的端点进行的线性表
- 线性表可以删除任意位置
- 栈只能在表尾插入或删除（类似弹夹，后面对应名词压入弹出都能十分契合）
- 队列只能在表尾插入或表头删除（类似于排队，队头先走，人来了在队尾）
  - 特性：栈——后进先出
由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具
- 数制转换 表达式求值 括号匹配检验 八皇后问题
  
  行编辑程序 函数调用 迷宫求解 递归调用的实现
由于队列具有先进先出的特性，使得队列可以解决类似排位问题的有用工具
- 脱机打印输出：按申请的先后顺序依次输出
  
  多用户系统中，多个用户排成队，分时地循环使用CPU和主存，按用户的优先级排成多个队，每个优先级一个队列
  
  实时控制系统中，信号按接收的先后顺序依次处理
  
  网络电文传输，按到达的时间先后顺序依次进行

3.1.1 栈的定义和特点

栈的定义：是一种特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表
- 又称为后进先出的线性表，简称LIFO结构（Last in First Out）
- 表尾称为栈顶，表头称为栈底，插入元素到栈顶的操作，称为入栈（压入、进栈、压栈），从栈顶删除最后一个元素的操作，称为出栈（弹出、弹栈）
栈的逻辑结构：与线性表相同，仍为一对一关系。
栈的存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
栈的运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则
栈的实现方式：关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同

3.1.2 队列的定义和特点

队列的定义：是一种先进先出的线性表，简称FIFO结构
- 只能插入到队尾，从队头删除
队列的逻辑结构：同线性表，仍为一对一关系。
队列的存储结构：顺序队或链队，以循环顺序队列更常见
队列的运算规则：只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则
队列的实现方式：关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

3.2 案例引入

案例3.1：进制转换

十进制整数N向其他进制数d（二、八、十六）的转换是计算机实现计算的基本问题。

转换法则：除以d倒取余

该转换法则对应于一个简单算法原理：

*n=(n div d)d+n mod d

其中：div为整除运算，mod为求余运算
例：十进制把159转换成八进制

运用到栈的后进先出的特性

3.2.1：括号匹配的检验

假设表达式中允许包含两种括号：圆括号和方括号
检验（（）】）是否匹配

后进的括号与前面括号进行匹配，如果为相同括号的两边，则栈顶的左括号弹出，也符合后进先出的特性
- 若遇到一下集中情况之一，说明括号不匹配
  1. 遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
  2. 当栈中弹出的左括号与当前检验的右括号类型不同，则说明出现了括号交叉情况；
  3. 表达式输入完毕后，但栈中还有没匹配的左括号，说明左括号多于右括号。

3.3.2：表达式求值

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

——算符优先算法
- 表达式的组成
  - 操作数：常数、变量。
  - 运算符：算术运算符、关系运算符和逻辑运算符。
  - 界限符：左右括弧和表达式结束符。
- 任何一个算术表达式都由操作数、算术运算符和界限符组层。后两者统称为算符
  - 例如：#3*（7-2）#
    为了实现表达式求值。需要设置两个栈
    - 一个是算符栈OPTR，用于寄存运算符
    - 另一个称为操作数栈OPND，用于寄存运算数和运算结果
    求值的处理过程是自左至右扫描表达式的每一个字符
    - 当扫描到的是运算数，则将其压入栈OPND
    - 当扫描到的是运算符时
      - 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
      - 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
      - 继续处理当前字符，直到遇到结束符为止。

3.2.3：舞伴问题

舞会上男女各排一队，舞会开始从队头各出一人配成舞伴，如果两队初始人数不同，则较长那一队未配对者等待下一轮舞曲。
该问题具有典型的先进先出特性，可以用队列作为是算法的数据结构
- 首先构造两个队列
- 依次将队头元素出队配成舞伴
- 某队为空，则另外一队等待者为下一舞曲第一个可获得舞伴的人。

3.3 栈的表示和操作的实现

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

基本操作：

InitStack(&S)

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

DestroyStack(&S)

初始条件：栈s巳存在。

操作结果：栈S被销毁。

ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。

StackEmpty(S)

初始条件：栈S巳存在。

操作结果：若栈 s 为空栈，则返回 true, 否则返回 false**。**

StackLength (S)

初始条件：栈S已存在。

操作结果：返回s的元素个数，即栈的长度。

GetTop(S)

初始条件：栈S已存在且非空。

操作结果：返回s的栈顶元素，不修改栈顶指针。

Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

Pop(&S,&e)

初始条件：栈s已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

StackTraverse(S)

初始条件：栈S已存在且非空。

操作结果：从栈底到栈顶依次对S的每个数据元素进行访问。

3.3.2 顺序栈的表示和实现

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

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

设top指针，指栈顶元素在顺序栈中的位置

另设base指针，指示栈底元素在顺序栈中的位置

但是为了方便操作，通常top指示真正的栈顶元素之上的下标地址

另外用stacksize表示栈可使用的最大容量

空栈：base==top是栈空的标志

栈满：top-base==stacksize

栈满时的处理方法：
1. 报错，返回操作系统。
2. 分配更大的空间
使用数组作为顺序栈存储方式的特点：
- 简单、方便、但容易产生溢出
  - 上溢：栈已满，又要压入元素
  - 下溢：栈已空，还要弹出元素
- 一般上溢是错误，下溢是一种结束条件，即问题处理已结束

顺序栈的表示

#define MAXSIZE 100
typeldef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

3.3.2.1 顺序栈的初始化

Status lnitStack(SqStack &S){				//构造空栈
	S.base=new SElemType[MAXSIZE]; 
    //或S.base=(SElemType*)malloc(MAXSIZE*sizeof（SElemType));
	if (!S.base)exit (OVERFLOW);			//存储分配失败
	S.top=S.base;							//栈顶指针等于栈底指针
	S.stacksize=MAXSIZE;
    return OK；
}

算法补充：顺序栈判断栈是否为空

Status StackEmpty（SqStack S){
    //若栈为空，返回TRUE否则返回FALSE
    if(S.top==S.base)
        return TRUE;
    else
        return FALSE;
}

算法补充：求顺序栈长度

1
2
3

int StackLength(SqStack S){
    return S.top-S.base;
}

算法补充：清空顺序栈

Status ClearStack(SqStack S){
    if (S.base)S.top=S.base;
    return OK;
}

算法补充：销毁顺序栈

Status DestroyStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize=0:
        S.base=S.top=NULL;
    }
    return OK;,			
}

3.3.2.2 顺序栈的入栈

Status Push(SqStack &S.SElemType e){
    if（S.top-S.base==S.stacksize)
        return ERROR;
    *S.top++=e:
    return OK;
}

3.3.2.3 顺序栈的出栈

Status Pop(SqStack &S,SElemType &e){
    if(S.top==S.base)
        return ERROR;
    e=*--S.top;
    return OK;
}

3.3.3 链栈的表示和实现

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

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

链表头结点就是栈顶
不需要头结点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

3.3.3.1 链栈的初始化

void lnit Stack(LinkStack &S){
    S=NuLL;
    return OK;
}

算法补充：判断链栈是否为空

Status StackEmptyl(LinkStack S){
    if(S==NULL)return TRUE;
	else return FALSE;
}

3.3.3.2 链栈的入栈

Status Push(LinkStack &S,SElemType e){
    p=new StackNode;	//生成新结点p
    p->data=e;			//将新结点数据域置为e
    p->nextg=S;			//将新结点插入栈顶
    S=p;				//修改栈顶指针
    return OK;
}

相当于头插法

3.3.3.3 链栈的出栈

Status Pop（LinkStack &S,SElemType &e){
    if(S==NULL)return ERROR;
    e=S->data;
    p=S;
    S=S->next;
    delete p;
    return OK;
}

3.3.3.4 取栈顶元素

SElemType GetTop(LinkStack S){
	if(S!=NULL)
    return S->data;
}

3.4栈与递归

递归的定义
- 若一个对象部分地包含它自己，或用他自己给自己定义，则称这个对象是递归的
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
  - 例如：递归求n的阶乘
    1
    2
    3
    4
    long Fact(long n){
    if(n==0)return 1;
    else return n*Fact(n-1);
    }
- 以下三种情况尝尝用到递归方法
  - 递归定义的数学函数
    - 阶乘函数
    - 二阶fibonaci数列
  - 具有递归特性的数据结构
    - 二叉树
    - 广义表
  - 可递归求解的问题
    - 迷宫问题
    - hanoi塔问题
- 递归问题——用分治法求解
  - 分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
  - 必备的三个条件
    1. 能够将一个问题转变成一个新的问题，而新的问题与原问题解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
    2. 可以通过上述转化而使问题简化
    3. 必须有一个明确的递归出口或递归的边界

分治法求解递归问题算法的一般形式：

函数调用过程

调用前，系统完成：
1. 将实参，返回地址等传递给被调用函数
2. 为被调用函数的局部变量分配存储区
3. 将控制转移到被调用函数的入口
调用后，系统完成：
1. 保存被调用函数的计算结果
2. 释放被调用函数的数据区
3. 依照被调用函数保存的返回地址将控制转移到调用函数

递归的优缺点
- 优点：结构清晰，程序易读
- 缺点：每次调用都要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大
  
  递归->非递归
  1. 尾递归、单项递归->循环结构
  2. 自用栈模拟系统的运行时栈

3.5 队列的表示和操作的实现

3.5.1 队列的抽象数据类型定义

3.5.2 队列的顺序表示和实现

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。相应的队列的存储方式也分为两种，即顺序队列和链式队列
队列的顺序表示——用一维数组base[MAXQSIZE]

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

若front=0且rear=MAXQSIZE时，再入队——真溢出
若front不为0，rear=MAXQSIZE时，再入队——假溢出，此时队列中还有空间可以存放
- 解决假溢出可以吧队的空间想象成一个循环的表
  - 引入循环队列
    1. 实现方法：利用%运算
    2. 插入元素：Q.base[Q.rear]=x;
      
      Q.rear=（Q.rear+1)%MAXQSIZE;
    3. 删除元素：x=Q.base[s.front]
      
      Q.front=(Q.front+1)%MAXQSIZE
    4. 循环队列:循环使用为队列分配的存储空间。
因为队空队满都是：front==rear
- 所以我们常常另设一个标志来区别队空队满、另设一个变量，记录元素个数或者少用一个元素空间。
- 队满时——少用一个元素空间
  - 队空：front==rear
  - 队满：（rear+1)%MAXQSIZE

3.5.2.1 队列的初始化

Status InitQueue(SqQueue &Q){
    Q.base=(QElemType*)
    malloc(MAXQSIZE*sizeof（QElemType)）；
    if（!Q.base)exit(OVERFLOW);
    Q.fornt=Q.rear=0;
    return OK;
}

3.5.2.2 求队列的长度

1
2
3

int QueueLength(SqQueue Q){
    return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
}

3.5.2.3 循环队列入队

Status EnQueue(SqQueue &Q，QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}

3.5.2.4 循环队列出队

Status DeQueue(SqQueue &Q,QElemType &e){
    if(Q.rear==Q.front) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK；

3.5.2.5 取队头元素

1
2
3

Status GetHead(SqQueue Q){
    if(Q.front!==Q.rear);
    return Q.base[Q.front];				//返回队头指针元素的值，队头指针不变

3.5.3 链队——队列的链式表示和实现

若用户无法估计所用队列长度，则宜采用链队列

链队的类型定义

#define MAXQSIZE 100 
typedef struct Qnode{
    QElemType data;
    stuct Qnode *next;
}QNode,*QueuePtr			//ptr是pointer的缩写
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

3.5.3.1 链队的初始化

Status InitQueue (LinkQueue &Q){
    Q.front=Q.rear=new QNode;
    if(!Q.front)exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;
}

3.5.3.2 链队列的销毁

Status DestroyQueue(LinkQueue &Q){
    while(Q.front){
        p=Q.front->next;
        ferr(Q.front);
        Q.front=p;
    }
    return OK;
}

3.5.3.3 链队列的入队

Status EnQueue (LinkQueue &Q, QElemType e){
    p=new QNode;
    p->data=e;
    p->next=NULL; Q. rear->next=p;
    Q.rear=p;
    return OK;
}

3.5.3.4 链队列的出队

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

3.5.3.5 链队列取队头

SElemType GetHead{LinkQueue Q){
    if(Q.front!=Q.rear)
        return Q.front->next->data;
}