【LeetCode 225】用一个or两个队列实现栈

╰半夏微凉° 2021-09-22 22:22 249阅读 0赞

LeetCode 225：

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

要用队列实现堆栈，主要就是要实现上述的四个功能函数，这里给出两种解法，第一种是利用两个队列来实现栈的解法：

class MyStack { 
    
        Queue<Integer> queue1;
        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 (this.empty()) { 
                queue1.add(x);
            } else { 
                if (queue1.isEmpty()) { 
                    queue2.add(x);
                } else { 
                    queue1.add(x);
                }
            }
        }
    
        /** Removes the element on top of the stack and returns that element. */
        public int pop() { 
            int value = 0;
            if (queue1.isEmpty()) { 
                while (queue2.size() > 1) { 
                    queue1.add(queue2.poll());
                }
                value = queue2.poll();
            } else { 
                while (queue1.size() > 1) { 
                    queue2.add(queue1.poll());
                }
                value = queue1.poll();
            }
            return value;
        }
    
        /** Get the top element. */
        public int top() { 
            int value = 0;
            if (queue1.isEmpty()) { 
                while (queue2.size() > 1) { 
                    queue1.add(queue2.poll());
                }
                value = queue2.peek();
                queue1.add(queue2.poll());
            } else { 
                while (queue1.size() > 1) { 
                    queue2.add(queue1.poll());
                }
                value = queue1.peek();
                queue2.add(queue1.poll());
            }
            return value;
        }
    
        /** Returns whether the stack is empty. */
        public boolean empty() { 
            return queue1.isEmpty() && queue2.isEmpty();
        }
    }

它的思路就是：当你要取一个元素时，相当于要取队列的最末一个元素，**将队列前n - 1个元素都移动到另外一个队列中，剩下的，就是原队列中的最末一个元素，取出即使栈返回的结果**。这种思路非常好，但代码可能不太简洁。

第二种，是只用一个队列的解法，稍微难想一点，但更简洁：

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

这段代码主要可能出现的疑惑在于，压入栈的部分，只要这一部分想通了，后面的部分就容易考虑了。

我们可以这么想，队列的特点是什么？一边入一边出，先入先出，而栈是先入后出，那，我们是否可以通过某些方法，让队列的一端维持“栈”的那种先入后出的状态呢？  
我们可以想，如果对于两个元素：a、b，出的顺利应该为： b、a，对于三个元素，a、b、c，出栈的顺利应该为 c、b、a，从两个元素，到三个元素，我们压入了一个元素c，而我们应该维护的顺序，从"b、a"，变成了压栈后"b、a、c"，变成"c、b、a"，可以发现，**对于每进入一个元素，将前面所有元素取出再重新入队列，可以维护同栈一样的顺序**，因此：

public void push(int x) { 
        	// 加入一个元素
            queue.add(x);
            // 在这个元素前的所有元素进行出队列，再入队列的操作
            for (int i = 0; i < queue.size() - 1; i++) { 
                queue.add(queue.poll());
            }
        }

在LeetCode上进行执行，都可以通过：  
![在这里插入图片描述][20190315004125577.png]  
用两个队列的方法更快一些，但同时占用内存的量更大。

[其他 LeetCode 题目解析][LeetCode]

[20190315004125577.png]: /images/20210920/80696a924dd249f6aec388da755b8863.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html