leetcode225 implement stack using queues

binta 发布于2019-08-15 13:30 / 2122人阅读

摘要：题目要求使用队列来模拟实现一个栈。栈是指先进后出的数据结构，而队列则是先进先出的数据结构。队列的包括在队列尾插入数据，输出队列头的数据，查看队列的长度，队列是否为空。

题目要求

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.
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).

使用队列来模拟实现一个栈。
栈是指先进后出的数据结构，而队列则是先进先出的数据结构。
假设我们分别往栈和队列中顺序输入[1,2,3]，那么栈的输出是[3,2,1]，而队列的输出的[1,2,3]。

队列的API包括在队列尾插入数据，输出队列头的数据，查看队列的长度，队列是否为空。

那么我们现在看一下如何通过队列来实现栈的操作。

方法一：两个队列

当插入数据中时，固定往非空的那个队列插入数据。（如果两个队列的值都为空，那么就任选一个队列插入即可）。当想要获得栈顶数据或者执行栈的pop操作时，那么就将队列中的值逐个输出到另一个队列中，并输出原队列中最后一个元素的值。

下面用图形展示一下：
1.向数据结构中插入1，因为此时两个队列总都为空，因此任选一个队列插入

2.向数据结构中插入2和3，因为此时队列一非空，因此插入队列一

3.模拟pop操作，这是需要将队列一的内容输出再输入到队列二中并丢弃队列1中最后一个元素，即为3

4.模拟top操作，类似于pop，将非空队列的内容逐个转移至空队列，并记录最后的一个元素返回，即为2

代码如下：

public class Stack {

    LinkedList queue1 = new LinkedList();
    LinkedList queue2 = new LinkedList();
    
    /** Push element x onto stack. */
    public void push(int x) {
        if(queue1.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int top = 0;
        if(queue1.isEmpty()){
            while(queue2.size() > 1){
                top = queue2.poll();
                queue1.offer(top);
            }
            top = queue2.poll();
        }else{
            while(queue1.size() > 1){
                top = queue1.poll();
                queue2.offer(top);
            }
            top = queue1.poll();
        }
        return top;
    }
    
    /** Get the top element. */
    public int top() {
        int top = 0;
        if(queue1.isEmpty()){
            while(!queue2.isEmpty()){
                top = queue2.poll();
                queue1.offer(top);
            }
        }else{
            while(!queue1.isEmpty()){
                top = queue1.poll();
                queue2.offer(top);
            }
        }
        return top;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
    
}

思路二：单个队列模拟栈

思路一使用两个队列从而确保值从队列中丢出的过程不会丢失。但是其实一个队列已经足以来模拟栈。我们只需要在每一次往队列中输入数据时，确保当前队列中的输出顺序和栈相同即可。同样我们使用图片来模拟一下过程。
1.输入1，这时队列为空，将1正常输入

2.输入2，这时为了确保队列的输出顺序和栈相同，我需要将1输出并重新输入，这时可以把1看成一个新输入的值，所以将在2之后输出

3.输入3，同上一步，在输入新加入的值后，将余下的值输出后重新输入一遍

其实队列的最大特点就是可以维护原来的输入顺序，因此每次输出再重新输入的数据之间的顺序不会受到影响。

4.pop和push只需要输出或者读取队首的值即可

class MyStack {

    /** Initialize your data structure here. */
    Queue queue;
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        while (size-- > 0) {
            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();
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Leetcod LeetCode Implemented Implement

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68136.html

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

摘要：下面是入栈时代码获得队列长度反转次数为队列长度减一反转语言没有栈和队列数据结构，只能用数组或双端队列实现。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Impl...

AlanKeene 2019-08-19 10:28 评论0 收藏0
[Leetcode] Implement Queue using Stacks 用栈实现队列

摘要：注意的方法是和，实际上我们应该实现的是和或者和，的实现和是一样的，但将改为时，我们要先把到的元素保存，然后再弹出输出栈，然后返回这个保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...

Martin91 2019-08-14 12:29 评论0 收藏0
LeetCode 232：用栈实现队列 Implement Queue using Stacks

摘要：题目使用栈实现队列的下列操作将一个元素放入队列的尾部。用栈实现队列，可以用两个栈完成题解。入队列时用存入节点，出队列时内节点顺序出栈压入中。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队...

cloud 2019-08-19 10:26 评论0 收藏0
[Leetcode] Implement Stack using Queues 用队列实现栈

摘要：双队列法复杂度时间空间思路和类似，我们也可以用两个队列来模拟栈的操作。当时，我们将数字进非空的队列就行了。操作和一样，区别在于我们拿到最后一个数后，还要再把它进另一个队列中。双队列法复杂度时间 O(N) 空间 O(N) 思路和Implement Queue using Stack类似，我们也可以用两个队列来模拟栈的操作。当push时，我们将数字offer进非空的队列就行了。当p...

ivan_qhz 2019-08-14 12:39 评论0 收藏0
leetcode232 Implement Queue using Stacks

摘要：题目要求通过队列实现一个栈的功能。栈的为压入栈顶，出栈，栈顶元素，栈是否为空。重复上述的操作。但是当需要弹出元素时，则从桶弹出。这样，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保证位输入顺序。极大的减少了不必要的入栈出栈。题目要求 Implement the following operations of a queue using stacks. push(x) ...

golden_hamster 2019-08-15 13:32 评论0 收藏0