Stack and Queue Implementations

LeetCode 232: Implementing a Queue Using Stacks

Core Concept: Use two stacks, one for input and one for output. Whenn dequeuing, transfer all elements from the input stack to the output stack, then pop from the output stack. For enqueuing, push directly to the input stack.

class QueueWithStacks {
    private Stack<Integer> inputStack = new Stack<>();
    private Stack<Integer> outputStack = new Stack<>();
    private int elementCount = 0;

    public QueueWithStacks() {}

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

    public int dequeue() {
        if (elementCount <= 0) {
            return -1;
        }
        elementCount--;
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.pop();
    }

    public int peekFront() {
        if (elementCount <= 0) {
            return -1;
        }
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek();
    }

    public boolean isEmpty() {
        return elementCount == 0;
    }
}

LeetCode 225: Implementing a Stack Using Queues

Core Concept: Simulate stack behavior with a queue. This example uses a single queue where each push operation reorders elements to maintain LIFO order.

class StackWithQueue {
    private Queue<Integer> dataQueue = new ArrayDeque<>();

    public StackWithQueue() {}

    public void push(int value) {
        dataQueue.offer(value);
        int currentSize = dataQueue.size();
        while (currentSize-- > 1) {
            dataQueue.offer(dataQueue.poll());
        }
    }

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

    public int top() {
        return dataQueue.element();
    }

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