当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.225.Implement Stack using Queues 用队列实现栈

LeetCode.225.Implement Stack using Queues 用队列实现栈

题目描述

225 Implement Stack using Queues
https://leetcode-cn.com/problems/implement-stack-using-queues/

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.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

  • You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, 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).

相似题目

LeetCode.剑指offer.009.用两个栈实现队列
LeetCode.232.Implement Queue using Stacks 用栈实现队列
LeetCode.225.Implement Stack using Queues 用队列实现栈


解题过程

两个队列PushO(1)PopO(n)

2个队列模拟栈,其中一个一直是空的。
push:放到非空队列尾部
pop:非空队列前n-1个元素入队到空队列,返回最后一个元素
empty:两个队列都是空则栈空
top:这里有个优化,使用一个成员变量tail保存最后一个入队的元素,top直接返回这个元素。在push和pop时都需要更新tail

push时间复杂度 O(1),pop时间复杂度 O(n)

private static class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    private Integer tail;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
        tail = null;
    }

    /** Push element x onto stack. */
    public void push(int x) {
        if (q1.isEmpty()) {
            q2.offer(x);
        } else {
            q1.offer(x);
        }
        tail = x;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        tail = null;
        Queue<Integer> emptyQueue = q1.isEmpty() ? q1 : q2;
        Queue<Integer> nonEmptyQueue = q1.isEmpty() ? q2 : q1;
        int size = nonEmptyQueue.size();
        for (int i = 0; i < size - 1; i++) {
            tail = nonEmptyQueue.poll();
            emptyQueue.offer(tail);
        }
        return nonEmptyQueue.poll();
    }

    /** Get the top element. */
    public int top() {
        return tail;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return true;
        }
        return false;
    }
}

两队队列PushO(n)PopO(1)

两队队列,一个一直为空。
如果想实现 Pop 时间复杂度为O(1),就得在入队的时候就把数据整理为栈的结构。
push:元素x放到空队列中,再把非空队列依次插入进来,就实现了最后插入的元素在队头
pop:直接非空队列出队

一个队列PushO(1)PopO(n)

一个队列,队列中的元素按 先进先出 的顺序排列。
Push:正常入队
Pop:前n-1个元素循环插入队列末尾,q.offer(q.poll()),第n个元素出队返回

一个队列PushO(n)PopO(1)

一个队列,队列中的元素按 后进先出 的顺序排列,即永远保持队头的元素是最后插入的
Push:插入队列尾部,然后前n-1个元素循环从头部出队后再插入尾部
Pop:直接出队即可


GitHub代码

algorithms/leetcode/leetcode/_225_ImplementStackUsingQueues.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_225_ImplementStackUsingQueues.java


上一篇 LeetCode.232.Implement Queue using Stacks 用栈实现队列

下一篇 LeetCode.695.Max Area of Island 岛屿的最大面积

阅读
评论
723
阅读预计3分钟
创建日期 2020-03-01
修改日期 2020-03-01
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论