JavaScript Data Structure and Algorithms

2018-03-06

Stack

  • We will cover the following topics
    • The Stack data Structure
    • Adding elements to a stack
    • Popping elements from a stack
    • How to use the Stack class
    • The decimal to binary problem

  • Stack Data structure

    • First In Last Out
    • variable items is private and only accessible to the Stack function
    • this approach creates a copy of the variable items for each class instance created. Therefore, it does not escalate well in case we need to use several instances of the Stack class at the same time
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      function Stack(){
          let items = [];
          this.push = function(element){
              items.push(element);
          };
          this.pop = function(){
              return items.pop();
          };
          this.peek = function(){
              return items[items.length - 1];
          };
          this.isEmpty = function(){
              return items.length == 0;
          };
          this.size = function(){
              return items.length;
          };
          this.clear = function(){
              items = [];
          };
          this.print = function(){
              console.log(items.toString());
          }
      }

  • ES 6

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Stack {
        constructor(){ this.items = []; }
        push(element){
            this.items.push(element);
        }
        pop(){
            return this.items.pop();
        }
        peek(){
            return this.items[items.length - 1];
        }
        isEmpty(){
            return this.items.length == 0;
        }
        size(){
            return this.items.length;
        }
        clear(){
            this.items = [];
        }
        print(){
            console.log(this.items.toString());
        }
    }

  • ES6 with Symbol property

    • The symbol property is not a private property
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      let _items = Symbol();

      class Stack2 {

          constructor () {
              this[_items] = [];
          }

          push(element){
              this[_items].push(element);
          }

          pop(){
              return this[_items].pop();
          }

          peek(){
              return this[_items][this[_items].length-1];
          }

          isEmpty(){
              return this[_items].length == 0;
          }

          size(){
              return this[_items].length;
          }

          clear(){
              this[_items] = [];
          }

          print(){
              console.log(this.toString());
          }

          toString(){
              return this[_items].toString();
          }
      }
      let stack = new Stack2();
      stack.push(5);
      stack.push(1);
      let objectSymbols = Object.getOwnPropertySymols(stack);
      stack[objectSymbols[0]].push(1); // forbidden

  • ES6 classes with WeakMap

    • With this approach, it is not possible to inherit the private properties if we extend this class.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      const items = new WeakMap();

      class Stack {
          constructor(){
              items.set(this, []);
          }
          push(element){
              let s = items.get(this);
              s.push(element);
          }
          pop(){
              let s = items.get(this);
              return s.pop();
          }
          peek(){
              let s = items.get(this);
              s[s.length - 1];
          }
          isEmpty(){
              let s = items.get(this);
              return s.length === 0;
          }
          size(){
              let s = items.get(this);
              return s.length;
          }
          clear(){
              items.set(this, []);
          }
      }

  • items variable is still declared outside the Stack class, so anyone can change it. We will wrap the Stack class with a closure

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    let Stack = (function(){
        const items = new WeakMap();
        class Stack {
            constructor(){
                items.set(this, []);
            }
            push(element){
                let s = items.get(this);
                s.push(element);
            }
            pop(){
                let s = items.get(this);
                return s.pop();
            }
            peek(){
                let s = items.get(this);
                return s[s.length - 1];
            }
            isEmpty(){
                let s = items.get(this);
                return s.length === 0;
            }
            size(){
                let s = items.get(this);
                return s.length;
            }
            clear(){
                items.set(this, []);
            }
        }
        return Stack;
    })();

  • Decimal to Binary

    • Convert Decimal Number to Binary Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function divideBy2(decNumber){
    var remStack = new Stack(),
    rem,
    binaryString = '';

    while (decNumber > 0){
        rem = Math.floor(decNumber % 2);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / 2);
    }

    while (!remStack.is(Empty())){
        binaryString += remStack.pop().toString();
    }
    return binaryString;
}
  • Base Converter
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function baseConverter (decNumber, base){
        var remStack = new Stack(), rem, baseString = '', digits = '0123456789ABCDEF';
        while (decNumber > 0){
            rem = Math.floor(decNumber % base);
            remStack.push(rem);
            decNumber = Math.floor(decNumber / base);
        }
        while (!remStack.isEmpty()){
            baseString += digits[remStack.pop()];
        }
        return baseString;
    }