Stack Using Queue — Pop-Heavy Reversal Bug in Trading

package io.thecodeforge.stack;

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

/**
 * This file is NOT the full implementation — it's a visual warm-up.
 * It demonstrates exactly WHY naive queue operations give you FIFO,
 * which is the OPPOSITE of what a stack needs.
 */
public class StackConceptDiagram {

    public static void main(String[] args) {

        Queue<Integer> naiveQueue = new LinkedList<>();

        // Simulate three pushes: 1, then 2, then 3
        naiveQueue.offer(1);  // queue: [1]
        naiveQueue.offer(2);  // queue: [1, 2]
        naiveQueue.offer(3);  // queue: [1, 2, 3]

        System.out.println("=== What a plain Queue gives you ===");
        System.out.println("(FIFO — oldest element comes out first)");
        while (!naiveQueue.isEmpty()) {
            // poll() removes from the FRONT — so 1 comes out first
            System.out.println("Dequeued: " + naiveQueue.poll());
        }

        System.out.println();
        System.out.println("=== What a Stack should give you ===");
        System.out.println("(LIFO — newest element comes out first)");
        System.out.println("Expected order: 3, 2, 1");
        System.out.println("Goal: make the queue behave this way.");
    }
}

package io.thecodeforge.stack;

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

/**
 * Stack implemented using a SINGLE Queue.
 * Strategy: Push is O(n), Pop and Peek are O(1).
 *
 * After every push, the queue is rotated so the newest
 * element sits permanently at the front.
 */
public class StackUsingQueuePushHeavy {

    // One queue is all we need for this strategy
    private Queue<Integer> mainQueue = new LinkedList<>();

    /**
     * Push a new value onto the stack.
     * Time Complexity: O(n) — we rotate all existing elements.
     */
    public void push(int value) {
        // Step 1: Add the new element to the rear of the queue
        mainQueue.offer(value);
        // At this point, 'value' is at the rear — wrong position.
        // We need it at the front. Rotate all PREVIOUS elements behind it.

        // Step 2: Rotate (size - 1) elements from front to rear
        // After this loop, 'value' will be at the front.
        int rotationsNeeded = mainQueue.size() - 1;
        for (int i = 0; i < rotationsNeeded; i++) {
            // Take the front element and put it at the back
            int frontElement = mainQueue.poll();
            mainQueue.offer(frontElement);
        }
        // Now the queue front = most recently pushed element (LIFO order achieved)
    }

    /**
     * Remove and return the top element of the stack.
     * Time Complexity: O(1) — front of queue IS the stack top.
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow — cannot pop from an empty stack");
        }
        return mainQueue.poll(); // Front is always the most recently pushed element
    }

    /**
     * Look at the top element without removing it.
     * Time Complexity: O(1)
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty — nothing to peek at");
        }
        return mainQueue.peek(); // Front = top of our logical stack
    }

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

    public int size() {
        return mainQueue.size();
    }

    // ─── Main: Walk through the internal state step by step ───────────────────
    public static void main(String[] args) {
        StackUsingQueuePushHeavy stack = new StackUsingQueuePushHeavy();

        System.out.println("=== Push-Heavy Strategy Demo ===");
        System.out.println();

        // Push 10
        stack.push(10);
        System.out.println("Pushed 10  | Internal queue: " + stack.mainQueue);
        // Queue: [10] — only one element, no rotation needed

        // Push 20
        stack.push(20);
        System.out.println("Pushed 20  | Internal queue: " + stack.mainQueue);
        // After offer: [10, 20]. Rotate 1 time: move 10 to rear → [20, 10]

        // Push 30
        stack.push(30);
        System.out.println("Pushed 30  | Internal queue: " + stack.mainQueue);
        // After offer: [20, 10, 30]. Rotate 2 times: move 20 → [10, 30, 20], move 10 → [30, 20, 10]

        System.out.println();
        System.out.println("Peek (top of stack): " + stack.peek()); // Should be 30

        System.out.println();
        System.out.println("--- Popping all elements (should be LIFO: 30, 20, 10) ---");
        while (!stack.isEmpty()) {
            System.out.println("Popped: " + stack.pop());
        }

        System.out.println();
        System.out.println("Stack is empty: " + stack.isEmpty());
    }
}

package io.thecodeforge.stack;

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

/**
 * Stack implemented using TWO Queues.
 * Strategy: Push is O(1), Pop and Peek are O(n).
 *
 * Elements are pushed normally. On pop/peek, all but the
 * last element are migrated to the helper queue, then the
 * queues are swapped.
 */
public class StackUsingQueuePopHeavy {

    private Queue<Integer> mainQueue  = new LinkedList<>();
    private Queue<Integer> helperQueue = new LinkedList<>();

    /**
     * Push a new value onto the stack.
     * Time Complexity: O(1) — just a plain enqueue.
     */
    public void push(int value) {
        mainQueue.offer(value);
        // Queue grows in FIFO order: oldest at front, newest at rear.
        // We accept this — we'll deal with the order reversal on pop.
    }

