The stack profile

What is a stack? The stack is a last in, first out (LIFO) data structure. What does a stack do? Stacks can simulate algorithms or lifo scenarios, such as:

  • To convert from decimal to binary, you need to print the remainder in reverse order.
  • The stack is used for middle and then non-recursive traversal of binary trees.
  • In life, stack can simulate coal stove and briquettes and other scenes.

There is no need for JavaScript engineers to implement a stack in development. Because JavaScript’s built-in Array object already implements stack-related methods. However, good programmers can’t just use what others have designed and not understand why, so let’s design a stack of our own.

function Stack(){... }module.exports = Stack;
Copy the code

Private variables

The stack class’s private variable is an array of items, which records the elements of the stack. Objects generated by stack class instantiation cannot manipulate items directly, because items are not visible outside the function. You can only manipulate items indirectly along the scope chain through some class method.

function Stack() {
  // Private variable items, used to record arrays, objects cannot be manipulated directly
  var items = [];
}
Copy the code

Implement push, POP and toString methods and run the following tests:

// Instantiate a stack object
  const stack = new Stack();

  // Expect the stack to be empty
  expect(stack.isEmpty()).toBeTruthy()

  stack.push(4)
  stack.push(7)

  // Expect stack to delete and return 7
  expect(stack.pop()).toBe(7)

  // Expect stack to convert to string '4'
  expect(stack.toString()).toBe('4')

Copy the code

The push, POP, and toString methods are the same as the Array push, POP, and toString methods, so the implementation code is as follows:

function Stack() {
  // The private items variable is used to record arrays and cannot be manipulated directly
  let items = [];
  // The class method push, which adds elements to the end of the array, can be called directly
  this.push = function (element) {
    items.push(element);
  }
  // Remove and return the element at the end of the array
  this.pop = function (element) {
    return items.pop()
  }
  // Convert the array to a string and return it
  this.toString = function () {
    return items.toString()
  }
}
Copy the code

Implement peek, isEmpty, clear, size methods implement peek, isEmpty, clear, size methods, and pass the following tests

    stack.push(6)
  // Expect the last element of the stack to be 6
  expect(stack.peek()).toBe(6)
  // Expect a stack length of 2
  expect(stack.size()).toBe(2)
  // Expect the stack not to be empty
  expect(stack.isEmpty()).toBeFalsy()

  stack.clear()
  // Expect the stack length to be 0
  expect(stack.size()).toBe(0)
Copy the code

The above method is relatively simple, directly on the code:

function Stack() {
  // Private variable items, used to record arrays, objects cannot be manipulated directly
  var items = [];
  
  // Look at the last item in the array
  this.peek = function () {
    return items[items.length - 1];
  };
  // Check whether the array is empty
  this.isEmpty = function () {
    return items.length == 0;
  };
  // Empty the array
  this.clear = function () {
    items = [];
  };
  // Return the length of the array
  this.size = function () {
    return items.length;
  };
}
Copy the code

Example code: github.com/gin280/java…