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

今天药忘吃喽~ 2022-02-28 03:34 310阅读 0赞

## 问题描述 ##

使用两个栈模拟队列，比如输入：1 2 3 4，则要求输出仍是：1 2 3 4

## 解题思路 ##

1、有两个栈，一个用来存放入队数据（数据栈），一个用来辅助（辅助栈）实现数据出队。

2、数据添加时，会依次压人栈，取数据时会取栈顶元素，但要模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了，把数据栈的元素依次弹出到辅助栈，保留最后一个元素，数据栈就直接把元素弹出，这时数据栈就已经空了。

3、辅助栈的元素依次压人数据栈，这样我们就成功取到了栈底元素。

## 代码实现 ##

public class Stack2Queue {
        /**
         * 用栈的入栈和出栈
         * 来实现队列的入队和出队
         * stack1是入栈的，stack2是出栈的。
         * 入队列：直接压入stack1即可
         * 出队列：如果stack2不为空，把stack2中的栈顶元素直接弹出；
         * 否则，把stack1的所有元素全部弹出压入stack2中，再弹出stack2的栈顶元素
         */
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
    
        public void add(Object o) {
            stack1.push(o);
        }
    
        public Object poll() {
            Object o = null;
    
            if (stack2.size()== 0) {
                //把stack1的数据放入stack2，留下最后一个数据
                while (stack1.size() > 1) {
                    stack2.push(stack1.pop());
                }
                if (stack1.size() == 1) {
                    //把stack1的留下的那个数据返回出去
                    o = stack1.pop();
                }
            } else {
                o = stack2.pop();
            }
    
            return o;
        }
    
        public int length() {
            return stack1.size() + stack2.size();
        }
    
        public static void main(String[] args) {
            /**
             * 用两个栈实现队列
             * */
            Stack2Queue stack2Queue = new Stack2Queue();
            stack2Queue.add("a");
            stack2Queue.add("b");
            stack2Queue.add("c");
            stack2Queue.add("d");
            stack2Queue.add("e");
            while(stack2Queue.length()>0) {
                System.out.println(stack2Queue.poll());
            }
        }
    
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关使用队列实现栈(数据结构基础回顾)

使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否

约定不等于承诺〃/ 2023年02月22日 05:23/ 0 赞/ 5 阅读

相关数据结构使用2个栈实现一个队列

function StackQueue(){ // 数组模拟栈，只能用push, pop方法 let stack1 = []; // 用于入队

刺骨的言语ヽ痛彻心扉/ 2022年12月22日 05:00/ 0 赞/ 121 阅读

相关【数据结构与算法】十七栈队列

【数据结构与算法】十七栈队列栈后进先出（Last In First Out），简称为LIFO线性表。实际应用方法的调用 A -> B -> C

短命女/ 2022年08月21日 12:43/ 0 赞/ 193 阅读

相关数据结构-栈&队列&Deque实现比较

栈栈的ADT 进栈出栈栈的存储结构实现队列队列的ADT 入队列出队

超、凢脫俗/ 2022年06月07日 13:23/ 0 赞/ 173 阅读

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

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

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

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

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

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

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

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

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

相关数据结构-js实现栈和队列

我们都知道数据结构对我们非常重要，我在几场笔试题中遇到了非常多的有关数据结构的问题。因为我学习数据结构在一年多以前了，有点忘了，所以今天想好好温习一下数据结构的知识，先从简单的

Dear 丶/ 2022年01月19日 02:55/ 0 赞/ 275 阅读

相关 (数据结构)栈和队列( C实现 )

栈和队列 1.栈 > 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵

「爱情、让人受尽委屈。」/ 2021年10月25日 15:18/ 0 赞/ 428 阅读