前言知识：
栈（Stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。队列（Queue）也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作，和栈一样，队列 的部分操作也会受到限制。栈 的特点是先进后出（FILO），队列 则是先进先出（FIFO），本文将会通过顺序存储的方式模拟实现 栈，以及链式存储的方式模拟实现 队列，两种数据结构都比较简单，一起来看看吧！
一： 栈
在讲栈之前我们必须得了解一些基本概念：
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则 。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
图示：
这就满足我们先前的概念，先进来的元素后出去，后进来的元素先出去。
比如许多生活中的例子，抗日剧中的三八大盖的子弹也是一种栈。
数组模拟栈
首先介绍 栈 的实现，栈 非常适合通过 顺序表 来模拟实现，因为 顺序表 尾插、尾删的复杂度是O(1)，并且 栈 的插入、删除都是在 栈顶 完成的，因此我们可以去除 顺序表 的部分功能，这样就可以得到一个 栈。
此时，入栈就相当于顺序表尾插，出栈就相当于顺序表的尾删。
芝士代码：
class MyStack { public int[] elem; public int usedSize;//记录使用的容量 public MyStack() { this.elem = new int[10]; } }
接下来就是对栈的实现的，在实现之前我们还得看看jdk中所给的集合。
我们在最开始讲数据结构的时候就看过 “ 集合的框架 ” 我们再来看看关于栈的部分：
现在在正式的开发过程中已经很少 Vector 更多的使用Stack 创建栈，我们来看看stack中有那些方法。
可以看到它的主要方法其实并不是很多，并且默认的构造方法还是空的，那么意味着我们需要模仿的方法只有五个。
入栈（push）： 判断是否栈已满，已满后进行扩容；每次使用完一个栈空间usedSize向后移动一位。
出栈（pop）：
判断是否为空，如果为空则抛出异常；否则弹出栈顶元素，并且usedSize--。
图示理解：
代码：
获取栈顶元素（peek）：
类似于出栈，但是下标位置不发生改变。
判断栈是否为空（isEmpty）：
判断栈是否已满（isFull）：
因为扩容实在内部扩容的，所以我将其权限置为private。
完整代码：
import java.util.Arrays; import java.util.Stack; public class MyStack { public int[] elem; public int usedSize; public MyStack() { this.elem = new int[10]; } //入栈 public void push(int val) { if (isFull()) { elem = Arrays.copyOf(elem, (int) (1.5*elem.length)); } elem[usedSize++] = val; } //出栈 public int pop() { if (isEmpty()) { throw new EmptyException("是个空栈"); } /*int val = elem[usedSize-1]; usedSize--; return val;*/ /* usedSize--; return elem[usedSize];*/ return elem[--usedSize]; } //获取栈顶元素 public int peek() { if ( isEmpty() ) { throw new EmptyException("是个空栈"); } return elem[usedSize - 1]; } //判断是否为空 public boolean isEmpty() { return usedSize == 0; } //判断是否已满 private boolean isFull() { // 判断是否需要扩容 return usedSize == elem.length; } }
异常：
public class EmptyException extends RuntimeException{ public EmptyException() { } public EmptyException(String message) { super(message); } }
二： 队列
同样，在了解队列之前我们先来了解队列的概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
frist in
first out
我们再来看看在jdk给出的集合：
Queue是个接口，底层是通过链表实现的。
我们可以通过栈，顺序链或者链表实现，还可以通过PriorityQueue实现，这个后面单独介绍。
我们用LinkedList举例，它主要有如下几种主要方法：
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
也可以在集合中看到所提供的方法：
接下来开始写代码：
单链表模拟队列：
public class MyQueue { //单链表模拟实现 static class Node { public int val; public Node next; public Node(int val) { this.val = val; } } public Node head; public Node last; public int usedSize; }
我们需要设置一个usedSize来记录实际的队列长度，head作为队头，last作为队尾。
那么我们的判断队列是否为空就很好判断：
另外我们在多添加一个方法，用来获取实际队列长度：
有了Empty方法peek方法就很好写了：
判断是否为空，为空抛出自定义异常，不为空直接返回队头的val值。
入队：
入队比较复杂，第一步需要确定是否为空队，如下图：
是为空队就需要head、last 均指向该元素，并且usedSize ++ 。
不为空那么lsat就需要先链接新入队的元素，在last指向新入队的元素，并且usedSize ++。
出队：
出队也很好理解：
同样分情况考虑，如果为空抛出异常，不为空正常出队
用一个临时变量保存val保留head的值，head指向head.next，并且usedSize -- ；最终返回val。
自定义异常：
完整代码：
public class EmptyException extends RuntimeException{ public EmptyException() { } public EmptyException(String message) { super(message); } }
public class MyQueue { //单链表模拟实现 static class Node { public int val; public Node next; public Node(int val) { this.val = val; } } public Node head; public Node last; public int usedSize; public void offer(int val) { //入队 Node node = new Node(val); if (Empty()) { head = node; } else { last.next = node; } last = node; usedSize++; } public int poll() { //出队 if (Empty()) { throw new EmptyException("空队"); } int val = head.val; head = head.next; if (head == null) { //如果只有一个结点那么last也要制空 last = null; } usedSize--; return val; } public int peek() { //peek if (Empty()) { throw new EmptyException("空队"); } return head.val; } public boolean Empty() { //判断空队 return usedSize == 0; } public int getUsedSize() { return usedSize; } }
当然用数组模拟大致思路是很类似的，但是有一点不同。
数组模拟队列：
用单链表我们用head记录队头，last记录队尾这很容易找到队头和队尾，我们用数组模拟队，front作为队头，rear作为队尾。
因为队列的第一个元素并非就存储在下标为0的位置处，那么我们就无法直接通过下标去访问队头，所以无法用下标访问的方式去获取元素队头和队尾。
同时还存在另一个问题，如果我们的队头的下标是数组的尾部，我们如何继续存储元素？
这是我们急迫需要解决的问题。
举例：
此时我们元素5需要入队的位置在下标为0处，怎么从array.length处跑到0处呢？
我们将队头和队尾加上：
按照单链表的形势，每次添加一个元素就++一次，明显不再使用于数组形式，我们需要改变记录方法；这里有个很好的想法：
这个问题的唯一的困难点在于rear处于array.length处。
按照上图，每次 rear 都需要重新赋值，rear 就等于上一次添加元素的下标，每次下标加一再取模数组的长度，如果位于array.length 处取模的值就为0，于是回到了数组开头。
同样出队列时也是用同样的思路去思考front 的值：
具体的我就不再一步步介绍，具体的可以参考我的代码：
完整代码：
public class MyQueue { //循环队列 //用数组模拟 private int[] elem; private int usedSize; private int front;//表示队列的头 private int rear;//表示队列的尾 public MyQueue(int k) { this.elem = new int[k + 1]; } /** * 入队 * @param val 值 * @return */ public boolean enQueue(int val) { if (isFull()) { return false; } elem[rear] = val; rear = (rear+1) % elem.length; //这里不能使用rear++；因为是个循环，rear有可能是最后数组的最后位置 usedSize++; return true; } /** * 出队列 * @return */ public boolean deQueue() { if (Empty()) { return false; } front = (front+1) % elem.length; usedSize--; //这里不能使用front++；因为是个循环，front有可能是最后数组的最后位置 return true; } /** * 得到队头元素 * @return */ public int getFront() { if (Empty()) { return -1; } return elem[front]; } /** * 得到队尾元素 * @return */ public int getRear() { if (Empty()) { return -1; } int index = (rear == 0) ? elem.length-1 : rear-1;//?? return elem[index]; } public boolean isFull() { //判断队是否满了 return (rear + 1) % elem.length == front; } public boolean Empty() { //判断空队 return rear == front; } }
还可以添加一个获取队列实际长度，代码中usedSize就是记录实际长度。
