栈和队列

栈和队列

栈是一种先进后出 只能在表尾进行插入和删除的线性表，我们把允许插入和删除的一端叫做栈顶，另一端叫做栈底。不含任何数据元素的叫做空栈。LIFO结构。

栈不一定是顺序存储结构的线性表，栈也可能是链式存储结构的线性表，简称链栈。

1.2.3 入栈顺序，出栈的顺序一定是3，2，1吗？ 很显然不是。因为栈只对出栈和入栈的位置就行了约束，即表尾(栈顶)但是并没有对出栈和入栈的时间进行约束。

栈由于是一种特殊的线性表，它也分为顺序存储和链式存储。

• 顺序栈。类比数组，数组的尾巴模拟栈顶
• 链栈。 去掉头结点，虽然头结点不是必须的，但是常规都有，头指针和栈顶指针合二为一。这样的话，原来判断空栈的条件是头指针的执行为NULL。变为栈顶指针top = NULL

 ` 入栈  s = (Node*)malloc(sizeof(Node)); s->next = S->top; S->top = s;  S->count ++; return OK`

 ` 出栈  p = S->top; S->top = p->next ;  free(q);S->Count -- ; `

共享栈

两个相同类型的栈，通过横过来，让一个的栈底变为数组下标的0处，另外一个变为数组下标的末端即n-1处。这样如果两个栈增加元素，就是两端点向中心延伸。    

栈的一个主要应用：递归

菲波那切数列

func Fbi(number:Int)->Int{ if number<2{ return number == 0 ? 0 : 1 return Fbi(number- 1) + Fbi(number -2 ) } }

逆波兰表示

后缀表达式的用法，遇到数字就入栈，遇到运算符就出栈，进行运算。

队列

队列是一种特殊的线性表。

链队列插入元素s

s->next = NULL

Q->rear->next = s

Q->rear = s