由两个栈组成的队列

问题

编写一个类,用两个栈实现队列,支持队列的基本操作:add、poll、peek。

思路

栈的特点是先进后出,队列的特点是先进先出,使用两个栈正好能把顺序反过来实现类似队列的操作。

方案

public class TwoStackQueue<T extends Comparable<T>> {

    private Stack<T> mStack1;

    private Stack<T> mStack2;

    public TwoStackQueue() {
        mStack1 = new Stack<>();
        mStack2 = new Stack<>();
    }

    public void add(T item) {
        mStack1.push(item);
    }

    /**
     * 移除并返回队首的元素
     *
     * @return
     */
    public T poll() {

        if (mStack1.isEmpty() && mStack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty!");
        } else if (mStack2.isEmpty()) {
            while (!mStack1.isEmpty()) {
                mStack2.push(mStack1.pop());
            }
        }

        return mStack2.pop();

    }

    /**
     * 返回队列头部的元素
     *
     * @return
     */
    public T peek() {

        if (mStack1.isEmpty() && mStack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty!");
        } else if (mStack2.isEmpty()) {
            while (!mStack1.isEmpty()) {
                mStack2.push(mStack1.pop());
            }
        }

        return mStack2.peek();

    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

C++ 高级语法学习与总结(代码实例)

    C++11增加了许多的特性,auto就是一个很明显的例子。  还有就是typedid()获取数据变量的类型     看下面简短的代码:         ...

35660
来自专栏Java编程技术

JDK动态代理代理与Cglib代理原理探究

UserServiceImpl被JDK代理后的类,在项目的com.sun.proxy下面生成$Proxy0.class类

26120
来自专栏机器学习入门

LWC 61:740. Delete and Earn

LWC 61:740. Delete and Earn 传送门:740. Delete and Earn Problem: Given an array nu...

23250
来自专栏机器学习入门

LWC 52:686. Repeated String Match

LWC 52:686. Repeated String Match 传送门:686. Repeated String Match Problem: Given...

21150
来自专栏Hellovass 的博客

设计一个有 getMin 功能的栈

这个类的设计上,采用两个栈,一个用来保存当前栈中的元素,其功能等同于一个正常的栈,记为 mStack;另一个栈用来保存每一步的最小值,记为 mMinStack.

8620
来自专栏海说

14、Iterator跟ListIterator的区别

14、Iterator与ListIterator的区别       在使用List,Set的时候,为了实现对其数据的遍历,会经常使用到Iterator(跌代器)...

19800
来自专栏文武兼修ing——机器学习与IC设计

栈与栈的实现栈栈的基本操作栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作...

33050
来自专栏吾爱乐享

java之学习LinkedList的特有功能及案例分析

13120
来自专栏专注 Java 基础分享

详解Java动态代理机制(二)----cglib实现动态代理

     上篇文章的结尾我们介绍了普通的jdk实现动态代理的主要不足在于:它只能代理实现了接口的类,如果一个类没有继承于任何的接口,那么就不能代理该类,原因是我...

284100
来自专栏小勇DW3

concrrent类下 BlockingDeque 下 自己实现代码编写

  java6增加了两种容器类型,Deque和BlockingDeque,它们分别对Queue和BlockingQueue进行了扩展。 Deque是一个双端队...

8520

扫码关注云+社区

领取腾讯云代金券