Stacks and Queues

Updated: 01 February 2024

Stacks and Queues

  • Collections of objects
  • Some simple operations: insert, remove, iterate, and test if empty
  • Two ways we may modofy data:
    • Stack - pop and push (LIFO)
    • Queue - enqueue and dequeue (FIFO)

Modular Programming

For the purpose of these types of data structures we want to completely separate the details of implementation from the specific client that we want to use. We want to design our libraries so that clients can choose different implementations and allows us to focus on performance where we would like to

Bags, Queues, and Stacks

Stack

A stack stores some data, and should have the following interface:

algorithms/stack/definition.ts
1
export interface Stack<T> {
2
  push(value: T): void;
3
  pop(): T | undefined;
4
  empty(): boolean;
5
  size(): number;
6
}

Linked List

Considering the above, we can implement this using a few different methods. For the first implement this using a linked list:

algorithms/stack/linked-list.ts
1
import { type Stack } from './definition'
2


3
interface Item<T> {
4
  value: T
5
  next?: Item<T>
6
}
7


8
const getSize = <T>(item?: Item<T>, count: number = 0): number => {
9
  if (!item) {
10
    return count
11
  }
12


13
  const innerSize = getSize(item.next, count + 1)
14
  return innerSize
15
}
16


17
export class LinkedListStack<T> implements Stack<T> {
18
  private first?: Item<T> = undefined
19


20
  push(value: T): void {
21
    const oldFirst = this.first
22


23
    this.first = {
24
      value,
25
      next: oldFirst,
26
    }
27
  }
28


29
  pop(): T | undefined {
30
    const item = this.first
31


32
    this.first = item?.next
33


34
    return item?.value
35
  }
36


37
  empty(): boolean {
38
    return this.first === undefined
39
  }
40


41
  size(): number {
42
    return getSize(this.first)
43
  }
44
}

In this case pushing and popping is a constant time operation

Array

And using an array:

algorithms/stack/fixed-size-array.ts
1
import type { Stack } from "./definition";
2


3
export class FixedSizeArrayStack<T> implements Stack<T> {
4
  private stack: Array<T>;
5
  private n = 0;
6


7
  constructor(capacity = 10) {
8
    this.stack = new Array<T>(capacity);
9
  }
10


11
  push(value: T): void {
12
    this.stack[this.n] = value;
13
    this.n++;
14
  }
15


16
  pop(): T | undefined {
17
    this.n--;
18
    const item = this.stack[this.n];
19


20
    return item;
21
  }
22


23
  empty(): boolean {
24
    return this.n === 0;
25
  }
26


27
  size(): number {
28
    return this.n;
29
  }
30
}

Note that we have used the non-trivial implementation to demonstrate the general concept since in Javascript the builtin array type does everything we would need anyway. As a general note in array based implementations is that we need to consider that an array has a specific capacity that will need to be accounted for when pusing or popping elements. Even though this isn’t really something we need to consider in Javascript the implementation assumes a bit of a more general concept of how arrays work

Considerations

  • Underflow: We probably want to throw if a client tries to pop from an empty stack
  • Overflow: We can use a resizing array to handle this and not require the client to provide us with a capacity
  • Loitering: Currently we still hold a reference to popped items in the stack, we can update our implementation to replace that reference in our array to better handle this

Resizing Arrays

To resize our array we will need to do some kind of copy every time we want to extend our array. Since copying an array is expensive we want to avoid having to do this too frequently. One strategy for choosing when to do this is called repeated doubling in which once we have filled the array we create a new array that is double the size of our old array and copy all the items into that

algorithms/stack/resizing-array.ts
1
import type { Stack } from "./definition";
2