    /**
     * Remove and return the top element of the stack (the last-pushed element).
     * Time Complexity: O(n) — we must drain (n-1) elements to expose the last one.
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow — cannot pop from an empty stack");
        }
        // Step 1: Move all elements except the last one into the helper queue.
        // The last element in mainQueue = the most recently pushed = stack top.
        while (mainQueue.size() > 1) {
            helperQueue.offer(mainQueue.poll());
        }

        // Step 2: The one remaining element in mainQueue is our stack top.
        int stackTop = mainQueue.poll();

        // Step 3: Swap references — helperQueue becomes the new mainQueue.
        // This avoids copying all elements back; we just swap which name points where.
        Queue<Integer> temp = mainQueue;
        mainQueue  = helperQueue;
        helperQueue = temp;
        // helperQueue is now empty and ready for the next pop operation.

        return stackTop;
    }

    /**
     * Look at the top element without removing it.
     * Time Complexity: O(n) — same drain-and-restore process as pop.
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty — nothing to peek at");
        }
        // Drain all but the last element
        while (mainQueue.size() > 1) {
            helperQueue.offer(mainQueue.poll());
        }

        // Peek at the stack top (last remaining in mainQueue)
        int stackTop = mainQueue.peek();

        // Move the top element to helperQueue as well, then swap
        // so ALL elements are preserved after peek.
        helperQueue.offer(mainQueue.poll());

        Queue<Integer> temp = mainQueue;
        mainQueue  = helperQueue;
        helperQueue = temp;
        // After swap, mainQueue has all elements back but in reversed order — that's fine,
        // because peek doesn't change the logical stack state.

        return stackTop;
    }

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

    public int size() {
        return mainQueue.size();
    }

    // ─── Main: Demonstrate the internal state at each step ───────────────────
    public static void main(String[] args) {
        StackUsingQueuePopHeavy stack = new StackUsingQueuePopHeavy();

        System.out.println("=== Pop-Heavy Strategy Demo ===");
        System.out.println();

        stack.push(10);
        System.out.println("Pushed 10  | mainQueue: " + stack.mainQueue);

        stack.push(20);
        System.out.println("Pushed 20  | mainQueue: " + stack.mainQueue);

        stack.push(30);
        System.out.println("Pushed 30  | mainQueue: " + stack.mainQueue);
        // Queue is in FIFO order: [10, 20, 30] — 30 is at the rear (stack top)

        System.out.println();
        System.out.println("Peek (top of stack): " + stack.peek()); // Should be 30
        System.out.println("mainQueue after peek: " + stack.mainQueue); // All elements intact

        System.out.println();
        System.out.println("--- Popping all elements (should be LIFO: 30, 20, 10) ---");
        while (!stack.isEmpty()) {
            System.out.println("Popped: " + stack.pop());
        }

        System.out.println();
        System.out.println("Stack is empty: " + stack.isEmpty());
    }
}

package io.thecodeforge.stack;

/**
 * A test harness that runs BOTH implementations against identical
 * inputs and confirms they produce identical LIFO output.
 * Run this to verify both strategies work correctly.
 */
import java.util.LinkedList;
import java.util.Queue;

public class StackOperationsTest {

    // ── Minimal Push-Heavy Stack (self-contained for testing) ──────────────
    static class PushHeavyStack {
        private Queue<Integer> queue = new LinkedList<>();

        public void push(int value) {
            queue.offer(value);
            for (int i = 0; i < queue.size() - 1; i++) {
                queue.offer(queue.poll());
            }
        }
        public int pop()  { return queue.poll(); }
        public int peek() { return queue.peek(); }
        public boolean isEmpty() { return queue.isEmpty(); }
    }

    // ── Minimal Pop-Heavy Stack (self-contained for testing) ───────────────
    static class PopHeavyStack {
        private Queue<Integer> mainQueue   = new LinkedList<>();
        private Queue<Integer> helperQueue = new LinkedList<>();

        public void push(int value) { mainQueue.offer(value); }

        public int pop() {
            while (mainQueue.size() > 1) helperQueue.offer(mainQueue.poll());
            int top = mainQueue.poll();
            Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp;
            return top;
        }

        public int peek() {
            while (mainQueue.size() > 1) helperQueue.offer(mainQueue.poll());
            int top = mainQueue.peek();
            helperQueue.offer(mainQueue.poll());
            Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp;
            return top;
        }

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

    // ── Test Runner ────────────────────────────────────────────────────────
    public static void main(String[] args) {
        int[] valuesToPush = {5, 15, 25, 35, 45};

        PushHeavyStack pushHeavy = new PushHeavyStack();
        PopHeavyStack  popHeavy  = new PopHeavyStack();

        // Push the same values into both stacks
        for (int value : valuesToPush) {
            pushHeavy.push(value);
            popHeavy.push(value);
        }

        System.out.println("Both stacks loaded with: [5, 15, 25, 35, 45]");
        System.out.println("Expected LIFO pop order:  45, 35, 25, 15, 5");
        System.out.println();

        System.out.printf("%-20s %-20s %-10s%n", "Push-Heavy Pop", "Pop-Heavy Pop", "Match?");
        System.out.println("-".repeat(52));

        boolean allMatch = true;
        while (!pushHeavy.isEmpty() && !popHeavy.isEmpty()) {
            int fromPushHeavy = pushHeavy.pop();
            int fromPopHeavy  = popHeavy.pop();
            boolean match = (fromPushHeavy == fromPopHeavy);
            if (!match) allMatch = false;

            System.out.printf("%-20d %-20d %-10s%n",
                fromPushHeavy, fromPopHeavy, match ? "✓" : "✗ MISMATCH");
        }

        System.out.println("-".repeat(52));
        System.out.println("All results match: " + allMatch);
    }
}