Java的栈与队列以及代码实现

栈的概念（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开始}@Overridepublic void push(int item) {if (full()) {//如果满了就扩容elem = Arrays.copyOf(elem, 2 * elem.length);}elem[++top] = item;}@Overridepublic int pop() throws RuntimeException {try {if (empty()) {throw new RuntimeException("栈为空");}} catch (RuntimeException e) {e.printStackTrace();}return elem[top--];//return返回后删除栈顶的元素}@Overridepublic int peek() {if (empty()) {throw new RuntimeException("栈为空");}return elem[top];//返回栈顶元素}@Overridepublic int size() {return top+1;//去除数组0}@Overridepublic boolean empty() {return top == -1;}@Overridepublic 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;@Overridepublic 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;}@Overridepublic 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;}@Overridepublic int peek() {if(this.head!=null){return this.head.elem;}return 0;}@Overridepublic 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()){//为空返回falsereturn 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则-1int 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都为空才为空}
}

总结

栈分为栈顶和栈底，最先进的为栈底，最后进的为栈顶。
队列分为队头和队尾，最先进的为队头，最后进的为队尾。