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

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

题目描述

232 Implement Queue using Stacks
https://leetcode-cn.com/problems/implement-queue-using-stacks/

Implement the following operations of a queue using stacks.

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

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

相似题目

58同城基础架构部中间件,一面面试题

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


解题过程

两个栈EnQueueO(1)DeQueueO(n)

两个栈,一个始终是空的
EnQueue: 插入到非空栈末尾
DeQueue:非空栈顶n-1个元素pop到空栈,返回最后一个元素,再全部push回非空栈
peek: 用一个变量始终记住栈底(队头)元素,push、pop时更新,peek时直接返回

EnQueue时间复杂度 O(1),DeQueue时间复杂度 O(n)

private static class MyQueue {
    private Deque<Integer> nonEmptyQueue;
    private Deque<Integer> emptyQueue;
    private Integer head; // 队列头

    /** Initialize your data structure here. */
    public MyQueue() {
        nonEmptyQueue = new LinkedList<>();
        emptyQueue = new LinkedList<>();
        head = null;
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (nonEmptyQueue.isEmpty()) {
            head = x;
        }
        nonEmptyQueue.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        head = null;
        int size = nonEmptyQueue.size();
        for (int i = 0; i < size - 1; i++) {
            head = nonEmptyQueue.pop();
            emptyQueue.push(head);
        }
        int ret = nonEmptyQueue.pop();
        while (!emptyQueue.isEmpty()) {
            nonEmptyQueue.push(emptyQueue.pop());
        }
        return ret;
    }

    /** Get the front element. */
    public int peek() {
        return head;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return nonEmptyQueue.isEmpty();
    }
}

两个栈EnQueueO(1)DeQueue摊还O(1)

EnQueue:将元素压入s1。
DeQueue:判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
peek:s2不空则取s2栈顶,否则取s1栈底,可以用一个变量记住s1栈底元素
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。

DeQueue时间复杂度可以具体查下“摊还分析”

两个栈EnQueueO(n)DeQueueO(1)

要想 出队 时能够 O(1),需要让栈顶始终是最先入站的元素。
EnQueue:非空栈元素再依次pop倒入空栈,新元素push到刚腾空的栈,再把另一个栈的元素挨个push进来
DeQueue:直接pop非空栈顶
peek:直接peek非空栈顶

EnQueue时间复杂度 O(n),DeQueue时间复杂度 O(1)


GitHub代码

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


上一篇 LeetCode.088.Merge Sorted Array 合并两个有序数组

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

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

页面信息

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

评论