栈的定义
----------------------------------------------
定义：栈是一个后进先出（Last in first out，LIFO）的线性表，它要求只在表尾进行删除和插入操作
特点：1.栈的元素必须要后进先出
2.栈的操作只能在线性表的表尾进行
3.栈的表尾称为栈的栈顶(top)，相应的表头称为栈底(bottom)
4.表头==栈底，表尾==栈顶
5.栈顶是高地址，栈底是低地址

栈的插入(push),进栈、压栈、入栈

栈的删除(pop),出栈、弹栈

栈的存储形式：顺序存储结构和链式存储结构，一般应用栈的顺序存储结构

最开始栈中不含任何数据，叫做空栈，此时栈顶就是栈底，数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大，
数据出栈时从栈底弹出，栈顶下移，整个栈的当前容量变小

顺序存储结构
----------------------------------------------
定义：typedef struct
{
ElemType *base;    //栈底指针变量
ElemType *top;    //栈顶指针变量
int stackSize;    //栈当前可用的最大容量
}sqStack;

创建栈
#define STACK_INIT_SIZE 100    //栈的最大容量
initStack(sqStack *s){
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));    //调用函数malloc申请空间
if( !s->base )    exit(0);    //申请空间失败，异常判断
s->top = s->base;    //初始状态栈底就是栈顶
s->stackSize = STACK_INIT_SIZE;    //栈当前可用的最大容量
}
入栈
入栈操作又叫压栈操作，就是向栈中存放数据。
入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针+1，直到栈满为止
code：
-----------
#include <stdio.h>
#include <stdlib.h>

    #define SATCKINCREMENT 10      //追加空间量

    Push(sqStack *s, ElemType e){
/*如果栈满追加空间*/
if(s->top - s->base >= s->stackSize){
s->base = (ElemType *)relloc(s->base,(s->stackSize + SATCKINCREMENT) * sizeof(ElemType));   //使用relloc函数追加空间，将原存储单元中的数据复制到新建的更大存储单元中
if( !s->base )  exit(0);        
s->top = s->base + s->stackSize;    //设置栈顶==栈底+当前栈空间的容量
s->stackSize = s->stackSize + SATCKINCREMENT;   //设置栈的最大容量，栈的当前容量+扩容容量

}
*(s->top) = e;  //向栈中放入数据
s->top++;       //当有数据放入时，栈顶增加      
}

出栈
出栈操作就是在栈顶取出数据，栈顶指针随之下移，每取出一个数据，栈的当前容量-1
栈顶不存放数据，取出的数据为栈顶的下一个数据
栈为空的时候，top=-1
code
-----------
Pop(sqStack *s, ElemType *e){
if(s->top == s->base)   return 0;   //空栈
*e = *--(s->top);   //栈顶不存放数据，取出的数据为栈顶的下一个数据
}

清空栈
只需要将s->top的内容赋值给s->base
原理与高级格式化单纯清空文件列表而没有覆盖硬盘的原理一样
清空栈其本身的物理空间不发生改变，数据仍然存在
code
-----------
ClearStack(sqStack *s){
s->top = s->base;
}

销毁栈
与清空栈不同，需在在存储存储单元中彻底销毁，释放所占用的空间
code
-----------
DestoryStack(sqStack *s){
int i,len;
len = s->stacksize;    //获取栈的容量
for(i = 0; i < len; i++){
free( s->base );    //从栈底（低地址）处开始释放空间
s->base++;        
}
s->base = s->top = NULL;
s->stacksize = 0;
}

计算栈的当前容量
指针之间不可以相加，可以++，--，和-
栈顶与栈顶的差值为当前栈所占用的字节数
栈的最大容量s->stacksize与当前容量不同
code
-----------
int StackLen(sqStack s)
{
return(s->top - s->base);
}

利用栈的数据结构将二进制转换为十进制
如果栈满，仍然压进去数据，导致溢出。
C语言无法检测数据的边界，如果数据超过指定数组长度，数组溢出。出现溢出漏洞
code
-----------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

    #define STACK_INIT_SIZE 20
#define STACKINCREMENT  10;

    typedef char ElemType

    /*定义栈*/
typedef struct {
ElemType *top;
ElemType *base;
int stacksize;
}sqStack;

    /*初始化栈*/
void InitStack(sqStack *s){
s = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); //为创建的栈分配空间
if ( !s->base ) exit(0);    //判断分配空间是否成功
s->top = s->base;   //初始化时，栈的首尾指向同一地址单元
s->stacksize = STACK_INIT_SIZE; //设置新生成的栈的空间大小为STACK_INIT_SIZE
}

    /*入栈*/
