I’ve already read the depth-first traversal section of graphs in the Subway book Learning JavaScript Data Structures and Algorithms, so I’m now reviewing the source code for each data structure in TypeScript. Source code reference from the author’s Github repository.

A Stack is an ordered collection that follows the Last In First Out (LIFO) principle. New elements added or to be removed are stored at the same end of the stack, called the top, and the other end is called the bottom. In the stack, the new elements are near the top of the stack, and the old elements are near the bottom of the stack.

The data structure

A stack should have several operations as follows:

  • push(element): pushes a new element to the top of the stack.
  • pop(): Removes the top element from the stack and returns the removed element.
  • peek(): returns the element at the top of the stack without modifying the stack.
  • isEmpty(): Whether the stack is empty.
  • clear(): Removes all elements in the stack.
  • size(): Returns the number of elements in the stack.
  • toString(): overrides the default toString method of Object

Array implementation

A stack is a lot like an incomplete array that can only be accessed from one end. So Array is the easiest stack data structure to implement.

export default class StackArray<T> {
  // The Array to store
  private items: T[];

  constructor() {
    this.items = [];
  }

  / * * *@description: stack *@param {T} Element The element to be pushed */
  push(element: T) {
    this.items.push(element);
  }

  / * * *@description: the stack *@return {T} Returns the stack element */
  pop(): T {
    return this.items.pop();
  }

  / * * *@descriptionReturns the element * at the top of the stack@return {T}* /
  peek(): T {
    return this.items[this.items.length - 1];
  }

  / * * *@description: returns whether the stack is empty *@return {Boolean}* /
  isEmpty(): boolean {
    return this.items.length === 0;
  }

  / * * *@description: Returns the number of elements in the stack *@return {Number}* /
  size(): number {
    return this.items.length;
  }

  / * * *@description: Empty the stack */
  clear() {
    this.items = [];
  }

  / * * *@description: overrides the Object default toString *@return {String}* /
  toString(): string {
    return this.items.toString(); }}Copy the code

Map implementation

When using arrays, most methods have O(n) time complexity. In the worst case, finding an element requires iterating through all positions in the array, so better performance can be achieved if you use a dictionary Map to store all stack elements directly.

export default class Stack<T> {
  // The stored Map
  private items: Map<number, T>;

  //
  constructor() {
    this.items = new Map(a); }/ * * *@description: stack *@param {T} Element The element to be pushed */
  push(element: T) {
    this.items.set(this.items.size, element);
  }

  / * * *@description: the stack *@return {T} Returns the stack element */
  pop(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.get(this.items.size - 1);
    this.items.delete(this.items.size - 1);
    return result;
  }

  / * * *@descriptionReturns the element * at the top of the stack@return {T}* /
  peek(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.get(this.items.size - 1);
  }

  / * * *@description: returns whether the stack is empty *@return {Boolean}* /
  isEmpty(): boolean {
    return this.items.size === 0;
  }

  / * * *@description: Returns the number of elements in the stack *@return {Number}* /
  size(): number {
    return this.items.size;
  }

  / * * *@description: Empty the stack */
  clear() {
    this.items.clear();
  }

  / * * *@description: overrides the Object default toString *@return {String}* /
  toString(): string {
    if (this.isEmpty()) {
      return ' ';
    }
    let result: string = ' ';
    this.items.forEach((value, key) = > {
      result = `${result}${key === 0 ? ' ' : ', '}${value}`;
    });
    returnresult; }}Copy the code

The relevant algorithm

The practical application of stack is very extensive. For example, when Javascript is running, a stack is used to store variables and method calls, and you see this call stack every time you debug and report errors. The following uses the stack to implement two classical algorithms.

Hexadecimal conversion

To convert a decimal number to base N, we can divide the decimal number by N and round the quotient until the result is 0. For example, to convert the decimal number 8039 to an n-base number, the algorithm is as follows:

Therefore, a stack can be used to store the remainder. Each remainder is pushed into the stack, and the remainder is removed from the stack one by one when the result is extracted. The algorithm is as follows:

