Queues: A Tale of Two Stacks

Queues: A Tale of Two Stacks.ts

interface IQueue {
  put(value: number): void;
  pop(): void;
  peek(): number | null;
}

class Stack implements IQueue {
  private _stack: number[] = [];

  put(value: number): void {
    this._stack.push(value);
  }

  pop(): void {
    this._stack.shift();
  }

  peek(): number | null {
    const [first = null] = this._stack;

    return first;
  }
}

class Queue implements IQueue {
  private _queue: number[] = [];

  put(value: number): void {
    this._queue.unshift(value);
  }

  pop(): void {
    this._queue.pop();
  }

  peek(): number | null {
    const [last = null] = this._queue.slice(-1, this._queue.length);

    return last;
  }
}

class Resolver {
  private _methodMap = new Map<number, keyof IQueue>([
    [1, "put"],
    [2, "pop"],
    [3, "peek"],
  ]);

  private _mapQuery(queryNumber: number): keyof IQueue | undefined {
    return this._methodMap.get(queryNumber);
  }

  get output(): number[] {
    return this._queries
      .map(([queryNumber, arg]) => {
        try {
          const method = this._mapQuery(queryNumber);

          return method === "put" ? this._queue[method](arg) : this._queue[method]();
        } catch (error) {
          return null;
        }
      })
      .filter(Boolean) as number[];
  }

  constructor(private _queries: number[][], private _queue: IQueue) {}

  static fifo(queries: number[][]) {
    return new Resolver(queries, new Queue()).output;
  }

  static lifo(queries: number[][]) {
    return new Resolver(queries, new Stack()).output;
  }

  static sanitizeInput(queries: string): number[][] {
    return queries
      .split("\n")
      .filter(Boolean)
      .map((str) => str.trim())
      .map((str) => str.split(" ").map((str) => +str));
  }
}

const input = `
  10
  1 42
  2
  1 14
  3
  1 28
  3
  1 60
  1 78
  2
  2
`;

const queries = Resolver.sanitizeInput(input);

console.log(Resolver.lifo(queries));
console.log(Resolver.fifo(queries));