【数据结构】栈和队列相互实现

本文主要是介绍【数据结构】栈和队列相互实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

栈实现队列

思路

入队列

出队列

获取队头元素

队列实现栈

思路

入栈

出栈

 获取栈顶元素

完整代码

栈实现队列

队列实现栈

---

栈实现队列

思路

栈的特点是 先进后出， 队列的特点是 先进新出，这就意味着我们无法通过一个栈来实现队列，那两个栈呢？

事实上，两个栈是可以实现队列的，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();}
}

这篇关于【数据结构】栈和队列相互实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---