数据结构之栈和队列
栈和队列的定义
栈和队列是两种常用的数据结构，是限定插入和删除只能在表的“端点”进行的线性表
栈的操作具有后进先出的固有特性
如“数值转换” “表达式求值” “括号匹配检验” “八皇后问题” “函数调用” “迷宫求解” 等等
队列的操作具有先进先出的特性
使得队列成为程序设计中解决类似排队问题的工具
栈的定义和特点
是一个特殊的线性表，限定仅在一端（通常是表尾）进行插入和删除操作的线性表
又称为后进先出，简称LIFO结构
表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base
插入元素到栈顶（表尾）的操作称为入栈；
从栈顶删除最后一个元素的操作称为出栈
压入=PUSH(x)弹出=POP(y)
队列的定义和特点
在表一端插入（表尾），在另一端（表头）删除
案例引入
案例1 进制转换
案例2 括号匹配的检验
案例3 表达式求值
案例4 舞伴问题
栈的抽象数据类型的类型定义
ADT Stack {
数据对象：
D={ai|ai属于ElemSet,i=1,2,3,...n,n>=0}
数据关系：
R1={<ai-1,ai>|ai-1，ai属于D，i=2，...,n}
约定an端为栈顶，a1端为栈底。
基本操作：初始化、进栈、出栈、取栈顶元素等
}
}ADT Stack - InitStack(&S)：初始化操作，构造一个空栈S
- DestoryStack(&S)：销毁栈操作
- StackEmpty(S)：判断S是否为空栈
- StackLength(L):返回S的元素个数
- GetTop(S,&e):取栈顶元素
- ClearStack(&S):栈置空操作
- Puah(&S,e):插入元素e为新的栈顶元素
- Pop(&S,&e):删除S的栈顶元素，并用e返回其值
顺序栈的表示和实现
存储方式：与一般线性表的顺序存储结构完全相同
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端
- top指针：指示栈顶元素在顺序栈中的位置
- base指针，指示栈底元素在顺序栈中的位置
但是，为了方便操作，通常top指示真正的栈顶元素之上的下表地址
另外，用stacksize表示栈可以使用的最大容量
使用数组作为顺序栈存储方式的特点：
简单方便单易产生溢出（数组大小固定）
上溢：栈已经满，又要压入元素
下溢：栈已经空，还要弹出元素
上溢是一种错误，而下溢一般认为是一种结束条件，即问题处理结束
顺序栈的数据类型定义
#define MAXSIZE 100
typedef struct {
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize; //栈可用最大容量
}SqStack;
```
### **算法1** 顺序栈的初始化
```C
Status InitStack(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;
}算法2 顺序栈判断是否是空
Status StackEmpty(SqStack S){
if(S.top==S.base)return TRUE;
else return FALSE;
}算法3 求顺序栈长度
Status StackLength(SqStack S){
return S.top-S.base；
}算法4 清空顺序栈
Status ClearStack(SqStack S){
if(S.base)S.top=S.base;
return OK;
}算法5 销毁顺序栈
Status DestroyStack(SqStack &S){
if(S.base){
delete S.base;
S.stacksize=0;
S.base= S.top =NULL;
}
return OK;
}算法6 顺序栈的入栈
Status Push(SqStack &S,SElemType e){
if(S.top-S.base==S.stacksize)//栈满
return ERROR;
*S.top++=e;//*S.top=e;S.top++;
return OK;
}算法7 顺序栈的出栈
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)//等价于if(StackEmpty(S))
return ERROR;
e=*--S.top;//--S.top;e=*S.top;
return OK;
}链栈的表示和实现
链栈是运算受限的单链表，只能在链表头部进行操作
typedef struct StackNode{
SElemType data；
struct StackNode *next;
}StackNode,*LinkStack;
LinkStack S;
算法1 链栈的初始化
void InitStack(LinkStack &S){
//构造一个空栈，栈顶指针置为空
S=NULL;
return OK;
}算法2 链栈的初始化
void InitStack(LinkStack &S){
//构造一个空栈，栈顶指针置为空
S=NULL;
return OK;
}算法3 判断链栈是否为空
void StackEmpty(LinkStack S){
if(S==NULL)return TRUE;
else return FALSE;
}算法4 链栈的入栈
Status Push(LinkStack &S,SElemType e){
p=new StackNode;
p->data=e;
p->next=S;
S=p;
return OK;
}算法5 链栈的出栈
Status Pop(LinkStack &S,SElemType &e){
if(S==NULL)return ERROR;
e=S->data;
p=S;
S=S->next;
delete p;
return OK;
}算法6 取栈顶元素
SElemType GetTop(LinkStack S){
if(S!=NULL)
return S->data;
}栈和递归
注：栈的应用与递归详见数据结构书中P48页始
队列的表示和操作实现
是仅在表尾进行插入操作，在表头进行删除操作的线性表
表尾即an端，称为队尾，表头为a1端，称为对头。
先进先出
插入元素称为入队，删除元素称为出队
队列的存储结构为链队或顺序队。
队列的抽象数据类型定义
ADT Queue {
数据对象：
D={ai|ai属于ElemSet,i=1,2,3,...n,n>=0}
数据关系：
R={<ai-1,ai>|ai-1，ai属于D，i=2，...,n}
约定an端为栈顶，a1端为栈底。
基本操作：初始化等
}
}ADT Queue 队列的顺序表示
#define MAXQSIZE 100
typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front; //头指针(队头元素下标)
int rear; //尾指针(队尾元素下标)
}SqQueue;
解决假上溢的方法：引入循环队列
循环队列的类型定义
算法1 循环队列的类型定义
#define MAXQSIZE 100
typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front; //头指针(队头元素下标)
int rear; //尾指针(队尾元素下标)
}SqQueue;算法2 循环队列的初始化
Status InitQueue(SqQueue &Q){
Q.base = new QElemType[MAXQSIZE] //分配数组空间
if(!Q.base) exit (OVERFLOW);
Q.front=Q.rear=0; //头指针尾指针置为0，队列为空
return OK;
}算法3 循环队列的长度
int QueueLength(SqQueue Q){
return((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
}算法4 循环队列的入队
Status EnQueueLength(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;
}算法5 循环队列的出队
Status DeQueueLength(SqQueue &Q，QElemType &e){
if(Q.front==Q.rear)return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}算法6 取队头元素
SElemType GetHead(SqQueue Q){
if(Q.front!=Q.rear)return Q.base[Q.front];
}队列的链式表示和实现
算法1 链队列的类型定义
#define MAXQSIZE 100
typedef struct Qnode{
QElemType data;
struct Qnode *next;
}QNode,*QuenePtr;typedef struct {
QuenePtr front;//队头指针
QuenePtr rear;//队尾指针
}LinkQuene;
算法2 链队列的初始化
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}算法3 链队列的销毁
Status DestroyQueue(LinkQueue &Q){
while(Q.front){
p=Q.front->next;
free(Q.front);
Q.front=p;}
return OK;
}算法4 链队列的销毁
Status DestroyQueue(LinkQueue &Q){
while(Q.front){
p=Q.front->next;
free(Q.front);
Q.front=p;}
return OK;
}算法5 链队列的元素入队
Status EnQueue(LinkQueue &Q,QElemType e){
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit (OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}算法6 链队列的元素出队
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;
}算法7 链队列的队头元素
Status GetHead(LinkQueue Q,QElemType &e){
if(Q.front==Q.rear)return ERROR;
e=Q.front->next->data;
return OK;
}
