栈和队列都来自线性表数据结构，都是“操作受限”的线性表
栈
1.定义：是限制在表的一端进行插入和删除操作的线性表。后进先出LIFO线性表
2. 注意点：
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Base)：是固定端，又称为表头
栈——顺序存储
定义：栈的顺序存储结构，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。
栈——动态顺序存储
1. 注意点：
◆ 用top=bottom作为栈空的标记
◆ 结点进栈时，首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置
◆ 结点出栈时，首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出
◆ 若栈的数组有Maxsize个元素，则top=Maxsize时栈满
2. 结构体定义：
typedef struct SqStack { ElemType *bottom; /* 栈不存在时值为NULL */ ElemType *top; /* 栈顶指针 */ int stacksize ; /* 当前已分配空间，以元素为单位 */ }SqStack;
3. 追加存储空间操作：
// 在压栈操作中 if(S.top-S.bottom>=S. stacksize-1){ // 栈满，根据存储空间增量，追加存储空间 S.bottom=(ElemType *)realloc((S.STACKINCREMENT+STACK_SIZE) *sizeof(ElemType)); if ( !S.bottom) return ERROR; // 存储空间追增后，栈顶指针的位置 S.top=S.bottom + S. stacksize; S.stacksize+=STACKINCREMENT; } // 空间追赠完毕后，对于压栈操作，直接赋值元素到 S.top 即可 *S.top=e; S.top++;
栈——静态顺序存储
1. 注意点：
◆ 用top=0表示栈空，每次top指向栈顶在数组中的存储位置
◆ 结点进栈时，首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。
◆ 结点出栈时，首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。
◆ 若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满
2.结构体定义：
typedef struct SqStack{ ElemType stack_array[MAX_STACK_SIZE] ; int top,bottom; }SqStack;
3. 上下溢：
当栈满时做进栈，定产生溢出，简称“上溢” —— 上溢是一种出错状态
当栈空时做退栈，将产生溢出，简称“下溢” —— 下溢可能是正常现象
栈——链序存储
1. 定义：链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针
2. 注意点：
◆ top == NULL
◆ top 所指，即栈顶元素
3. 栈的应用：
◆ 进值转换
◆ 括号匹配
◆ 递归调用：
（1）有效的递归调用函数应包括两部分：递推规则 终止条件
（2）递归：一个函数直接或间接地调用自己本身
队列
1.定义：队列是运算受限的线性表。是一种先进先出FIFO的线性表。只允许在表的一端进行插入，而在另一端进行删除。
① 队首(front) ：允许进行删除的一端称为队首。
② 队尾(rear) ：允许进行插入的一端称为队尾
队列——顺序存储结构
1. 定义：利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素，称为顺序队列
2. 结构体定义：
typedef struct queue{ ElemType Queue_array[MAX_QUEUE_SIZE]; int front; int rear; }SqQueue;
3. 注意点：
◆ 初始化：front=rear=0。◆ 入队：将新元素插入rear所指的位置，然后rear加1。
◆ 出队：删去front所指的元素，然后加1并返回被删元素。◆ 队空：front=rear。◆ 队满：rear=MAX_QUEUE_SIZE-1或front=rear
4. 假溢出：
在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用
循环队列
1.避免“假溢出”思想：
当队首、队尾指针指向上界(MAX_QUEUE_SIZE-1)时，其加1操作的结果是指向向量的下界0
2. 用模运算简化操作：
i=(i+1)%MAX_QUEUE_SIZE
◆ i代表队首 (front)或队尾 (rear)
3. 注意点：
◆ rear所指的单元始终为空
◆ 循环队列空：front=rear
◆ 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front
◆ 入队：先赋值，再队尾指针移动rear=(rear+1)% MAX_QUEUE_SIZE
◆ 出队：先取值，再队首指针移动 front=(front+1)% MAX_QUEUE_SIZE
队列——链序存储结构
1.定义：链队列，是限制仅在表头进行删除操作和表尾进行插入操作的单链表
2.结构体定义：
（1）数据元素结点：
typedef struct Qnode{ ElemType data; struct Qnode *next; }QNode;
（2）指针结点：
typedef struct link_queue{ QNode *front , *rear; }Link_Queue;
