玩转数据结构（十一）两个队列实现栈

逃离我推掉我的手 2022-05-21 09:09 132阅读 0赞

### 1、思路分析 ###

*  现在有两个队列，queue1和queue2; 当要实现入栈操作时，将数据放入到不为空的队列中，要是两个队列都为空，默认先放入queue1队列中。如下图：a、b、c、d都放入到queue1队列中。

### ![70][] ###

*  当要实现出栈操作时，将不为空的队列中的数据放入到另一个为空的队列中，直至剩下一个；而那一个数据就是要出队的数据。如下图：将queue1中的a、b、c依次转移到queue2中，只剩下d，而d就是要出队的数据，相当于栈顶数据。依次反复即可实现弹栈操作。

![70 1][]

### 2、代码实现 ###

import java.util.ArrayDeque;
    import java.util.Queue;
    /**
     * 两个队列实现栈
     * @param <E>
     */
    public class QueueStack<E>{
        private Queue<E> queue1 = new ArrayDeque<E>();
        private Queue<E> queue2 = new ArrayDeque<E>();
        public boolean isEmpty() {
            return queue1.isEmpty() && queue2.isEmpty();
        }
        /**
         * 入队
         * @param e
         */
        public void enqueue(E e) {
            //若两个队列为空，则将数据优先放入queue1中
            if(isEmpty()) {
                queue1.add(e);
                return;
            }
            //若queue2为空，queue1不为空，将数据放入queue1
            if(queue2.isEmpty()) {
                queue1.add(e);
                return;
            }
            //若queue1为空，queue2不为空，将数据放入queue2
            if(queue1.isEmpty()) {
                queue2.add(e);
                return;
            }
        }
        /**
         * 出队
         * @return E
         */
        public E dequeue() {
            if(isEmpty()) {
                throw new RuntimeException("error! stack is empty!");
            }
            if(queue2.isEmpty()) {
                //将queue1中的数据放入到queue2，直至剩下一个数据，返回
                while(queue1.size() > 1) {
                    queue2.add(queue1.poll());
                }
                return queue1.poll();
            }
            if(queue1.isEmpty()) {
                //将queue2中的数据放入到queue1，直至剩下一个数据，返回
                while(queue2.size() > 1) {
                    queue1.add(queue2.poll());
                }
                return queue2.poll();
            }
            return null;
        }
    }

### 3、测试代码 ###

###  ###

public static void main(String[] args) { QueueStack<Integer> stackQueue = new QueueStack<Integer>(); for (int i = 0; i < 10; i++) { System.out.println("入栈：" + i); stackQueue.enqueue(i); if(i % 3 == 2) { System.out.println("出栈：" + stackQueue.dequeue()); } } while(!stackQueue.isEmpty()) { System.out.println("出栈：" + stackQueue.dequeue()); } }

4、结果

入栈：0
    入栈：1
    入栈：2
    出栈：2
    入栈：3
    入栈：4
    入栈：5
    出栈：5
    入栈：6
    入栈：7
    入栈：8
    出栈：8
    入栈：9
    出栈：9
    出栈：7
    出栈：6
    出栈：4
    出栈：3
    出栈：1
    出栈：0

[70]: /images/20220521/104177e2afc44744a5ddf1be87fb0733.png
[70 1]: /images/20220521/8af146c9db024d5b98e382b905201cf1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】队列OJ：两个栈实现队列、两个队列实现栈、实现最小值栈

目录一、两个栈实现队列二、两个队列实现栈三、最小值栈----可获取栈的最小值 -------------------- 一、两个栈实现队列栈的特点是先进

梦里梦外;/ 2023年09月27日 13:26/ 0 赞/ 91 阅读

相关数据结构 - 两个栈实现一个队列

实现原理栈的特性是先进后出，队列的特性是先进先出。那么，我们使用两个栈，对同一个元素进行先进后出两次栈就形成了先进先出的顺序。即一个元素需要入栈两次，才能被取出来。

Love The Way You Lie/ 2022年12月26日 04:50/ 0 赞/ 128 阅读

相关回顾数据结构——使用两个栈实现一个队列和用两个队列实现一个栈

今天下午有面试，早上先来无事，写一篇博客压压惊，由于时间不多，先写个思路和实现代码，图后面有时间补上。使用两个栈实现一个队列核心思想：因为栈是先进后出的，所以自身带

男娘i/ 2022年11月28日 13:56/ 0 赞/ 157 阅读

相关 [数据结构][Python]用两个栈实现队列与用两个队列实现栈

题目用栈模拟一个队列，实现入队、出队解决方案让元素1入队 <table> <thead> <tr> <th>栈A</th> <t

àì夳堔傛蜴生んèń/ 2022年10月02日 15:55/ 0 赞/ 192 阅读

相关玩转数据结构（十一）两个队列实现栈

1、思路分析现在有两个队列，queue1和queue2; 当要实现入栈操作时，将数据放入到不为空的队列中，要是两个队列都为空，默认先放入queue1队列中。如下图

逃离我推掉我的手/ 2022年05月21日 09:09/ 0 赞/ 133 阅读

相关玩转数据结构（十）两个栈实现队列

栈是一种先进后出的数据结构，而队列是一种先进先出的数据结构，如何使用两个栈实现一个队列呢？这也是面试中常问的问题。 1、思路分析先来看一幅图： ![70][]

末蓝、/ 2022年05月21日 09:08/ 0 赞/ 148 阅读

相关 python队列和栈操作，两个栈实现队列，两个队列实现栈

参考：[http://docs.python.org/2/tutorial/datastructures.html\more-on-lists的官方代码][http_docs.

迈不过友情╰/ 2022年05月06日 11:30/ 0 赞/ 245 阅读

相关数据结构【队列】（十二）：队列实现栈

问题描述使用两个队列实现栈，要满足后入先出，比如输入：1 2 3 4 5，那么输出就应该是：5 4 3 2 1 解题思路使用两个队列，分别是数据队列和辅助队里

淡淡的烟草味﹌/ 2022年02月28日 04:16/ 0 赞/ 257 阅读

相关数据结构【栈】（十）：使用栈实现队列

问题描述使用两个栈模拟队列，比如输入：1 2 3 4，则要求输出仍是：1 2 3 4 解题思路 1、有两个栈，一个用来存放入队数据（数据栈），一个用来辅助（辅助

今天药忘吃喽~/ 2022年02月28日 03:34/ 0 赞/ 274 阅读

相关两个栈实现队列和两个队列实现栈 Java

public class Test07 { / 用两个栈实现一个队列（先进后出）队列的声明如下：实现它的两个函

àì夳堔傛蜴生んèń/ 2021年11月16日 06:08/ 0 赞/ 352 阅读