void Push(sqStack *s, ElemType e){
/*判断栈是否溢出，溢出时增加容量*/
if( s->top - s->base >= stacksize){
s->base = (ElemType)relloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(ElemType)) //使用relloc函数进行栈的扩容
if( !s->base )  exit(0);    //判断扩容是否成功
}
*(s->top) = e;  //将元素e压入栈
s->top++;   //栈顶向上移动
}

    /*出栈*/
void Pop(sqStack *S, ElemType e){
if(s->top == s->base)   return; //判断栈是否为空
*e = *--(s->top);   //出栈操作
}

    /*计算栈的大小*/
int StackLen(sqStack s){
int len = s->top - s->base; //计算栈的大小
return len;
}

    int main(){
ElemType c;
sqStack s;
int len,Decimal;

        InitStack(&s);

        printf("请输入二进制数，按回车结束：%c", c);
while( !c = '\n'){
scanf("%c",&c);
Push(&s,c);
}
len = StackLen(s);
for(int i = 0; i < len; i++){
Pop(&s,&c)
Decimal = Decimal + (c - 48) * pow(2, i);
}
printf("转化为十进制数为：%d\n", Decimal);
return 0;
}

二进制转换为其他进制
转换为八进制
code
-----------
int main(){
ElemType c;
sqStack s,p;
int len,Decimal;

        InitStack(&s);

        printf("请输入二进制数，按回车结束：%c", c);
while( !c = '\n'){
scanf("%c",&c);
Push(&s,c);
}
len_sz = StackLen(s) / 3;
len_sy = StackLen(s) % 3;
for(int i = 0; i < (len_sy == 0 ? len_sz : len_sz + 1 ); i++){
for(int j = 0; j < 3; j++)
{
Pop(&s,&c);  
Decimal = Decimal + (c - 48) * pow(2, i);
}
Push(&p,Decimal);
}
len_p = StackLen(p);
for(int k = 0; k < len_p; k++){
Pop(&p,&Decimal);
printf("转化为八进制数为：%d\n", Decimal);
}
return 0;
}

栈的链式存储结构
----------------------------------------------
简称栈链
结构定义
code
-----------
typedef struct StackNode{
Elemtype data;    //存放栈的数据
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;    //top指针
int count;        //栈元素计算器
}

入栈
code
-----------
Status Push (LinkStackPtr *s Elemtype e){
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));    //创建新的元素
p->data = e;    //为新的元素赋值
p->next = s->top;    //将新元素入栈
s->top = p;    //栈顶指向新的元素，迭代入栈；
s->count++;    //栈元素数目
return 1;
}

出栈
code
-----------
Status Pop(Linkstack *s,Elemtype e){
LinkStackPtr p;
if(StackEmpty(*s))    return 0;    //判断是否为空栈
*e = s->stop->data;
p = s->top;
s->top = s->top->next;
free(p);
s->count--;
return 1;
}

逆波兰计算器
----------------------------------------------
逆波兰表达式
a + b ==> a b +
a + (b - c) ==> a b c - +
a + (b - c) * d ==> a b c - d * +
a + d * (b - c) ==> a d b c - * +

    code
-----------
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

    #define STACK_INIT_SIZE 20