3
export class ResizingArrayStack<T> implements Stack<T> {
4
  private stack: Array<T>;
5
  private n = 0;
6


7
  constructor() {
8
    this.stack = new Array<T>(1);
9
  }
10


11
  push(value: T): void {
12
    if (this.full()) {
13
      this.resize();
14
    }
15


16
    this.stack[this.n] = value;
17
    this.n++;
18
  }
19


20
  pop(): T | undefined {
21
    this.n--;
22
    const item = this.stack[this.n];
23


24
    return item;
25
  }
26


27
  empty(): boolean {
28
    return this.n === 0;
29
  }
30


31
  size(): number {
32
    return this.n;
33
  }
34


35
  private full() {
36
    return this.n >= this.stack.length;
37
  }
38


39
  private resize(): void {
40
    const size = this.size();
41
    const newStack = new Array(size * 2);
42


43
    for (let i = 0; i < this.stack.length; i++) {
44
      newStack[i] = this.stack[i];
45
    }
46


47
    this.stack = newStack;
48
  }
49
}

In this implementation the cost of inserting an item is N for cases where we are inserting a single item but may be some power of 2 for cases where we are inseting an item that is in a position outside of the current array. Overall however this cost becomes something that we need to pay less frequently as N grows and overall the cost of inserting the first N items comes to be around 3N. This idea of averaging out these costs is called the amortized cost

In the above implementation we do not resize shrink the array when the array is half full since we can end up in a situation where the consumer frequently pushes or pops value around this mark which will cause frequent array resizes and will be very expensive. A bit of a more general solution to this could be to wait until the array is a quarter full and then resize it to half the size which will help avoid some of this resizing

Tradeoffs

  • Linked-list
    • Every operation takes constant time in the worst case
    • Extra time and space for dealing with links
  • Rezing array
    • Every operation takes a constant amortized time
    • Less wasted space

Queue

The definition of a Queue looks very similar to the Stack but the enqueue and dequeue operations work slightly differently

Linked List

In a linked-list implementation we add items at the start of the list and remove them from the end

From an implementation standpoint we also need to keep track of the last and first item in the list

algorithms/queue/linked-list.ts
1
import { type Queue } from "./definition";
2


3
interface Item<T> {
4
  value: T;
5
  next?: Item<T>;
6
}
7


8
const getSize = <T>(item?: Item<T>, count: number = 0): number => {
9
  if (!item) {
10
    return count;
11
  }
12


13
  const innerSize = getSize(item.next, count + 1);
14
  return innerSize;
15
};
16


17
export class LinkedListQueue<T> implements Queue<T> {
18
  private first?: Item<T> = undefined;
19
  private last?: Item<T> = undefined;
20


21
  queue(value: T): void {
22
    const newNode = {
23
      value,
24
    };
25


26
    if (this.last) {
27
      this.last.next = newNode;
28
    }
29


30
    if (this.first === undefined) {
31
      // if nothing in queue then init to input item
32
      this.first = newNode;
33
    }
34


35
    this.last = newNode;
36
  }
37


38
  dequeue(): T | undefined {
39
    const item = this.first;
40


41
    this.first = item?.next;
42


43
    if (this.first === undefined) {
44
      // if nothing in queue then we should remove ref to last item
45
      this.last = undefined;
46
    }
47


48
    return item?.value;
49
  }
50


51
  empty(): boolean {
52
    return this.first === undefined;
53
  }
54


55
  size(): number {
56
    return getSize(this.first);
57
  }
58
}

Iterators

An iterator is a data structure that implements the iterator and iterable interfaces in the respective language. This enables us to work with in loops and other language specific functionality

Javascript Definition

In Javascript, the relevant definitions look like so:

1
interface IteratorYieldResult<TYield> {
2
  done?: false
3
  value: TYield
4
}
5


6
interface IteratorReturnResult<TReturn> {
7
  done: true
8
  value: TReturn
9
}
10


11
type IteratorResult<T, TReturn = any> =
12
  | IteratorYieldResult<T>
13
  | IteratorReturnResult<TReturn>
14


15
interface Iterator<T, TReturn = any, TNext = undefined> {
16
  next(...args: [] | [TNext]): IteratorResult<T, TReturn>
17
}
18


19
interface Iterable<T> {
20
  [Symbol.iterator](): Iterator<T>
21
}
22


23
interface IterableIterator<T> extends Iterator<T> {
24
  [Symbol.iterator](): IterableIterator<T>
25
}

