Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/

 

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

 

Queue를 이용해서 stack을 개발하라는 문제이다. 처음에는 두개의 큐를 이용해서 pop이나 push를 부를때마다, queue에 한개가 남을때까지 stack으로 보내준 후, 마지막 남은것을 peek하거나 poll하는 식의 접근을 생각했었지만, 더 좋은 방법이 있었다. 바로 큐를 1개만 사용하는것이다. 값이 1과 9 사이였고, 최대 100번의 호출밖에 없기때문에, 사이즈가 최대 100이라고 한다면, push가 조금 복잡해도 된다는 생각이었다.

 

import java.util.*;

class MyStack {

    Queue<Integer> queue;
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
        for(int i = 0; i < queue.size() - 1; i++){
            queue.add(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();        
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

값이 들어올때마다 큐의 사이즈보다 1 적게 로테이션을 돌려서, 값을 거꾸로 저장해주는 방식이다.

 

가장 효율이 좋았고, queue를 사용한것이 조금 컸는지, space에서는 그렇게 효율적이지는 않았다.

여기서 pop, top, empty같은 경우에는 O(1), push의 경우에는 O(N)의 시간이 사용되며, 즉 최대 100 * O(N), 결국 O(N)의 솔루션이다. Space는 큐의 사이즈, 즉 O(N)의 space complexity가 필요하다.

 

 

Pokemon Queue

 

 

https://leetcode.com/problems/implement-stack-using-queues/

Implement Stack using Queues - LeetCode