本文主要是介绍【数据结构】栈和队列相互实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
栈实现队列
思路
入队列
出队列
获取队头元素
队列实现栈
思路
入栈
出栈
获取栈顶元素
完整代码
栈实现队列
队列实现栈
栈实现队列
思路
栈的特点是 先进后出， 队列的特点是 先进新出，这就意味着我们无法通过一个栈来实现队列，那两个栈呢？
事实上，两个栈是可以实现队列的，stack1和stack2 思路如下：
入队列：先把所有元素都放到stack1中。
出队列：判断stack2是否为空
- 为空则把stack1中元素按照出栈顺序放到stack2中，同时返回stack2栈顶元素。
- 不为空则直接返回stack2栈顶元素。
定义基础变量
class MyQueue {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueue() {stack1 = new ArrayDeque<>();stack2 = new ArrayDeque<>();}
}入队列
offer方法
根据上面思路，新元素放在stack1中。
public void offer(int x) {stack1.push(x);}出队列
poll方法
在实现具体内容之前，我们要先判断两个栈是否都为空。
这里需要写个empty方法，判断条件是：两个栈是否为空。
public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}根据上面的思路，来完成出队列。
出队列：判断stack2是否为空
- 为空则把stack1中元素按照出栈顺序放到stack2中，同时返回stack2栈顶元素
- 不为空则直接返回stack2栈顶元素。
public int poll() {if(empty()){return -1;}if(stack2.isEmpty()){while(!stack1.isEmpty()){//第一个栈的所有元素 放到第二个栈当中stack2.push(stack1.pop());}}return stack2.pop();}获取队头元素
peek方法
思路和pop方法一样，不过返回的是stack2.peek();
public int peek() {if(empty()){return -1;}if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}
队列实现栈
思路
这里也是用两个队列实现栈，分别为qu1和qu2。
入栈：把元素放到不为空的队列中。如果都为空，放在qu1中。
出栈：把 不为空的队列 中的 size-1个元素放到另一个队列当中，最后剩下的元素模拟出栈。
定义基础变量
class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {this.qu1 = new LinkedList<>();this.qu2 = new LinkedList<>();}
}入栈
push方法
根据上面的思路：把元素放到不为空的队列中。如果都为空，放在qu1中。
//入栈public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}出栈
pop方法
根据上面的思路：把 不为空的队列 中的 size-1个元素放到另一个队列当中，最后剩下的元素模拟出栈。
同时还要考虑两个队列是否都为空，都为空将无法向下进行。所以可以写个empty方法来判断。
public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}pop方法完整如下：
//出栈public int pop() {if(empty()){return -1;}if(qu1.isEmpty()){int size = qu2.size();for(int i = 0; i < size - 1; i++){qu1.offer(qu2.poll());}return qu2.poll();}else{int size = qu1.size();for(int i = 0; i < size - 1; i++){qu2.offer(qu1.poll());}return qu1.poll();}}
获取栈顶元素
peek方法
获取栈顶元素和pop方法的思路相似， 不过这里不需要删除栈顶元素，而是把size给元素全部放到另一个队列中，同时需要定义一个中间值 val 来记录数据。
//获取栈顶元素public int top() {if(empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();int val = 0;for(int i = 0; i < size; i++){val = qu1.poll();qu2.offer(val);}return val;}else {int size = qu2.size();int val = 0;for(int i = 0; i < size; i++){val = qu2.poll();qu1.offer(val);}return val;} }完整代码
栈实现队列
class MyQueue {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueue() {stack1 = new ArrayDeque<>();stack2 = new ArrayDeque<>();}public void offer(int x) {stack1.push(x);}public int poll() {if(empty()){return -1;}if(stack2.isEmpty()){while(!stack1.isEmpty()){//第一个栈的所有元素 放到第二个栈当中stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}
队列实现栈
class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}public int pop() {if(empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();for(int i = 0; i < size-1; i++){qu2.offer(qu1.poll());}return qu1.poll();}else {int size = qu2.size();for(int i = 0; i < size-1; i++){qu1.offer(qu2.poll());}return qu2.poll();} }//在队列里面找中间值 存放移动的数据public int peek() {if(empty()){return -1;}if(!qu1.isEmpty()){int size = qu1.size();int val = 0;for(int i = 0; i < size; i++){val = qu1.poll();qu2.offer(val);}return val;}else {int size = qu2.size();int val = 0;for(int i = 0; i < size; i++){val = qu2.poll();qu1.offer(val);}return val;} }public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}
这篇关于【数据结构】栈和队列相互实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
