关于java:LeetCode232用栈实现队列

43次阅读

共计 2074 个字符，预计需要花费 6 分钟才能阅读完成。

题目形容：请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的开端

int pop() 从队列的结尾移除并返回元素

int peek() 返回队列结尾的元素

boolean empty() 如果队列为空，返回 true；否则，返回 false

阐明：

你只能应用规范的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是非法的。

你所应用的语言兴许不反对栈。你能够应用 list 或者 deque（双端队列）来模仿一个栈，只有是规范的栈操作即可。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：双栈实现队列

MyQueue 的 2 个栈别离为 inStack 和 outStack，inStack 用来入队列，outStack 用来出队列，几个办法的次要实现逻辑如下：

push(int x)：将 x 入栈 inStack。

pop()：如果栈 outStack 不为空，间接从 outStack 中出栈一个；如果 outStack 为空，则如果 inStack 不为空，将 inStack 的全副元素出栈并且入栈 outStack，而后从栈 outStack 中出栈一个，如果 inStack 也为空，则抛出异样该队列为空。

peek()：如果栈 outStack 不为空，返回 outStack 的栈顶元素；如果 outStack 为空，则如果 inStack 不为空，将 inStack 的全副元素出栈并且入栈 outStack，而后返回 outStack 的栈顶元素，如果 inStack 也为空，则抛出异样该队列为空。

empty()：如果 inStack 和 outStack 都为空，返回 true；否则返回 true。

import java.util.Stack;

public class LeetCode_232 {public static void main(String[] args) {MyQueue myQueue = new MyQueue();
        myQueue.push(1); // queue is: [1]
        myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
        System.out.println(myQueue.peek() == 1); // return 1
        System.out.println(myQueue.pop() == 1); // return 1, queue is [2]
        System.out.println(myQueue.empty()); // return false
    }
}

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {inStack = new Stack<>();
        outStack = new Stack<>();}

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {inStack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {if (outStack.isEmpty()) {if (inStack.isEmpty()) {throw new RuntimeException("stack is empty.");
            } else {while (!inStack.isEmpty()) {outStack.push(inStack.pop());
                }
                return outStack.pop();}

        } else {return outStack.pop();
        }
    }

    /**
     * Get the front element.
     */
    public int peek() {if (outStack.isEmpty()) {if (inStack.isEmpty()) {throw new RuntimeException("stack is empty.");
            } else {while (!inStack.isEmpty()) {outStack.push(inStack.pop());
                }
                return outStack.peek();}

        } else {return outStack.peek();
        }
    }

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