#define STACKINCREMENT  10
#define MAXBUFFEER      10

    typedef double ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSzie;
}sqStack;

    InitStack(sqStack *s){
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if( !s->base )  exit(0);
s->top = s->base;
s->stackSzie = STACK_INIT_SIZE;
}

    Push(sqStack *s, ElemType e){
if (s->top - s->base >= s->stackSzie){
s-base = (ElemType *)relloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base)   exit(0);
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e;
s->top++;
}

    Pop(sqStack *s,ElemType *e){
if(s->top == s->base)   return;
*e = *--(s->top);
}

    int StackLength(sqStack s){
int len = s->top - s->base;
return len;
}

    int mian(){
sqStack s,q;
char c;
double d,e;
char str[MAXBUFFEER];   //定义缓冲区，将输入的数字串接成为一个数
int i = 0;

InitStack(&s);

printf("请按逆波兰表达式的输入待以计算数据\n数据与运算符之间用空格隔开，以#作为结束标志")
scanf("%c",&c);

while( c != '#'){
while( isdigit(c) || c == '.'){     //用于过滤数字
str[i++] = c;   //将数字接收
str[i] = '\0';  //？？？？？？？？？？？？？？？
if( i > 10) printf("输入的数据过大")；  //超过缓冲区大小
scanf("%c",&c);
if(c == ' '){   //输入空格时表示一个数据输入完毕
d = atof(str);  //将字符换类型转换为浮点类型
push(&s, d);    //将筛选的数据压入栈中
i = 0;
break;
}
}
switch (c){     //判断运算符，进行相应的算法
case '+':
Pop(&s,&d);
Pop(&s,&e);
Push(&s,d + e);
break;
case '-':
Pop(&s,&d);
Pop(&s,&e);
Push(&s,d - e);
break;
case '*':
Pop(&s,&d);
Pop(&s,&e);
Push(&s,d * e);
break;
case '/':
Pop(&s,&d);
Pop(&s,&e);
if( e != 0) Push(&s,d / e);
else {
printf("除数不可以为0")；
return -1;
}
break;
}
scanf("%c",&c);     //继续输入后续计算
}
Pop(&s,&d);     //取出最后压入栈中的数据，即为最终结果
printf("最终的计算结果为：%d", d);

}

中缀表达式转化为后缀表达式
设计思路：从左到右遍历中缀表达式中的每个数字和符号，若是数字，直接输出；
若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，
则栈顶元素依次出栈并输出，直到遇到左括号或者栈空格才将吃屎的符号入栈
code
-----------
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

    #define STACK_INIT_SIZE 20
#define STACKINCREMENT  10
#define MAXBUFFEER      10

    typedef double ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSzie;
}sqStack;

    InitStack(sqStack *s){
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if( !s->base )  exit(0);
s->top = s->base;
s->stackSzie = STACK_INIT_SIZE;
}

    Push(sqStack *s, ElemType e){
if (s->top - s->base >= s->stackSzie){
s-base = (ElemType *)relloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base)   exit(0);
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
*(s->top) = e;
s->top++;
}

    Pop(sqStack *s,ElemType *e){
if(s->top == s->base)   return;
*e = *--(s->top);
}

    int StackLength(sqStack s){
int len = s->top - s->base;
return len;
}

    int main(){
sqStack s;
char c,e;   //c为输入的数据，e用来存放临时数据

        InitStack(&s);

        printf("请输入中缀表达式，以#作为结束符");
scanf("%c",&c);

        while( '#' != c ){
while( isdigit(c) ){
printf("%c ",c);     //遍历栈的过程中，如果是数字则直接打印
scanf("%c",&c);
if( isdigit(c) ){
printf(" ");
}
}    
if( ')' == c ){ //如果为），则进行出栈,检验栈中是否有左括号，如果没有左括号，则将栈中的数据输出
Pop(&s,&e);
while( '(' != e){
printf("%c ",e);
Pop(&s,&e);
}
}
else if( '+' == c || '-' == c ){    //如果输入的元素优先级低于或等于栈中元素的优先级
if( !StackLen(s) ){     //如果栈为空，则将输入的数据压入栈中
Push(&s,c);
}else{
do{
Pop(&s,&e);
if( '(' == e )  Push(&s,e);
else    printf("%c ",c);     //如果输入的数据的优先级与栈中元素的优先级相等，进行打印输出
}while(StackLen(s) && '(' != e );   //判断栈中元素与输入元素的优先级
Push(&s,c); //吃屎的那位压入栈中
}
}
else if ( '*' == c || '/' == c || '(' == c ){
Push(&s,c)；
}
else if ( '#' == c )    break;
else{
printf("输格式错误");
return -1;
}
while(StackLen(s)){
Pop(&s,&e);
printf("%c",e);
}
scanf("%c",&c);
}
}

队列
----------------------------------------------
定义：队列(queue)是只允许在一端进行插入操作，另一端进行删除操作的线性表
队列是一种先进先出的表
队头是出队列的位置，队尾是入队列的位置

队列的链式存储结构
队列既可以用链表实现，与可以用顺序表来实现，跟栈相反的是，栈一般用顺序表实现，队列一般使用链表实现，简称链队列
结构定义
-----------
typedef struct QNode{    //节点数据  结构
ElemType data;    //节点数据
struct QNode *next    //节点指针
}QNode, *QueuePrt;

    typedef struct{
QueuePrt front,rear;    //队头、尾指针
}LinkQueue;

    将对头指针指向链队列的头节点，队尾指针指向终端节点
其中，头节点不是必要的，加上是为了方便操作