Java栈和队列
栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组实现）用队列实现栈用栈来实现队列总结
栈的概念（Stack）
栈是常见的线性数据结构，栈的特点是以先进后出的形式，后进先出，先进后出，分为栈底和栈顶
栈应用于内存的分配，表达式求值，存储临时的数据和方法的调用等。
例如这把枪，第一发子弹是最后发射的，第一发子弹在栈底，而最新安装上去的子弹在栈的顶部，只有将上面的子弹打完（栈顶的数据走完），最后一发子弹才会射出
栈的实现
栈的实现是基于简单的数组形成的，我们可以将它想象成连续的数组，而栈的顺序是由后放到前放
模拟实现栈的方法:push（放入一个元素到栈中)
pop(提取栈顶的一个元素，并将在其栈中消除)
peek(查看栈顶的元素)
size(查看栈中的大小)
empty(栈中是否为空)
full(栈是否满了)
代码
import java.util.Arrays;public class MyStack implements IStack { private int[] elem; private int top;//数组的栈顶,以及数组栈中存放元素的数量 private static final int DEFAULT_CAPACITY = 10;//这里是初始容量 public MyStack() { elem = new int[DEFAULT_CAPACITY]; top = -1;//数组下标从0开始 } @Override public void push(int item) { if (full()) { //如果满了就扩容 elem = Arrays.copyOf(elem, 2 * elem.length); } elem[++top] = item; } @Override public int pop() throws RuntimeException { try { if (empty()) { throw new RuntimeException("栈为空"); } } catch (RuntimeException e) { e.printStackTrace(); } return elem[top--];//return返回后删除栈顶的元素 } @Override public int peek() { if (empty()) { throw new RuntimeException("栈为空"); } return elem[top];//返回栈顶元素 } @Override public int size() { return top+1;//去除数组0 } @Override public boolean empty() { return top == -1; } @Override public boolean full() { return top == elem.length;//count==当前的elem的总长度为true }}队列（Queue）
队列是由先进先出的线性数据结构，采用的是先进先出，后进后出，如果要插入元素的话就是从入队尾巴方向插入，而删除作为出队要在头尾删除。
队列的方法
模拟实现队列(双链表实现)
public class MyQueue implements IQueue{ static class Queue{ public int elem; public Queue next; public Queue prev; public Queue(int elem) { this.elem = elem; } } public Queue head; public Queue last; public int size=0; @Override public void offer(int val) { Queue queue = new Queue(val); if (this.head == null) { this.head = queue; this.last = queue; ++size; return; } this.last.next=queue; this.last.prev=this.head; this.last=last.next; ++size; } @Override public int poll() { if(this.head==null){ throw new RuntimeException("没有要丢掉的队列"); } Queue cur =this.head; if(this.head.next==null){ return -1; } this.head=this.head.next; this.head.prev=null; size--; return cur.elem; } @Override public int peek() { if(this.head!=null){ return this.head.elem; } return 0; } @Override public int size() { return size; }}循环队列（循环数组实现）
数组实现队列的循环需要引入一个公式（目前的下标值+1）%当前数组的长度
(index+1)%array.length,下标值从0开始少一个数，当index+1就是当前的总长度时，公式后的值一定为下标0。
private int[] array; private int front; private int rear; public MyCircularQueue(int k) { array=new int[k+1]; front=0;//初始位置 rear=0; } public boolean enQueue(int value) { //入列 if(isFull()){ //这里如果容量已经满了，需要先删除后在进行插入 return false; } array[rear]=value;//rear下标获取元素 rear=(rear+1)%array.length;//rear最终循环为0下标 return true; } public boolean deQueue() { //出列 if(isEmpty()){ //为空返回false return false; } front=(front+1)%array.length;//front只需要往后走 return true; } public int Front() { if(isEmpty()){ return -1; } return array[front]; } public int Rear() { if(isEmpty()){ return -1; } //这里三木操作符判断是否为0如果为0，将rear回退到最后一个位置，不为0则-1 int temp = (rear==0)?array.length-1:rear-1; return array[temp]; } public boolean isEmpty() { return front==rear; } public boolean isFull() { return (rear+1)%array.length==front; }}用队列实现栈
因为队列是先进先出的，而我们的栈是先进后出的，两种线性结构的关系是颠倒的，一个队列是不能完成的，我们需要两个队列互相工作来完成
辅助队列先获取数值，保证辅助队列是最后一个拿到值的，然后将主队列的值给到辅助队列，在交换两个队列的数值，因为队列关系先进先出，每一次最后一个值就是队列先出的数值
主队列不为空，将主队列的元素都poll出放到辅助栈中，使用一个tmp来将主队列（这里主队列已经遍历完）和辅助队列交换
Queue<Integer> q1;//主队列 Queue<Integer> q2;//辅助队列 public MyStack() { q1=new LinkedList<>();//构造方法 q2=new LinkedList<>(); } public void push(int x) { q2.offer(x); while(!q1.isEmpty()){//主队列不为空，则将主队列出列给到辅助队列 q2.offer(q1.poll()); } //走到这里主队列是为空 Queue tmp=q1; q1=q2; q2=tmp; //将两个队列交换 } public int pop() { return q1.poll(); } public int top() { return q1.peek(); } public boolean empty() { return q1.isEmpty(); }}用栈来实现队列
栈来实现队列，栈是先进后出的顺序，而队列是先进先出的顺序
将push都放到a栈中当我们peek或者是要删除的时候，我们都将a栈的元素pop给b栈，这样b栈已经有了我们的元素
但是我们还需要考虑的是丢掉元素后如果在一起添加元素到a栈呢，这里我们给一个条件，如果b的栈不为空时，我们仍然用b栈的队列
如果a为空，这两个栈都是空的说明没有元素直接返回-1，如果a不为空的话且b没有新的元素b继续捕获新的a栈中所有的元素
class MyQueue { Stack<Integer> A; Stack<Integer> B; public MyQueue() { A=new Stack<>(); B=new Stack<>(); } public void push(int x) { A.push(x); } public int pop() { int check=peek(); B.pop(); return check; } public int peek() { //先判断b是否是空的，如果不是空的直接返回，是空才可以往下走 if(!B.isEmpty())return B.peek(); //因为b还不是空的，所以不需要将a栈放到b中 if(A.isEmpty())return -1; while(!A.isEmpty()){ B.push(A.pop());//将所有的a放到b中 } return B.peek(); } public boolean empty() { return A.isEmpty()&&B.isEmpty(); //a和b都为空才为空 }}总结
栈分为栈顶和栈底，最先进的为栈底，最后进的为栈顶。
队列分为队头和队尾，最先进的为队头，最后进的为队尾。