/ * * *@description: Converts a decimal number to the corresponding base *@param {Number} DecNumber Number to convert *@param {Number} Base The base to convert to *@return {String} Returns the numeric text */ in base
function baseConverter(decNumber: number, base: number) :string {
  / / remainder stack
  const remStack = new Stack<number> ();// A maximum of 10 digits and 26 letters can be expressed in base 36
  const digits: string = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  let rem: number;
  let baseString: string = ' ';

  if(! (2 <= base && base <= 36)) {
    return ' ';
  }

  // Common base arithmetic
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base);
    // Each iteration pushes the remainder to the stack
    remStack.push(rem);
    decNumber = Math.floor(decNumber / base);
  }

  while(! remStack.isEmpty()) {// Each iteration pushes the remainder off the stack
    baseString += digits[remStack.pop()];
  }

  return baseString;
}
Copy the code

Under test:

console.log(baseConverter(8039.32)); // output => 7R7
console.log(baseConverter(8039.16)); // output => 1F67
console.log(baseConverter(8039.8)); // output => 17547
console.log(baseConverter(8039.2)); // output => 1111101100111
Copy the code

Hanoi

The Tower of Hanoi originates from an Indian legend. When Maha Ma created the world, he built three diamond pillars, one of which was stacked with 64 gold disks from bottom to top. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns. According to this legend, abstract mathematical problems:

There are three rods A, B and C. Rod A has N (N>1) perforated disks, the size of the disk from bottom to top decreasing. All disks are required to be moved to C rod according to the following rules:

  • You can only move one disk at a time;
  • The large plate cannot be placed on top of the small plate;

How to move? What’s the minimum number of moves? The algorithm here sees several wonderful answers in Zhihu: How to understand hannotta recursion? . In general, the algorithm is divided into four steps by mathematical induction, as shown in the figure below:

First look at state B, where the largest plate is in the starting tower and all smaller plates are in the auxiliary tower. What should be done now is to move the largest plate from the starting tower to the target tower, so:

  • Before performing this step, all you need to do is move any smaller dishes from the starting tower to the auxiliary tower;
  • After performing this step, all you need to do is move any smaller dishes from the auxiliary tower to the target tower;

The result is a recursion in which each tower can only be moved in and out from the top, so it can be perfectly abstracted by a stack. The algorithm is as follows:

import Stack from '.. /data-structures/stack';
{name: string, stack: stack}
interface Tower {
  name: string;
  stack: Stack<number>;
}

[Map
      
       ]
      ,>
type Moves = Array<Map<string.string> >;/ * * *@description: Moving plate recursive method *@param {number} Plates Number of plates to be moved *@param {Tower} Source Indicates the start tower of the move *@param {Tower} Helper The helper tower for this movement *@param {Tower} Dest Indicates the end tower of the movement *@param {Moves} Moves Ends the array of steps * for the last move@return {Moves} Returns the array of post-move steps */
const hanoiStackRecur = (
  plates: number.source: Tower,
  helper: Tower,
  dest: Tower,
  moves: Moves = []
): Moves= > {
  // Handle the corner situation
  if (plates <= 0) {
    return moves;
  }
  // Baseline conditions
  if (plates === 1) {
    // Either the first or the last step is simply to move the smallest plate from the starting tower of the current turn to the target tower
    dest.stack.push(source.stack.pop());
    const move = new Map<string.string> (); move.set(source.name, source.stack.toString()); move.set(helper.name, helper.stack.toString()); move.set(dest.name, dest.stack.toString()); moves.push(move); }else {
    /** * First remember that the initial state of this turn is as follows: * Starting tower: plates * Auxiliary tower: first 1 to plates-1 plates * Target tower: No plates less than or equal to plates */
    // Previous tasks of this turn: move the first 1 to plates-1 from the starting tower to the auxiliary tower
    hanoiStackRecur(plates - 1, source, dest, helper, moves);
    // Turn task: Move the current largest plate from the start tower to the target tower
    dest.stack.push(source.stack.pop());
    // 👇 simply record the step, adding the current step to the step array
    const move = new Map<string.string> (); move.set(source.name, source.stack.toString()); move.set(helper.name, helper.stack.toString()); move.set(dest.name, dest.stack.toString()); moves.push(move);/ / 👆
    // Mission after this turn: move the first 1 to plates-1 from the auxiliary tower to the target tower
    hanoiStackRecur(plates - 1, helper, source, dest, moves);
  }
  return moves;
};

