文档章节

使用队列实现栈 Implement Stack using Queues

叶枫啦啦
 叶枫啦啦
发布于 2017/08/18 09:52
字数 774
阅读 4
收藏 0

问题:

Implement the following operations of a stack using queues.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • empty() -- Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue -- which means only push to backpeek/pop from frontsize, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

解决:

① 题目要求使用队列实现stack操作。用两个队列q1,q2实现一个栈。push时把新元素添加到q1的队尾。pop时把q1中除最后一个元素外逐个添加到q2中,然后pop掉q1中的最后一个元素,然后注意要保证队列2在使用完成后置为空,以保证我们添加元素时始终向q1中添加。top的道理类似。push: O(1),pop: O(n),top: O(n)

class MyStack { //101ms
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    /** Initialize your data structure here. */
    public MyStack() {} 
    /** Push element x onto stack. */
    public void push(int x) {
        q1.offer(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while(q1.size() > 1) q2.offer(q1.poll());
        int top = q1.poll();
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
        return top;
    }
    /** Get the top element. */
    public int top() {
        while(q1.size() > 1) q2.offer(q1.poll());
        int top = q1.peek();
        q2.offer(q1.poll());
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
        return top;
    } 
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty();
    }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack(); 
 * obj.push(x); 
 * int param_2 = obj.pop(); 
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

使用两个队列,所有元素都倒序保存在q1中,即后添加的元素在q1的最前端;每次push时,把新元素放到空的q2,然后把q1中元素逐个添加到q2的队尾,最后交换q1和q2。这样q1队首的元素就是最后添加的元素,pop和top直接返回q1队首的元素就好。push: O(n),pop: O(1),top: O(1)

class MyStack { // 86ms
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    /** Initialize your data structure here. */
    public MyStack() {} 
    /** Push element x onto stack. */
    public void push(int x) {
        q2.offer(x);
        while(q1.size() > 0) q2.offer(q1.poll());
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return q1.poll();
    }
    /** Get the top element. */
    public int top() {
        return q1.peek();
    } 
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty();
    }
}

③ 只使用一个队列。push时直接添加到队尾就好。pop和top时,把队列除最后一个元素外,逐个循环添加到队列的尾部。push: O(1),pop: O(n),top: O(n)

class MyStack { //90ms
    private Queue<Integer> q = new LinkedList<>();
    /** Initialize your data structure here. */
    //public MyStack() {} 
    /** Push element x onto stack. */
    public void push(int x) {
        q.offer(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        for (int i = 1;i < q.size() ;i ++ ) {
            q.offer(q.poll());
        }
        return q.poll();
    }
    /** Get the top element. */
    public int top() {
        for (int i = 1;i < q.size() ;i ++ ) {
            q.offer(q.poll());
        }
        int top = q.peek();
        q.offer(q.poll());
        return top;
    } 
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 12
博文 577
码字总数 384162
作品 0
海淀
私信 提问
用队列实现栈操作

原题   Implement the following operations of a stack using queues.   push(x) – Push element x onto stack.   pop() – Removes the element on top of the stack.   top() –......

一贱书生
2016/12/28
2
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
LeetCode 225 Implement Stack using Queues(用队列来实现栈)(*)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50551035 翻译 原文 分析 对栈和队列不清楚的话,可以先看这篇...

nomasp
2016/01/20
0
0
LeetCode算法题-Implement Stack Using Queues

这是悦乐书的第193次更新,第198篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作: push(x) - 将元素x推入栈。 pop() ...

小川94
2018/12/06
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
16
0

没有更多内容

加载失败,请刷新页面

加载更多

spring mvc主流程源码阅读(剖析)

第一步,通过web.xml的配置可以知道,用户访问url第一次先走到DispatchServlet,(默认你学过基本的java的Servlet开发) <servlet><servlet-name>springServlet</servlet-name><serv......

小海bug
13分钟前
0
0
vmstat命令详解

https://www.cnblogs.com/ggjucheng/archive/2012/01/05/2312625.html

流光韶逝
48分钟前
1
0
如何理解算法时间复杂度的表示

先从O(1) 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键 字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执...

yky20190625
今天
5
0
分布式架构 实现分布式锁的常见方式

一、我们为什么需要分布式锁? 在单机时代,虽然不需要分布式锁,但也面临过类似的问题,只不过在单机的情况下,如果有多个线程要同时访问某个共享资源的时候,我们可以采用线程间加锁的机制...

太猪-YJ
今天
9
0
GitLab Docker 安装记录

安装环境 环境Centos7.4 64 1.拉取镜像文件 docker pull gitlab/gitlab-ce:latest 2.docker 安装 git.zddts.com 为访问域名或换成可以访问的IP docker run -d --hostname git.***.com -p ......

侠者圣
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部