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

末蓝、 2022-05-21 09:08 207阅读 0赞

栈是一种先进后出的数据结构，而队列是一种先进先出的数据结构，如何使用两个栈实现一个队列呢？这也是面试中常问的问题。

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

先来看一幅图：

![70][]

左侧描述的是使用两个栈实现入队操作：有两个栈stack1和stack2,将入队的数据全部压入stack1栈中，即可完成入队操作。

右图描述的是使用两个栈实现出队操作：先判断stack2是否为空，要是为空，先将stack1中的数据全部压入stack2中，再弹stack2的栈顶元素。否则直接弹stack2的栈顶元素。

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

import java.util.Stack;
    
    /**
     * 使用两个栈实现一个队列
     * @param <E>
     */
    public class StackQueue<E> {
        private Stack<E> stack1 = new Stack<E>();
        private Stack<E> stack2 = new Stack<E>();
    
        public boolean isEmpty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    
        public int getSize() {
            return stack1.size() + stack2.size();
        }
    
        public void push(E e) {
            stack1.push(e);//首先将所有数据放入到stack1中
        }
    
        public E pop() {
            //若stack2为空，将stack1中的数据直接放入Stack2
            if(stack2.isEmpty()) {
                while(!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            //要是stack2不为空，直接从stack2中弹出数据
            return stack2.pop();
        }
    
        public E peek() {
            if(stack2.isEmpty()) {
                while(!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
    
            return stack2.peek();
        }
    }

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

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

### 4、测试结果 ###

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

[70]: /images/20220521/fb1918fb74124374b553205f99e53de7.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

两个队列实现栈： package test; import java.util.Stack; public class TwoSt

以你之姓@/ 2022年07月18日 01:24/ 0 赞/ 257 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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