Range Iterator

For the purpose of our example, we can implement an iterator that will iterate over a range

algorithms/iterator/range.ts
1
class RangeIterator implements Iterator<number, number, number> {
2
  current: number;
3
  constructor(
4
    readonly start: number,
5
    private readonly end: number,
6
    private readonly step: number
7
  ) {
8
    // step back so we can include the initial value
9
    this.current = start - this.step;
10
  }
11


12
  next(): IteratorResult<number> {
13
    const outOfBounds = this.current > this.end;
14
    const canNotIterate = this.current + this.step > this.end;
15


16
    const isDone = outOfBounds || canNotIterate;
17


18
    if (isDone) {
19
      return {
20
        // this return value will be ignored as the iterator is done
21
        value: undefined,
22
        done: true,
23
      };
24
    }
25


26
    this.current += this.step;
27
    return {
28
      value: this.current,
29
      done: false,
30
    };
31
  }
32
}
33


34
export class Range implements Iterable<number> {
35
  constructor(
36
    private readonly start: number,
37
    private readonly end: number,
38
    private readonly step = 1
39
  ) {}
40


41
  [Symbol.iterator]() {
42
    return new RangeIterator(this.start, this.end, this.step);
43
  }
44
}

Bag

In some cases we don’t particularly care about the sequencing but we just want t be able to add items and iterate throught the items that we added in any order - this is called a bag. The interface for how we can define a bag looks like such:

algorithms/iterator/bag.ts
1
export interface Bag<T> extends Iterable<T> {
2
  add(item: T): void;
3
  size(): number;
4
}

Applications

Lots of languages have the functionality that we discussed above but the reason you may want to implement your own is because these implementations try to address a lot of general cases but may not meet specific requirements that you require for your implementation, for example builtin library code may compromise between read and write operations for a list which may cause a read-heavy algorithm to be very slow unlike a more specialized implementation which can be designed to have more specific performance characteristics to the problem at hand

Dijkstra’s two stack algorithm

THe two stack algorithm for arithmetic operation can be used to evaluate infix expressions. The algorithm is as follows:

Given some input set of strings: ( 1 + ( 2 + 3 ) * ( 4 + 5 ) - 6 ) we can evaluate the result using the following process:

  1. Define two stacks
  • Value stack
  • Operator stack
  1. Iterate over all items
  • If value - push onto value stack
  • If Operator - push onto operator stack
  • If left paren - ignore
  • If right paren - pop two values, pop one operator, and apply the operator, put result onto value stack

The implementation can be seen below:

algorithms/stack/dijkstras-two-stack-arithmetic.ts
1
import { ResizingArrayStack } from "./resizing-array";
2


3
const operate = {
4
  "+": (a: number, b: number) => a + b,
5
  "-": (a: number, b: number) => a - b,
6
  "*": (a: number, b: number) => a * b,
7
  "/": (a: number, b: number) => a / b,
8
};
9


10
type Operator = keyof typeof operate;
11


12
const isDefined = <T>(val: T | undefined): val is T => val !== undefined;
13


14
const openParen = "(";
15
const closeParen = ")";
16


17
export const twoStackArithmetic = (strs: string[]) => {
18
  const values = new ResizingArrayStack<number>();
19
  const operators = new ResizingArrayStack<Operator>();
20


21
  for (const str of strs) {
22
    switch (str) {
23
      case openParen:
24
        break;
25


26
      case "+":
27
      case "-":
28
      case "*":
29
      case "/":
30
        operators.push(str);
31
        break;
32


33
      case closeParen:
34
        const b = values.pop();
35
        const a = values.pop();
36
        const op = operators.pop();
37


38
        const valid = isDefined(a) && isDefined(b) && isDefined(op);
39


40
        if (!valid) throw new Error("Invalid state");
41
        const result = operate[op](a, b);
42


43
        values.push(result);
44
        break;
45


46
      default:
47
        const value = parseInt(str);
48
        values.push(value);
49
        break;
50
    }
51
  }
52


53
  return values.pop();
54
};