— 栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另外一固定端称为“”栈底“，当栈中没有元素时称为”空栈“。特点：后进先出（LIFO）。
— 创建空栈：CreateStack(len)
— 清空栈：CreateStack(S)
— 判断是否空栈：EmptyStack(S)
— 判断是否栈满：FullStack(S)
— 元素进栈：PushStack(S,x)
— 元素出栈：PopStack(S)
— 取栈顶元素：GetStack(S)
typedef int data_t;
typedef struct
{ data_t *data; /* 用指针指向栈的存储空间 */
int maxlen; /* 当前栈的最大元素个数 */
int top; /* 指示栈顶的位置（数组下标）的变量 */
}seqstack_t;
typedef int data_t;
typedef struct node_t
{ data_t data; /* 数据域 */
struct node_t *next; /* 链接指针域 */
}linkstack_t; /* 链栈类型定义 */
几乎所有的编译器都具有检测括号是否匹配的能力，
如何实现编译器中的符号成对检测
算法思路：
从第一个字符开始扫描，
当遇到普通字符时忽略，当遇到左括号时压入栈中，
当遇到右符号时从栈中弹出栈顶符号，并进行匹配，
匹配成功：继续读入写一个字节
匹配失败：立即停止，并报错
结束：
成功：所有字符扫描完毕，且栈为空
失败：匹配失败或所有的字符扫描完毕但栈非空。
当需要检测成对出现但又互不相邻的事物时
可以使用栈“先进先出”的特性
栈非常适合于需要“就近匹配”的场合
应用二：中缀 后缀计算机的本质工作就是做数学运算，那计算机可以读入字符串
中缀表达式：5 + 3 1+ 2 * 3 8 +(3+1)*5
后缀表达式：5 3 + 1 2 3 * + 8 3 1 – 5* +
两者直接可以相互转换： 5+3 =>5 3 + 1+ 2 * 3 => 1 2 3 * + 8 +(3+1)*5 => 8 3 1 – 5* +
中缀表达式符合人类的阅读和思维习惯
后缀表达式符合计算机的 “运算习惯”
如何将中缀表达式转换成后缀表达式？
遍历中缀表达式中的数字和符号
对于数字：直接输出
对于符号：
左括号：进栈
运算符号：与栈顶符号进行优先级比较
若栈顶符号优先级低：此符合进栈 （默认栈顶若是左括号，左括号优先级最低）
若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
右括号：将栈顶符号弹出并输出，直到匹配左括号
遍历结束：将栈中的所有符号弹出并输出
中缀转后缀
后缀 转 中缀
9 3 1 -3 *+ 10 2/ + 转变成中缀表达式
从左到右 数字直接入栈遇到符号，取栈顶元素 运算 ，将运算结果压入栈中遍历完全后，剩下的数字 是最终的运算结果。— 队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“”队头“，当线性表中没有元素时称为”空队“。特点：先进先出（FIFO）。
— 对于非空的队列，表头没有直接前驱，表尾没有直接后继，其他有且仅有一个直接前驱和一个直接后继。
— 只允许在表尾插入数据，在表头删除数据。
typedef int datatype ;
#define MAXSIZE 64 /* 定义队列的容量 */
typedef struct
{
datatype data[MAXSIZE]; /* 用数组作为队列的存储空间 */
int front , rear; /* 指示队头位置和队尾位置的下标 */
}seqqueue; /* 顺序队列类型定义 */
typedef int datatype ;
typedef struct node
{
datatype data; /* 数据域 */
struct node * next; /* 链接指针域 */
}linkqueue; /* 链栈类型定义 */
typedef struct
{
linkqueue * front; /* 指向队头结点的前一个节点的指针 */
linkqueue * rear; /* 指向队尾结点的指针*/
}_linkqueue_;
— — 例子： 操作系统和客服系统中，都是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。
队列是一种先进先出（First In First Out）的 线性表，简称 FIFO.允许插入的一端称为队尾，允许删除的一端称为队头。
队列在程序设计中用的是非常频繁的，比如键盘进行各种字母或者数字的输入，到显示器上如笔记本软件上的输出，其实都是队列的典型应用。
常用操作：
销毁队列清空队列进队列出队列获取队头元素获取队尾元素获取队列的长度创建一个队列
例题：
用循环队列实现如下功能：用户从键盘输入整数，程序将其入队，用户输入字母，程序将其队头元素出队，并在每一次出队和入队打印队列元素。
