LeetCode--Implement Queue using Stacks

喜欢ヅ旅行 2022-08-17 16:07 21阅读 0赞

**Problem:**

> 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.  
> Notes:  
> \- You must use onlystandard 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).

**Analysis:**  
题意：用栈实现队列  
用两个堆栈实现，一个放push的数据，另一个放pop的数据，但是在pop在前需要将push栈中的数据push到pop栈中,这样就可以使pop先进先出了。  
注意：

*  堆栈的输入元素是对象，所以需要定义Integer类型
 *  pop时应该先pop堆栈（pop的），如果为空就要将push堆栈的数据push到pop堆栈中，然后再pop出去。
 *  peek需要返回int类型，所以注意输出时return，不要忘了。
 *  判断是否为空主要是判断两个栈是否同时为空。

**Anwser:**

class MyQueue {
        // Push element x to the back of queue.
        Stack<Integer> in = new Stack<>();
        Stack<Integer> out = new Stack<>();
        public void push(int x) {
            in.push(x);
        }
        // Removes the element from in front of queue.
        public void pop() {
            if (!out.empty()) out.pop();
            else {
                while(!in.empty())  out.push(in.pop());
                out.pop();
            }
        }
        // Get the front element.
        public int peek() {
            if (!out.empty()) return out.peek();
            else {
                while(!in.empty()) out.push(in.pop());
                return out.peek();
            }
        }
        // Return whether the queue is empty.
        public boolean empty() {
            if(in.empty()&& out.empty()) return true;
            else return false;
        }
    }