/ * * *@description: Hannotta algorithm *@param {number} Plates Number of plates to be moved *@return {Moves} Returns an array of all movement steps */
export function hanoiStack(plates: number) :Moves {
  // Initializes the starting tower, auxiliary tower, and destination tower
  const source: Tower = { name: 'source'.stack: new Stack<number>() };
  const dest: Tower = { name: 'dest'.stack: new Stack<number>() };
  const helper: Tower = { name: 'helper'.stack: new Stack<number>() };

  // Push a specified number of plates to the start tower
  for (let i = plates; i > 0; i--) {
    source.stack.push(i);
  }

  // Call recursive methods
  return hanoiStackRecur(plates, source, helper, dest);
}
Copy the code

Test the calculation results of the next 5 dishes:

[
  Map { 'source'= >'5, 4, 3, 2'.'helper'= >' '.'dest'= >'1' },
  Map { 'source'= >'5, 4, 3'.'dest'= >'1'.'helper'= >'2' },
  Map { 'dest'= >' '.'source'= >'5, 4, 3'.'helper'= >'2, 1' },
  Map { 'source'= >'5, 4'.'helper'= >'2, 1'.'dest'= >'3' },
  Map { 'helper'= >'2'.'dest'= >'3'.'source'= >'5, 4, 1' },
  Map { 'helper'= >' '.'source'= >'5, 4, 1'.'dest'= >'3, 2' },
  Map { 'source'= >'5, 4'.'helper'= >' '.'dest'= >'3, 2, 1' },
  Map { 'source'= >'5'.'dest'= >'3, 2, 1'.'helper'= >'4' },
  Map { 'dest'= >'3, 2'.'source'= >'5'.'helper'= >'4, 1' },
  Map { 'dest'= >'3'.'helper'= >'4, 1'.'source'= >'5, 2' },
  Map { 'helper'= >'4'.'dest'= >'3'.'source'= >'5, 2, 1' },
  Map { 'dest'= >' '.'source'= >'5, 2, 1'.'helper'= >'4, 3' },
  Map { 'source'= >'5, 2'.'helper'= >'4, 3'.'dest'= >'1' },
  Map { 'source'= >'5'.'dest'= >'1'.'helper'= >'4, 3, 2' },
  Map { 'dest'= >' '.'source'= >'5'.'helper'= >'4, 3, 2, 1' },
  Map { 'source'= >' '.'helper'= >'4, 3, 2, 1'.'dest'= >'5' },
  Map { 'helper'= >'4, 3, 2'.'dest'= >'5'.'source'= >'1' },
  Map { 'helper'= >'4, 3'.'source'= >'1'.'dest'= >'5, 2' },
  Map { 'source'= >' '.'helper'= >'4, 3'.'dest'= >'5, 2, 1' },
  Map { 'helper'= >'4'.'dest'= >'5, 2, 1'.'source'= >'3' },
  Map { 'dest'= >'5, 2'.'source'= >'3'.'helper'= >'4, 1' },
  Map { 'dest'= >'5'.'helper'= >'4, 1'.'source'= >'3, 2' },
  Map { 'helper'= >'4'.'dest'= >'5'.'source'= >'3, 2, 1' },
  Map { 'helper'= >' '.'source'= >'3, 2, 1'.'dest'= >'5, 4' },
  Map { 'source'= >'3, 2'.'helper'= >' '.'dest'= >'5, 4, 1' },
  Map { 'source'= >'3'.'dest'= >'5, 4, 1'.'helper'= >'2' },
  Map { 'dest'= >'5, 4'.'source'= >'3'.'helper'= >'2, 1' },
  Map { 'source'= >' '.'helper'= >'2, 1'.'dest'= >'5, 4, 3' },
  Map { 'helper'= >'2'.'dest'= >'5, 4, 3'.'source'= >'1' },
  Map { 'helper'= >' '.'source'= >'1'.'dest'= >'5, 4, 3, 2' },
  Map { 'source'= >' '.'helper'= >' '.'dest'= >'5, 4, 3, 2, 1'}]Copy the code

Front-end notepad, not regularly updated, welcome to pay attention to!

  • Wechat official account: Lin Jingyi’s notepad
  • Blog: Lin Jingyi’s notebook
  • Nuggets column: Lin Jingyi’s notebook
  • Zhihu column: Lin Jingyi’s notebook
  • Github: MageeLin