【5.28算法练习】用队列实现栈#队列#栈

2021/5/30 1:20:55

本文主要是介绍【5.28算法练习】用队列实现栈#队列#栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通队列的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

示例

输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题

我们知道栈是先进后出,队列是先进先出的,我的直观想法如下

  • push() 哪个队列有元素就放进哪个队列,如果两个队列都为空,那放进哪个队列都可以。
  • pop() 例如此时queue1不为空,queue1最后进的元素应该最先出,把队列1元素按先进先出顺序offer到queue2中,注意当队列1中只剩一个元素时,这个元素就是最后进来的元素,故应该返回这个元素。
  • top() 和上面pop()思想一致,但是不弹出元素。
  • empty() 只要两个队列都为空说明此栈不为空。

第一版

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList();
        queue2 = new LinkedList();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (queue1.isEmpty()) {
            while (queue2.size() != 1) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        } else {
            while (queue1.size() != 1) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }

    }

    /**
     * Get the top element.
     */
    public int top() {
        Integer peek;
        if (queue1.isEmpty()) {
            while (queue2.size() != 1) {
                queue1.offer(queue2.poll());
            }
            peek = queue2.peek();
            queue1.offer(queue2.poll());
            return peek;
        } else {
            while (queue1.size() != 1) {
                queue2.offer(queue1.poll());
            }
            peek = queue1.peek();
            queue2.offer(queue1.poll());
            return peek;
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
  • 时间复杂度:push() 和empty()为O(1) ,top()和pop()为O(N)
  • 空间复杂度:O(N)

每次pop()、top() 都要在queue1和queue2之间交换元素,代码不够优美。

第二版

参考高票答案,然后对第一版代码进行改造。

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

  • 时间复杂度:top()、pop() 和empty()为O(1) ,push()为O(N)
  • 空间复杂度:O(N)

先进先出转为先进后出主要在push() 操作中,最后一个进来的元素永远要放进空的queue2中,然后queue1的元素offer到queue2中,然后,queue1和queue2交换,交换后queue2为空,迎接下一个push() 的元素,这样在pop()、top() 直接通过queue1.poll() 、queue1.peek() 即可。

扩展版

如果只能用一个队列,来实现栈的功能,不算难,核心操作在push()中。

class MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        //把之前在队列里的元素弹出在压入,只为新来的元素pop()可以先弹出
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

  • 时间复杂度:top()、pop() 和empty()为O(1) ,push()为O(N)
  • 空间复杂度:O(N)

小结

如果对栈不熟悉可以参考之前写的文章《Stack源码剖析》。
此题在力扣上也有镜像题目,叫用栈实现队列。
如果按解法一也可实现,两个栈之间相互交换,当弹出方只剩一个元素这个值即为top()和pop()返回对象,同样问题是不够优美,大家可以思考一下怎么优美实现。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。



这篇关于【5.28算法练习】用队列实现栈#队列#栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程