Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

 

스택을 이용해서 Queue를 디자인하라는 문제이다. Stack에서 Queue로 가는데 가장 어려운 챌린지는 바로 stack에서는 top밖에 이용하지 못한다는 것이다. 그러므로 맨 마지막 element를 이용하기 위해서는, 당연히도 스택을 뒤집어야한다. 벽돌을 쌓았는데 맨 첫번째 벽돌을 빼내야하고, 발로 차서 빠져나오지 못한다면, 순서를 거꾸로 다시 쌓아서 위에서부터 처리하는식이다.

import java.util.Stack;
class MyQueue {

    Stack<Integer> stack;
    Stack<Integer> popStack;
    public MyQueue() {
        stack = new Stack<>();
        popStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
    }
    
    public int pop() {
        if(empty()) return -1;
        if(popStack.empty()){
            flushToPopStack();   
        }
        return popStack.pop();
    }
    
    public int peek() {
        if(empty()) return -1;
        if(popStack.empty()){
            flushToPopStack();   
        }
        return popStack.peek();  
    }
    
    public boolean empty() {
        return stack.empty() && popStack.empty();
    }
    
    public void flushToPopStack() {
        while(!stack.empty()){
            popStack.push(stack.pop());
        }    
    }
}

push를 할땐, 순서대로 넣고, 대신 pop이나 peek이 불릴 때, flushToPopStack이라는 function을 이용해서 거꾸로 옮겨주는식으로 했다. 만약, 두번째 스택에 지난번에 옮겨둔것들이 있다면, 그것들부터 pop을 하면 된다.

push, empty의 경우에는 O(1)이고, peek또는 pop의 경우에는, 최악의 경우 O(N)이지만, 한번이라도 flush를 했다면 N이상의 작업을 다시 하지는 않아도 된다.

 

위 해법으로 100%에 해당하는 속도로 문제를 풀 수 있었다.

Pokemon Stack

https://leetcode.com/problems/implement-queue-using-stacks/

Implement Queue using Stacks - LeetCode