栈和队列
栈和队列的定义和特点
栈的定义和特点
栈（stack）： 是限定仅在表尾（栈顶）进行插入或删除操作的线性表。
栈的表尾端称为 栈顶（top） ，表头端称为 栈尾（bottom） 。
空栈： 不含数据元素的栈
假设栈 S = {a1,a2,a3 ... an}，栈中元素按照 a1,a2,a3 ... an 的顺序进栈，则称 a1 为栈底元素，称 an 为栈顶元素。
栈又称 后进先出（Last In First Out） 的线性表，简称 LIFO 结构 。
栈的插入操作，叫做进栈，也称压栈、入栈。
栈的删除操作，叫做出栈，也称弹栈。
注意： 栈对线性表的插入和删除的位置进行限制，并没有对元素进出的时间进行限制。 这意味着在任何时候的栈顶元素都可以出栈，哪怕是在将所有元素压栈的过程中。比如1、2、3进栈，当1、2进，3没进时，可以选择将2出栈再让3进栈。
队列的定义和特点
队列（queue）： 是只允许在一端进行插入操作，在另一端进行删除操作的线性表。
队列中允许插入的一端称为 队尾 ，允许删除的一端称为 对头 。
队列是一种 先进先出（First In First Out， FIFO）的线性表。
假设栈 q = {a1,a2,a3 ... an}，其中的元素按照 a1,a2,a3 ... an 的顺序进队列并删除，则称 a1 为对头元素，称 an 为队尾元素。
栈的抽象数据类型
ADT 栈 (stack)
Data
线性表的数据对象为{a1,a2,a3,...,an}，每个数据元素的类型均为 Datatype 。
与线性表一样，数据元素具有相同的类型，相邻元素之间一对一，除了首尾元素都具有前驱和后继的关系。
Operation
InitStack(*s)：初始化操作，创建一个空栈
DestroyStack(*s)：若栈存在，则销毁它
ClearStack(*s)：若栈存在，则清空它
StackEmpty(s)：若栈为空，则返回 OK ，否则返回 ERROR
GetTop(s, *e)：若栈非空，则通过 e 返回栈顶元素
Push(*s, e)：若栈非空且未满，则插入 e 到栈 s 内成为栈顶元素
Pop(*s, *e)：若栈非空，则删除栈 s 中的栈顶元素，并用 e 返回其值
StackLength(s)：返回栈 s 的长度，即栈的元素个数
栈的顺序存储结构和链式存储结构
栈的顺序存储结构的定义
栈的结构定义①：
#define MAXSIZE 1000 //假设栈长度为 1000
typedef int SElemType; // SElemType 视具体情况而定，这里假设为 int
typedef struct {
SElemType data[MAXSIZE];
int top; //栈顶元素的数组下标，空表设为 -1
}SqStack;
栈的结构定义②：
#define MAXSIZE 1000
typedef int SElemType;
typedef struct {
SElemType *top; //栈顶指针
SElemType *base; //栈底指针
int stacksize; //栈空间的最大大小
}SqStack;
定义②的栈的 top ：当栈为空栈时， top 指向栈底，非空时， top 永远指向栈顶元素的下一个位置。
当使用定义①时，判断空栈的条件是 top == -1 ，为真则栈为空，反之非空。
当使用定义②时，判断空栈的条件是 top == base ，为真则栈为空，反之非空。
栈的顺序存储结构的操作
注意： 以下两个操作都是基于定义①的栈定义
进栈操作 的代码实现：
Status Push(Sqstack *s, SElemType e){
if(s->top == MAXSIZE - 1) //判断是否满栈
return ERROR;
s->top++;
s->data[s->top] = e;
return OK;
}
出栈操作 的代码实现：
Status Pop(Sqstack *s, SElemType *e){
if(s->top == -1) //判断是否为空栈
return ERROR;
*e = s->data[s->top];
s->top--;
return OK;
}
初始化操作 的代码实现：
void InitStack(Sqstack *s){
s-> = -1;
}
注意： 以下两个操作都是基于定义②的栈定义
进栈操作 的代码实现：
Status Push(Sqstack *s, SElemType e){
if(s->top - s->base == s.stacksize) //判断是否满栈
return ERROR;
*s->top++ = e; //元素 e 压入栈中，栈顶指针 + 1
}
出栈操作 的代码实现：
Status Pop(Sqstack *s, SElemType *e){
if(s->top == s->base) //判断 s 是否为空栈
return ERROR;
*e = *--s.top;
return OK;
}
初始化操作 的代码实现：
void InitStack(Sqstack *s){
s->base = (Sqstack *)malloc(sizeof(SElemType) * MAXSIZE);
if(!s->base)
exit(OVERFLOW);
s->top = s->base;
s.stacksize = MAXSIZE;
return OK;
}
栈的链式存储结构的定义
栈的链式存储结构，简称链栈。
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;
int count; //元素个数
}LinkStack;
链栈大部分操作都与单链表相似，只是在插入和删除时不太一样。
栈的链式存储结构的操作
初始化操作 的代码实现：
void InitStack(LinkStack *s){
s->top = NULL;
s->count = 0;
}
进栈操作 的代码实现：
Status Push(LinkStack *s, ElemType e){
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
temp->data = e;
temp->next = s->top;
s->top = temp;
s->count++;
return OK;
}
出栈操作 的代码实现：
Status Pop(LinkStack *s, ElemType *e){
LinkStackPtr p;
if(StackEmpty(*s))
return ERROR;
*e = s->top->data;
p = s->top;
s->top = s->top-next;
free(p);
s->count--;
return OK;
}
如果栈的使用过程中元素个数变化不可控，则最好使用链栈；反之使用顺序栈。
栈的作用
栈的引用简化了某些特定的程序设计的问题。好比人类过海开船，去远方坐飞机一样，提高了解决问题的效率。而栈的顺序存储结构相比于数组，不再关注数组的下标的，而是重点关注栈顶。
栈的应用——递归
递归 ：在一个函数、过程或者数据结构定义的内部又直接或间接出现定义本身的应用，则称它们是递归的。
而每一个递归定义都必须至少拥有一个条件： 一个满足该条件时，递归终止，即不再引用自身而是返回值退出，且是按照递归的顺序，反序退出。
例如链表，在定义时，再次调用了自己的定义，所以链表是一种递归的数据结构。
递归和迭代的区别：
- 迭代使用的是循环结构，递归使用的是选择结构。
- 由于大量的递归函数调用会创建过多的函数副本，所以往往会占据大量的时间和内存。而迭代则不会。
- 递归的代码相比迭代更加具有可读性。
因为递归的调用和退出过程很像栈的出栈与入栈，所以 编译器一般都通过栈实现递归函数：
在递归函数的调用过程中，每一次递归都将函数的局部变量、函数形参、以及返回地址压入栈中。在退出时，位于栈顶的局部变量、函数形参、以及返回地址都被弹出。
栈的应用——四则运算表达式求值
逆波兰（Reverse Polish Notation，RPN）表示： 一种不需要括号的后缀表达式，这里的后缀指的是运算符在它的两个运算数字的后面。比如 “9+(3-1)*3+10/2” 表示为 “9 3 1 - 3 * + 10 2 / +”
- 计算机如何应用后缀表达式计算出结果：
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将栈顶两个数字出栈，进行计算并将结果进栈，一直到最终获得结果。
- （重）如何把中缀表达式转为后缀表达式：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分。
若是符号，则判断其与栈顶符号的优先级：若优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈；若优先级高于栈顶符号，则将当前符号进栈；若是左括号“(”，则进栈；若是右括号“)”，则将栈内元素依次出栈，直到将“(”出栈为止，但是注意： 左括号和右括号不输出到后缀表达式中 。
若已经到原表达式的最后，则将栈内符号全部输出。
计算机如何处理中缀表达式 最重要的两步：
- 将中缀表达式转换为后缀表达式（栈用来进出运算的符号）
- 将后缀表达式进行运算得出结果（栈用来进出运算的数字）
队列的定义
队列（queue）： 队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。
队列是一种 先进先出（First In First Out， FIFO）的线性表。队列中允许插入的一端称为 队尾 ，允许删除的一端称为 对头 。
队列的结构定义：
ADT 队列 (Queue)
Data
线性表的数据对象为{a1,a2,a3,...,an}，每个数据元素的类型均为 Datatype 。
与线性表一样，数据元素具有相同的类型，相邻元素之间一对一，除了首尾元素都具有前驱和后继的关系。
Operation
InitQueue(*Q)：初始化操作，建立一个空队列
DestroyQueue(*Q)：若队列存在，则销毁它
ClearQueue(*Q)：若队列存在，则清空它
QueueEmpty(Q)：若队列为空，则返回 OK ，否则返回 ERROR
GetHead(Q, *e)：若队列 Q 存在且非空，则用 e 返回其队头元素
EnQueue(*Q, e)：若队列 Q 存在，则将 e 插入该队列成为其队尾元素
DeQueue(*Q, *e)：若队列 Q 存在且非空，则删除其队头元素并用 e 返回其队头元素
QueueLength(Q)：返回队列 Q 的长度，即队列的元素个数
endADT
循环队列——队列的头尾相接的顺序存储结构
为什么使用循环队列？
如果队列使用常规的顺序存储结构的话，队列头是在数组下标为0的位置，此时入队列操作只需要在队尾插入一个元素即可，时间复杂度为 O(1) 。但是出队列的操作是在队列头操作的，所以每次出队列，除队列后的元素都要向前移一位，用于保证队列头不为空，此时时间复杂度为 O(n) 。
为什么出队列操作中元素全部都要移动呢？而循环队列则是为了解决常规顺序存储结构的入队列操作问题。通过不固定表头在数组首位，再加上两个分别指向首元素 front 和尾元素下一位的下标变量 rear ，即可解决这个问题。
第二个问题：循环队列如何判断队列是否为空？
方法①：设置一个变量 flag ，当 Q->rear == Q->front 和 flag == 0 都为真时，队列非空，反之为空。
方法②：当队列空时 front == rear 为真，当队列满时 (Q->rear + 1) % MAXSIZE == Q->front 为真，我们修改其条件，令满队列保留一个元素空间不存储数据。
循环队列的定义
循环队列： 我们把队列的头尾相接的顺序存储结构称为循环队列
注意： 以下的结构定义和操作都是采取方法②
循环队列的结构 定义：
#define MAXSIZE 1000 //队列可能达到的最大长度
typedef int QElemType;
typedef struct {
QElemType data[MAXSIZE];
int front; //队列头元素的下标
int rear; //队列头元素的下标；若队列不为空，则为尾元素下一个元素的下标
}SqQueue;
循环队列的初始化操作 代码实现：
Status InitQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
求循环队列的长度操作 代码实现：
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
循环队列的入队列操作 代码实现：
Status EnQueue(SqQueue *Q, QElemType e){
if ( (Q->rear + 1) % MAXSIZE == Q->front )
return OK;
Q->data[Q->rear] = e; //从队列尾元素入队列
Q->rear = (Q->rear + 1) % MAXSIZE; // rear 向后移一位，若到最后则转到数组头部
return OK;
}
循环队列的出队列操作 代码实现：
Status DeQueue(SqQueue *Q, QElemType *e){
if ( Q->rear == Q->front )
return OK;
*e = Q->data[Q->front]; //用 e 返回队头元素
Q->front = (Q->front + 1) % MAXSIZE; // front 向后移一位，若到最后则转到数组头部
return OK;
}
队列的链式存储结构及其实现
队列的链式存储结构： 其实就是线性表的单链表，只是只能在队头出元素，队尾进元素，简称 链队列 。
为了操作的方便，我们将队头指针 front 指向链队列的头结点，而队尾指针 rear 指向终端结点。同样地，我们 也给链队列添加头结点 ，用于统一和简化某些操作。
当队列为空时， front 和 rear 指针都指向头结点。
链队列的结构 代码实现：
typedef int QElemType; //假设抽象数据类型为 int ，根据实际情况更改
typedef struct QNode{
QEleType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front, rear;
}LinkQueue;
链队列的出队列操作 代码实现：
Status DeQueue (LinkQueue *Q, QElemType *e){
QueuePtr p;
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;
free(p);
return OK;
}
链队列的入队列操作 代码实现：
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;
}
