结构介绍
栈(Stack):栈是一种很常见的数据结构，特点是先进后出(FILO, First In Last Out)，意思是先进来的元素后出去，后进来的元素先出去。类似于我们进电梯一样，先进去的人总是被挤在里面，然后最后才能出去。
队列(Queue):队列也是一种很常见的数据结构，特点是先进后出(FIFO, First In First Out)，意思是先进来的元素先出去，后进来的元素后出去。类似于我们排队打饭一样，先进去排队的人总是会先打饭。
栈
源码解读
可以发现Stack是一个类，继承自Vector，Vector是一个线程安全的可变数组，和ArrayList类似，底层是用数组实现的。
Vector对外提供了很多方法，类似于前面介绍的ArrayList。但是Stack本质上只对外提供push、pop、peek、empty方法。虽然可以通过Stack对象访问父类Vector的public方法，但是是不推荐这么使用的。
- push方法：向栈中添加元素，源码中直接调用Vector的addElement方法
- pop方法：从栈中移除元素，源码中获取栈的大小，然后移走栈中的最后一个元素
- peek方法：查看栈顶元素，源码中获取栈的大小，然后查看最后一个元素
- empty方法：直接返回栈的大小
队列
源码解读
我们发现Java中的栈和队列并不等价，栈是一个实现类，而队列是一个接口。
我们在创建时，常常创建实现类LinkedList的实例对象。追溯LinkedList类，可以发现实现接口Deque，Deque是一个双端队列接口，Deque又继承自Queue，因此LinkedList也是实现Queue接口的。
Queue和Stack类似，虽然可以通过父类访问很多方法，但是本质上对外只提供add、offer、remove、poll、element、peek方法
- add方法：向队尾添加元素
- offer方法：向队尾添加元素，在LinkedList实现中会调用add方法
- remove方法：从队头删除元素
- poll方法：从队头删除元素，在LinkedList中本质上和remove相同
- element方法：获取队头元素
- peek方法：获取队头元素，在LinkedList中本质上和element相同
实现
因为栈和队列中的元素都是会动态添加的，而且栈在操作中，总是操作尾部(插入、删除)，队列在操作中总是操作头部(删除)或尾部(插入)。所以使用双向链表实现最为简单。
在前面已经介绍过链表，其中我们只用addLast(push)、removeLast(pop)、getLast(peek)、size(类似empty)就可以模拟栈，只用addLast(add、offer)、removeFirst(remove、poll)、getFirst(element、peek)方法就是队列。这里不过多赘述。
有的面试官可能会要求使用数组实现，其实是类似的
栈就用一个标志位top表示栈顶是哪一个索引，然后入栈top++，出栈top–，然后考虑一下扩容即可。
队列麻烦一些，需要用一个rear表示队头，tail表示队尾。入队tail++，出队rear++，注意要使用循环队列节省空间，即入队时如果到达数组尾部，且头部因为出队有剩余空间(rear > 0)，则可以放在队头。
这里有一个知识点，就是什么时候表示需要扩容了？假设刚开始队头和队尾都指向0，那么当元素满的时候、或者队空的时候，队头和队尾都会指向同一个数。可以空出一个空间表示是否已经队满，或者用一个额外的变量表示是否已经队满。
小结
栈和队列的实现方式并不难，现在的面试也不会手撕这么简单的数据结构了。基本上最简单的也是Trie树、堆、set、map等，后面会一一为小伙伴们手撕。