栈

定义：栈是限定在表尾进行进行插入和删除操作的线性表
特点：允许插入和删除的一端叫做栈顶，另一端叫做栈底，不含任何元素的栈称为空栈，栈又称为后进先出（last-in，first-out，LIFO）面试的时候回LIFO是什么。
image.png
实现方式
1、如果用数组实现，栈底是下标为0的一端

image.png

第一个图栈里有两个元素，而栈顶在1这个位置，有一个指针指向，第二个图是一个空栈
第三个图是一个满栈，也就是说数组的大小是固定的，已经存储满了

2、如果用链表存储

image.png

如图：an就是链表的尾，a1是栈底，链表大家都知道插入和删除特别快，但是查找很慢。而栈只是从栈顶删除元素，也就是说是尾删，这样更好

3、我们看一下链栈的出入操作，里面的结点是怎么变化的

image.png

上面这个图是链表的入栈操作：就是s.next=top;top=s; count++ （很简单，就是将插入的结点的next指向top ，然后将s赋值给top，在将大小++）

image.png

上面这个图是链表的出栈操作：就是将p.next=top,count--(就是将头指针指向p的next,然后count-- 如果是在c语言中还要释放p结点 free(p))

栈的经典应用(逆波兰表达式法)

1、我们知道如果我们要算一个四则运算的值我们知道先算括号里面的，然后算* 和除再算+ -，但是计算机不知道，那么计算机是怎么样来算的，我们来看看：

比如：这样的一个式子9+(3-1)*3+10/2 那么计算机吧这个式子会做这样的变换：9 3 1 - 1 * + 10 / 2 +
2、思路

数字输出，运算符进栈，括号匹配出栈，栈顶优先级出栈

a、首先使用两个栈一个是s1 一个是s2 s1 是用来临时存储运算符的， s2 是用来存放输入的逆波兰表达式的，
b、从中缀表达式的最左端开始，逐个读取每一个字符，如果操作数，则压入s2，如果是左括号，则压入s1，如果为右括号，则将s1中的运算符依次取出并且压入s2，直到遇到左括号，但是该左括号出栈但不压入s2，如果为操作符，判断s1是否为空，如果为空则将它压入s2，如果扫描到的比栈顶的元素的优先级大将它入栈，如果扫描到的比小于栈顶或者等于栈顶的优先级小，直到扫描到的元素大于栈顶的元素（注意这里是一个循环），然后判断s1里面如果还有运算符则一一出栈压入到s2中
c、然后这个时候所有的数据全部在s2中，这个时候从的将s2逆置，从栈底开始取元素，开始扫描，如果扫描到的是一个运算符，则将他之前扫描到的两个元素做运算，得到存储到该位置，一直扫描，直到栈里还剩一个元素，就得到结果。

3、这个逆波兰表达式的实现我在下一篇会附上源码（并且包括使用数组自定义Stack）

队列

定义：是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
特点：插入的一端叫做队尾，删除的一端叫做队头

image.png
队列的存储结构

1、队列的顺序存储

出队复杂度比较高，时间复杂度尾O(n),比较容易出现假溢出

image.png
还有一种是头尾相连的顺序存储结构称为循环队列（这个就不说了）

2、队列的链式存储结构

队列的链式存储结构其实就是线性表的单链表 (这个在第一篇中手写单链表实现),只不过只能尾进头出

image.png

3、队列的变形记(双端队列Deque)

Deqeue是一种具有队列和栈的数据结构，双端队列中的元素，从两端弹出，删除和插入操作在表的两端进行 image.png
应用场景：LinkedList/ArrDeque/LinkedBlockingDeque(阻塞的双向队列)