栈：先进后出 队列：先进先出
两个栈实现一个队列：
思路：先将数据存到第一个栈里，再将第一个栈里的元素全部出栈到第二个栈，第二个栈出栈，即可达到先进先出
源码：
class Queue{ //用的jdk自带的栈 private Stack s1=new Stack<>(); private Stack s2=new Stack<>(); public void offer(E val){ //入队 s1.push(val); } public E poll() { //出队 while (s2.empty()){ while (!s1.empty()){ s2.push(s1.peek()); s1.pop(); } } E val=s2.peek(); s2.pop(); //获取出队元素后，再将s2里面的元素放入s1里面。 while (!s2.empty()){ s1.push(s2.pop()); } return val; } public E peek(){//查看对头元素 while (s2.empty()){ while (!s1.empty()){ s2.push(s1.peek()); s1.pop(); } } E val=s2.peek(); //获取出队元素后，再将s2里面的元素放入s1里面。 while (!s2.empty()){ s1.push(s2.pop()); } return val; } public boolean empty(){ //判断队是否为空 return s1.empty(); } }
测试：
public static void main(String[] args) { Queue queue = new Queue<>(); Random rand = new Random(); for (int i = 0; i < 5; i++) { int data = rand.nextInt(100); System.out.print(data + " "); queue.offer(data); } System.out.println(); System.out.println("出队："); while (!queue.empty()) { System.out.print(queue.poll()+" "); } } 运行结果：
79 67 45 73 59 出队：79 67 45 73 59
两个队列实现一个栈：
思路：先将数据存到第一个队列里面，然后数据出队一直出队到地二个队列里面，直到第一个队列里面剩余一个数据，这个时候出队 即可达到先进后出的特性
源码：
自定义的一个循环队列：
class Queue{ // 存储队列元素的数组 private E[] que; // 表示队头的位置 private int front; // 表示队尾的位置 private int rear; public E[] getQue() { return que; } public int getFront() { return front; } public int getRear() { return rear; } /** * 默认构造队列，初始大小是10 */ public Queue(){ this(10); } /** * 用户可以指定队列的大小size * @param size */ public Queue(int size){ this.que = (E[])new Object[size]; this.front = this.rear = 0; } /** * 入队操作 * @param val */ public void offer(E val){ if(full()){ // 扩容 E[] newQue = Arrays.copyOf(this.que, this.que.length*2); int index = 0; for(int i=this.front; i != this.rear; i=(i+1)%this.que.length){ newQue[index++] = this.que[i]; } this.front = 0; this.rear = index; this.que = newQue; } this.que[this.rear] = val; this.rear = (this.rear+1)%this.que.length; } /** * 出队操作，并把出队的元素的值返回 */ public E poll(){ if(empty()){ return null; } E front = this.que[this.front]; this.front = (this.front+1)%this.que.length; return front; } /** * 查看队头元素 * @return */ public E peek(){ if(empty()){ return null; } return this.que[this.front]; } /** * 判断队满 * @return */ public boolean full(){ return (this.rear+1)%this.que.length == this.front; } /** * 判断队空 * @return */ public boolean empty(){ return this.rear == this.front; }}
两个队列实现一个栈：
class SeqStack{ private Queue que1; // 存放栈的元素 private Queue que2; // 做一个辅助操作 public SeqStack(){ this.que1 = new Queue<>(); this.que2 = new Queue<>(); } public SeqStack(int size){ this.que1 = new Queue<>(size); this.que2 = new Queue<>(size); } public void push(E val){ this.que1.offer(val); } public E pop(){ // 从que1出队，把最后一个出队的元素返回 E data = null; /** * 把que1里面的所有元素出队，放入que2里面， * 然后把que1最后一个出队的元素直接返回，不用放入que2 */ while(!this.que1.empty()){ data = this.que1.poll(); if(this.que1.empty()){ break; } this.que2.offer(data); } // 获取该出栈的元素以后，再把que2的元素再放入que1里面 while(!this.que2.empty()){ this.que1.offer(this.que2.poll()); } return data; } public E top(){ // 从que1出队，把最后一个出队的元素返回 E data = null; while(!this.que1.empty()){ data = this.que1.poll(); this.que2.offer(data); } // 获取该出栈的元素以后，再把que2的元素再放入que1里面 while(!this.que2.empty()){ this.que1.offer(this.que2.poll()); } return data; } public boolean full(){ return this.que1.full(); } public boolean empty(){ return this.que1.empty(); }}
测试:
public static void main(String[] args) { SeqStack seqStack=new SeqStack<>(); Random rand = new Random(); for (int i = 0; i < 5; i++) { int data = rand.nextInt(100); System.out.print(data + " "); seqStack.push(data); } System.out.println(); System.out.println("出栈："); while (!seqStack.empty()) { System.out.print(seqStack.pop()+" "); } } 运行结果：
9 3 7 83 32 出栈：32 83 7 3 9