Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, it’s still good to summarise here

1. Stacks

Last In First Out

Linked-list Implementation

Maintain a pointer to the first item of the linked-list. Add or remove are simply to update that pointer.

class Node {
  item: string;
  next: Node;

  constructor(item: string, next: Node) {
    this.item = item;
    this.next = next;
  }
}

class Stack {
  first: Node;

  push = (item: string): void => {
    const oldFirst = this.first;
    this.first = new Node(item, oldFirst);
  }

  pop = (): string => {
    const item = this.first.item;
    this.first = this.first.next;
    return item;
  }
}

Array Implementation

• Use array s[] to store N items on stack
• push(): add new item at s[N]
• pop(): remove item from s[N-1]

Resizing-array Implementation

• Start with array size 1
• push(): double size of array when full and copy all items
• pop(): halve size of array when array is one-quarter full

Amortized time (average time): constant because we access the item directly in the array, only slow when double size of array, but we won’t do it very frequently. It happen lgN times.

One interesting thing I found is that Golang slices is implemented this way (from what I read from the Go book), but yeah, I have to check again to make sure because I have never worked with Go yet.

Comparison

Linked-list implementation

• Every operation takes constant time in the worst case
• Uses extra time and space to deal with the links.

Resizing-array implementation

• Every operation takes constant amortized time
• Less wasted space

Actually, Resizing-array implementation will be helpful a lot in implementing a randomized queue. See below

2. Queues

First In First Out

Linked-list Implementation

Maintain 2 pointers to the first and last items of the linked-list. Enqueue or dequeue are simply to update those pointers

class Node {
  item: string;
  next: Node;
}

class Queue {
  first: Node;
  last: Node;

  enqueue = (item: string): void => {
    const oldLast = this.last;
    this.last = new Node();
    this.last.item = item;
    this.last.next = null;
    if (isEmpty()) this.first = this.last;
    else oldLast.next = this.last;
  }

  dequeue = (): string => {
    const item = this.first.item;
    this.first = this.first.next;
    if (isEmpty()) last = null;
    return item;
  }
}

Array Implementation

• Use array q[] to store items in queue
• Use 2 pointers to store the index of head and tail
• enqueue(): add new item at q[tail]
• dequeue(): remove item from q[head]
• The index can goes out of the array range. Use modulo to get the correct index.
• Apply resizing array like Stack’s Array Implementation

3. Double-Ended Queues - Deques

A double-ended queue or deque (pronounced “deck”) is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure.

By using a doubly linked-list, we can achieve constant worst-case time for all the Deque operation (including constructor). The sample working implementation can be found here.

4. Randomized Queues

A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure.

An Resizing-Array implementation supports each randomized queue operation a constant amortized processing time. The implementation is the same as the Queue’s Resizing Array Implementation. To enqueue, we still add new item at q[tail]. The only difference is the dequeue method. To dequeue, we will pick a random item in the array, move the last item into that position and return that random item. The sample working implementation can be found here.

5. Stack with Max

Stack with Max is another data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. To implement that, simply use 2 stacks, one to store all the items just like the Stack implementation above, the other one to store the maximum values.

class Node {
  item: number;
  next: Node;
}

class MaxStack {
  // ...similar to stack implementation

  // for maxStack
  max: Node;

  getMax = (): number => this.max.item;

  push = (item: number): void => {
    // ...similar to stack implementation

    // store max value
    if (item > this.getMax()) {
      const oldMax = this.max;
      this.max = new Node();
      this.max.next = oldMax;
    }
  }

  pop = (): number => {
    // ...similar to stack implementation

    if (tmp === this.getMax()) {
      this.max = this.max.next;
    }
    return tmp;
  }
}