本文章只针对知识进行概括性梳理，相关代码详情可以咕咕哥
栈的引入模型：手枪子弹的压堂（出栈），装子弹（进栈），递归的实现，回溯的过程都可以看成栈，网页前进后退键
栈的定义
是限定仅在表尾进行插入和删除操作的线性表，又被称为后进先出的线性表（LIFO）
允许插入或者删除的一段叫栈顶，另外一段叫栈底
栈的插入叫进栈，压栈，入栈
栈的删除操作叫出栈，弹栈
进出栈的顺序
第一个进栈的元素不一定最后一个出栈
eg: 1进，1出，2进，2出，3进，3出
栈的ADT
Data
同线性表
Operation
InitStack(S)
DestoryStack(S)
ClearStack(S)
StackEmpty(S)
GetTop(S,e)
Push(S,e)
Pop(S,*e)
StackLength(S)
因为本身栈是一个线性表，所以ADT对与线性表也适用。。。
栈的顺序储蓄结构
参考线性表的顺序储存结构，top指针永远指向栈顶。
出入栈时间复杂度为O（1）
两栈共享
前提：两栈必须具有相同的类型，不然问题会变得更大。
共享原理：
一个从下标0处，另一个栈为数组的末端，相当于栈顶向中间点延伸当top1+1=top2的时候该共享数组就达到满栈。
栈的链式储存结构
参考线性表的链式储存结构。
注意的是上章讲的，插入时候应该先让新节点创建连接，再修改原有指针（这里指的top），
删除则相反。
栈的四则运算
- 通过栈让中缀表达式改为后缀表达式，栈存的是字符。遇到后括号，或者优先级高于栈内的符号，谈谈谈出栈！
- 后缀表达式计算结构，数字入栈，遇到符号就让栈顶的两个数字进行运算，从而得到正确的结构。
队列
队列是一种先进先出的线性表，FIFO，
ADT
DATA
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
InitQueue(Q)
DestoryQueue(Q)
clearQueue(Q)
QueueEmpty(Q)
GetHead(Q)
EnQueue(Q)
DeQueue(Q，e）
QueueLength(Q)
循环队列
队列顺序储存的不足，因为和线性表的顺序储存结构完全相同，这就导致了一件坏事情，每一次的插入和删除就得让后续队列遍历更换位置一次。但是循环队列很好的解决了这一点。
假溢出：数组尾部的已满，但是头部还有空余。
为了解决假溢出，我们把头尾相接的顺序储存结构称为循环队列
当出现及一处的情况时候，尾指针就会回到头部
判断是否为空：当front(头指针)等于rear（尾指针）
判断是否满 ：
- 设置个flag 让 front=rear 而且flag =0 为空，flag =1 为满
- 保留一个元素空间，也就是说公式满足：（rear + 1)%QueueSize == front 时候队列是满的。
- 计算改队列长度通用公式（rear - front + QueueSize）%QueueSize
队列的链式储存结构
队列的链式储存结构就是单链表，只不过它只能尾进头出，我们把它称为链队列。
空队列时：front和rear都会指向头结点。
插入时候和链表一样的注意：：：：
出队的时候如果删除最后一个元素时候除了头结点时候，应该将rear指向头结点。
网友评论