/**
 * A Stack Based Queue Implementation.
 * The Queue data structure which follows the FIFO (First in First Out) rule.
 * The dequeue operation in a normal stack based queue would be o(n), as the entire has to be shifted
 * With the help of two stacks, the time complexity of this can be brought down to amortized-O(1).
 * Here, one stack acts as an Enqueue stack where elements are added.
 * The other stack acts as a dequeue stack which helps in dequeuing the elements
 */

import { Stack } from "../stack/stack";
import { Queue } from "./queue";

export class StackQueue<T> implements Queue<T> {
    private enqueueStack: Stack<T> = new Stack<T>();
    private dequeueStack: Stack<T> = new Stack<T>();

    /**
     * Returns the length of the Queue
     *
     * @returns {number} the length of the Queue
     */
    length(): number {
        return this.enqueueStack.length() + this.dequeueStack.length();
    }

    /**
     * Checks if the queue is empty.
     *
     * @returns {boolean} Whether the queue is empty or not.
     */
    isEmpty(): boolean {
        return this.enqueueStack.isEmpty() && this.dequeueStack.isEmpty();
    }

    /**
     * Adds an item to the queue.
     * We always add a new item to the enqueueStack.
     * @param item The item being added to the queue.
     */
    enqueue(item: T): void {
        this.enqueueStack.push(item);
    }

    /**
     * Shifts the elements from the enqueueStack to the dequeueStack
     * In the worst case, all the elements from the enqueue stack needs to shifted, which needs O(n) time.
     * However, after the shift, elements can de dequeued at O(1).
     * This helps in dequeuing the elements in amortized O(1) time.
     */
    private shift(): void {
        while (!this.enqueueStack.isEmpty()) {
            const enqueueStackTop = this.enqueueStack.pop();
            this.dequeueStack.push(enqueueStackTop);
        }
    }

    /**
     * Removes an item from the queue and returns it.
     *
     * @throws Queue Underflow if the queue is empty.
     * @returns The item that was removed from the queue.
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow");
        }

        if (this.dequeueStack.isEmpty()) {
            this.shift();
        }

        return this.dequeueStack.pop();
    }

    /**
     * Returns the item at the front of the queue.
     *
     * @returns The item at the front of the queue or null if the queue is empty.
     */
    peek(): T | null {
        if (this.isEmpty()) {
            return null;
        }

        if (this.dequeueStack.isEmpty()) {
            this.shift();
        }

        return this.dequeueStack.top();
    }
}