225. Implement Stack using Queues

// LeetCode URL: https://leetcode.com/problems/implement-stack-using-queues/
import java.util.LinkedList;
import java.util.Queue;

/**
 * One Queue. Push is O(N), Pop is O(1).
 *
 * Time Complexity: Push = O(N). Pop = O(1). Top = O(1). Empty = O(1)
 *
 * Space Complexity: O(N)
 *
 * N = Number of elements in the stack.
 */
class MyStack1 {

    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack1() {
        queue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() throws RuntimeException {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return queue.poll();
    }

    /** Get the top element. */
    public int top() throws RuntimeException {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return queue.peek();
    }

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

/**
 * Two Queue. Push is O(1), Pop is O(N).
 *
 * Time Complexity: Push = O(1). Pop = O(N). Top = O(1). Empty = O(1)
 *
 * Space Complexity: O(N)
 *
 * N = Number of elements in the stack.
 */
class MyStack2 {

    Queue<Integer> queue1;
    Queue<Integer> queue2;
    int top;

    /** Initialize your data structure here. */
    public MyStack2() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue1.offer(x);
        top = x;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() throws RuntimeException {
        if (queue1.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        while (queue1.size() > 1) {
            top = queue1.poll();
            queue2.offer(top);
        }
        int poppedVal = queue1.poll();
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
        return poppedVal;
    }

    /** Get the top element. */
    public int top() throws RuntimeException {
        if (queue1.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

// Your MyStack object will be instantiated and called as such:
// MyStack obj = new MyStack();
// obj.push(x);
// int param_2 = obj.pop();
// int param_3 = obj.top();
// boolean param_4 = obj.empty();