C语言数据结构基础学习笔记——栈和队列
之前我们学过了普通的线性表，接下来我们来了解一下两种特殊的线性表——栈和队列。
栈是只允许在一端进行插入或删除的线性表。
栈的顺序存储结构也叫作顺序栈，对于栈顶指针top，当栈为空栈时，top=-1；当栈为满栈时，top=maxsize-1。顺序栈的定义为：
#define maxsize 50 //定义栈中元素的最大个数
typedef struct{
elemtype data[maxsize]; //存放栈中元素
int top; //栈顶指针
}sqstack; //顺序栈的简写
顺序栈的入栈操作为：
bool push(sqstack &s,elemtype x){
if(s.top==maxsize-1) return false;
s.data[++s.top]=x; return true;
}
顺序栈的出栈操作为：
bool pop(sqstack &s,elemtype &x){
if(s.top==-1) return false;
x=s.data[s.top--];
return true;
}
顺序栈读取栈顶元素为：
bool gettop(sqstack s,elemtype &x){
if(s.top==-1) return false;
x=s.data[s.top];
return true;
}
顺序栈读取栈顶元素与出栈操作对比，注意读取栈顶元素时栈顶指针没有自减。
对于一个数组，如果只从数组头部开始入栈，并没有达到很高的空间利用率，因此我们引入共享栈的概念。共享栈是两个栈共用同一个数组，分别从数组头部和数组尾部开始开始入栈。其定义为：
#define maxsize 100 //定义栈中元素的最大个数
typedef struct{
elemtype data[maxsize]; //存放栈中元素
int top1; //栈1顶指针
int top2; //栈2顶指针
}sqdoublestack; //共享栈的简写
bool push(sqstack &s,elemtype x,int stacknum){
if(s.top1+1==s.top2) return false;
if(stacknum==1) s.data[++s.top1]=x;
else if(stacknum==2) s.data[--s.top2]=x;
return true;
}
共享栈的满栈条件是top1+1=top2。
同时，栈也有链式存储结构，叫作链栈，它空栈时top=null，一般不会满栈。链栈的定义为：
typedef struct snode{
elemtype data; //数据域
struct snode *next; //指针域
}snode,*slink; //链式栈的结点
typedef struct linkstack{
slink top; //栈顶指针
int count; //链式栈结点数
}linkstack;
栈有着丰富的应用场景，比较经典的题目有括号的匹配以及后缀表达式的求值。
①括号的匹配：给你一串杂乱的大，中，小括号的序列，让你判断这里的括号序列满不满足数学计算的规律（括号套括号）。主要思路是将所有的左括号依次入栈，碰到右括号出栈匹配，若是不同种的括号返回false，若是同一种括号则继续以上操作，直到空栈并且数组中的字符串遍历完成，返回true。
②后缀表达式的计算：后缀表达式是计算机最喜欢的一种表达式方式，例如（5+10+1*13）/14这个中缀表达式，它的后缀表达式为5 10 + 1 13 * + 14 /，其将每一步计算的运算符号置后。利用栈计算后缀表达式的主要思路是：①将数字5入栈，再将数字10入栈；②当指针碰到运算符+时，将栈中的前两个元素出栈进行计算（后出栈的数在前位），结果入栈，如本例值15入栈；③同上一步，计算1*13得13入栈，此时栈底值15，栈顶值13；④同上一步，指针碰到运算符+，将15与13求和，得值28入栈；⑤再同上一步，计算28/14=2入栈；⑥此时字符串数组遍历完毕，栈中的唯一值2则为表达式的结果。
栈思想的最重要的一个应用便是递归，递归是指在一个函数、过程或数据结构中的定义中又应用了它自身的编程思想。理解递归的一个基础方法便是找到递归式和递归边界，我们来看两个例子：
①用递归求n的阶乘：
int f(int n){
if(n==0) return 1; //递归边界
else return n*f(n-1); //递归式
}
②求斐波那契数列的第n项：
int fib(int n){
if(n==0) return 0; //递归边界
else if(n==1) return 1; //递归边界
else return fib(n-1)+fib(n-2); //递归式
}
递归式是每一次递归过程的计算核心，而递归边界就是每一次递归的结束标志。
另一种特殊的线性表是队列，队列的定义是只允许在一端进行插入，而在另一端进行删除的线性表。
队列的顺序存储结构是顺序队列，其定义为：
#define maxsize 50 //定义队列中元素的最大个数
typedef struct{
elemtype data[maxsize]; //存放队列中元素
int front,rear; //队头指针和队尾指针
}sqqueue;
但对于一个数组队列来说，每一次入队和出队都会浪费一个数组位置，于是我们引入循环队列的概念，队尾指针rear在指到队尾后会回到下标为0的位置（利用取余来实现），即每一次rear和front的更新基于以下操作：rear=(rear+1)%maxsize,front=(front+1)%maxsize。
但是这样又产生了新的问题，rear=front到底是队空还是队满无法判断。这样的问题有以下两种解决办法：①设一个frag，作为标志位，当队满时frag=1；②牺牲一个数组位置，保留一个空余单元，此时队满的判断标准变成了(rear+1)%maxsize=front，队列中的元素数计算方法为：(rear-front+maxsize)%maxsize。
循环队列的入队操作为：
bool enqueue(sqqueue &q,elemtype x){
if((q.rear+1)%maxsize==q.front) return false; //队满
q.data[q.rear]=x;
q.rear=(q.rear+1)%maxsize;
return true;
}
循环队列的出队操作为：
bool dequeue(sqqueue &q,elemtype &x){
if(q.rear==q.front) return false; //队空
x=q.data[q.front];
q.front=(q.front+1)%maxsize;
return true;
}
队列链式存储的定义为：
typedef struct{
elemtype data; //数据域
struct linknode *next; //指针域
}linknode; //链式队列的结点
typedef struct{
linknode *front,*rear; //队头和队尾指针
}linkqueue;
链式队列的入队和出队类似于链表的相应操作。