Stack/Queue HackerRank Algorithms in Java ‘Queues: A Tale of Two Stacks’ solution

Problem

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.
A basic queue has the following operations:

• Enqueue: add a new element to the end of the queue.
• Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process queries, where each query is one of the following 3 types:

• 1 x: Enqueue element x into the end of the queue.
• 2: Dequeue the element at the front of the queue.
• 3: Print the element at the front of the queue.

Sample Input

10
1 42
2
1 14
3
1 28
3
1 60
1 78
2
2

Sample Output

14
14

Solution

• 데이터 저장은 stackin에 한다.
• dequeue()를 할 때, stackin에 있는 데이터를 전부 stackout으로 옮기고 pop()하면 stackin에서 가장 먼저 들어온 값이 반환된다. 만약 이미 stackout에 숫자가 있는 채로 stackin에 있는 데이터를 옮기면 순서가 섞이므로 stackout이 비워질 때까지 기다린다.

Code

class MyQueue<T> {
    private Stack<T> stackin = new Stack<>();
    private Stack<T> stackout = new Stack<>();
    
    public void enqueue(T n) {
        stackin.push(n);
    }
    
    public void dequeue() {
        if(stackout.isEmpty()) {
            while(!stackin.isEmpty())
                stackout.push(stackin.pop());
        }
        stackout.pop();    
    }
    
    public T peek() {
        if(stackout.isEmpty()) {
            while(!stackin.isEmpty())
                stackout.push(stackin.pop());
        }
        
        return stackout.peek();
    }
}