232. Implementing Queue Using Stacks

Implement a queue using stacks with the following operations:

• push(x) -- Insert an element at the back of the queue.
• pop() -- Remove and return the element from the front of the queue.
• peek() -- Return the element at the front of the queue without removing it.
• empty() -- Return whether the queue is emppty.

Constraints

• You may only use standard stack operations: push to top, peek/pop from top, size, and is empty.
• If your programming language doesn't support stacks, you can simulate them using lists or deques, as long as you adhere to standard stack operations.
• All operations are guaranteed to be valid (e.g., no pop or peek calls on an empty queue).

Approach

Use two stacks to simulate a queue: one for input and one for output.

• When pushing an element, simply add it to the input stack.
• When popping or peeking, if the output stack is empty, transfer all element from the input stack to the output stack (this reverses they order). Then, perform the operation on the output stack.
• The queue is empty when both stacks are empty.

Code Example

class QueueUsingStacks {
    private java.util.Stack<Integer> inputStack;
    private java.util.Stack<Integer> outputStack;

    public QueueUsingStacks() {
        inputStack = new java.util.Stack<>();
        outputStack = new java.util.Stack<>();
    }

    public void push(int value) {
        inputStack.push(value);
    }

    public int pop() {
        transferIfNeeded();
        return outputStack.pop();
    }

    public int peek() {
        transferIfNeeded();
        return outputStack.peek();
    }

    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }

    private void transferIfNeeded() {
        if (!outputStack.isEmpty()) return;
        while (!inputStack.isEmpty()) {
            outputStack.push(inputStack.pop());
        }
    }
}

225. Implementing Stack Using Queues

Implement a stack using queues with the following operations:

• push(x) -- Push element x onto the stack.
• pop() -- Remove and return the element on top of the stack.
• top() -- Return the top element without removing it.
• empty() -- Return whether the stack is empty.

Constraints

• You may only use standard queue operations: push to back, peek/pop from front, size, and is empty.
• If your programming language doesn't support queues, you can simulate them using lists or deques, as long as you adhere to standard queue operations.
• All operations are guaranteed to be valid (e.g., no pop or top calls on an empty stack).

Approach

Use a single queue to simulate a stack.

• When pushing an element, simply add it to the queue.
• When popping or accessing the top element, rotate the queue by moving all elements except the last one to the back. This makes the last element accessible at the front, mimicking stack behavior.

Code Example

class StackUsingQueues {
    private java.util.Queue<Integer> dataQueue;

    public StackUsingQueues() {
        dataQueue = new java.util.LinkedList<>();
    }

    public void push(int value) {
        dataQueue.add(value);
    }

    public int pop() {
        rotateToTop();
        return dataQueue.poll();
    }

    public int top() {
        rotateToTop();
        int topValue = dataQueue.poll();
        dataQueue.add(topValue);
        return topValue;
    }

    public boolean empty() {
        return dataQueue.isEmpty();
    }

    private void rotateToTop() {
        int elementsToMove = dataQueue.size() - 1;
        for (int i = 0; i < elementsToMove; i++) {
            dataQueue.add(dataQueue.poll());
        }
    }
}