Using a Queue to Simulate a Stack

A single queue cannot fully emulate stack behavior due to the LIFO (Last In, First Out) nature of stacks versus the FIFO (First In, First Out) principle of queues. However, using two queues, we can successfully mimic stack operations.

Push Operation: Add elements to the non-empty queue. If both are empty initially, insert into the first queue.

Pop Operation: Transfer all but one element from the non-empty queue to the other, then remove and return the last remaining element.

Top Operasion: Move all elements from one queue to the other, tracking each value until the last one is retrieved — this represents the top of the stack.

Empty Check: The stack is empty only when both queues are empty.

import java.util.LinkedList;
import java.util.Queue;

class QueueBasedStack {
    private Queue<Integer> primary;
    private Queue<Integer> secondary;

    public QueueBasedStack() {
        primary = new LinkedList<>();
        secondary = new LinkedList<>();
    }

    public void push(int val) {
        if (isEmpty()) {
            primary.offer(val);
            return;
        }
        if (!primary.isEmpty()) {
            primary.offer(val);
        } else {
            secondary.offer(val);
        }
    }

    public int pop() {
        if (isEmpty()) return -1;
        
        Queue<Integer> source = primary.isEmpty() ? secondary : primary;
        Queue<Integer> target = primary.isEmpty() ? primary : secondary;
        
        while (source.size() > 1) {
            target.offer(source.poll());
        }
        return source.poll();
    }

    public int top() {
        if (isEmpty()) return -1;
        
        Queue<Integer> source = primary.isEmpty() ? secondary : primary;
        Queue<Integer> target = primary.isEmpty() ? primary : secondary;
        int result = -1;
        
        while (!source.isEmpty()) {
            result = source.poll();
            target.offer(result);
        }
        return result;
    }

    public boolean isEmpty() {
        return primary.isEmpty() && secondary.isEmpty();
    }
}

---

Using a Stack to Simulate a Queue

To implement a queue using two stacks, leverage the fact that reversing the order of elements via stack popping allows us to maintain FIFO semantics.

Enqueue Operation: Simply push the element onto stack1.

Dequeue Operation: If stack2 is empty, transfer all elements from stack1 to stack2. Then pop from stack2.

Peek Operation: Similar to dequeue, ensure stack2 has elements before returning the top.

Empty Check: The queue is empty only when both stacks are empty.

import java.util.Stack;

class StackBasedQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public StackBasedQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void enqueue(int val) {
        input.push(val);
    }

    public int dequeue() {
        if (isEmpty()) return -1;
        
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.pop();
    }

    public int peek() {
        if (isEmpty()) return -1;
        
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }

    public boolean isEmpty() {
        return input.isEmpty() && output.isEmpty();
    }
}

This approach ensures correct ordering for queue-like behavior using stack primitives.