The SDET Playbook

← All questions

Implement a stack and a queue in TypeScript, and test their invariants

Asked Sep 28, 2026Viewed 0 times

1 Answer

Sign in to answer and to vote.

  • 0
    The SDET PlaybookSep 28, 2026

    A stack is last in, first out (browser back history); a queue is first in, first out (steps waiting to run). An array is a fine stack, but Array.prototype.shift() moves every remaining element, so a queue built on it takes O(n) per dequeue. Keeping a head index makes it O(1):

    export class Stack<T> {
      private items: T[] = [];
      push(item: T): void { this.items.push(item); }
      pop(): T | undefined { return this.items.pop(); }
      peek(): T | undefined { return this.items.at(-1); }
      get size(): number { return this.items.length; }
    }
    
    export class Queue<T> {
      private items: T[] = [];
      private head = 0;
      enqueue(item: T): void { this.items.push(item); }
      dequeue(): T | undefined {
        if (this.head === this.items.length) return undefined;
        const item = this.items[this.head++];
        if (this.head > 1024 && this.head * 2 > this.items.length) {
          this.items = this.items.slice(this.head); // drop consumed slots now and then
          this.head = 0;
        }
        return item;
      }
      get size(): number { return this.items.length - this.head; }
    }
    

    Test the behavior that defines each structure, not just one happy path:

    import { describe, expect, it } from 'vitest';
    import { Queue, Stack } from './collections';
    
    describe('Stack', () => {
      it('returns items in reverse order', () => {
        const s = new Stack<number>();
        [1, 2, 3].forEach((n) => s.push(n));
        expect([s.pop(), s.pop(), s.pop()]).toEqual([3, 2, 1]);
      });
      it('is safe when empty', () => {
        const s = new Stack<number>();
        expect(s.pop()).toBeUndefined();
        expect(s.size).toBe(0);
      });
    });
    
    describe('Queue', () => {
      it('returns items in insertion order across interleaved calls', () => {
        const q = new Queue<string>();
        q.enqueue('a'); q.enqueue('b');
        expect(q.dequeue()).toBe('a');
        q.enqueue('c');
        expect([q.dequeue(), q.dequeue(), q.dequeue()]).toEqual(['b', 'c', undefined]);
      });
      it('keeps order and size through compaction', () => {
        const q = new Queue<number>();
        for (let i = 0; i < 5000; i++) q.enqueue(i);
        for (let i = 0; i < 4000; i++) expect(q.dequeue()).toBe(i);
        expect(q.size).toBe(1000);
        expect(q.dequeue()).toBe(4000);
      });
    });
    

    The second queue test targets the one tricky branch, compaction, which a small happy-path test never reaches. Point that out: choosing tests from the code's risky paths is the skill being assessed.

    Sources: MDN: Array.prototype.shift(), Vitest