JS data structure & Algorithm learning – stack

“This is the seventh day of my participation in the First Challenge 2022.

Hi, here is the pig bully with Teacher Coderwhy JS data structure learning summary, the New Year more to teach ducks!

Learning portal:

• JS Data Structure & Algorithm learning – Concept Portal
• JS data structure & Algorithm learning – Array portal
• JS data structure & algorithm learning – stack text!
• JS data structure & Algorithm learning – queue to summarize
• JS data structure & Algorithm learning — Linked list to be summarized
• JS data Structure & Algorithm learning — Bidirectional linked list to be summarized
• JS data Structure & Algorithm learning — Set to be summarized
• JS data structure & Algorithm learning — Hash table to be summarized
• JS data structure & Algorithm learning — Red black tree to be summarized
• Waiting to learn!!

The stack

In contrast to arrays, stacks are constrained linear structures

concept

Why is a stack a restricted data structure? Unlike arrays, there is no limit to what we can do if we want to delete or insert an element in an array, but a stack is limited because of its structure.

If we want to remove the middle element, we need to remove the element above it before removing the target element. For this feature, we call it LIFO. We have two terms for stack operation:

0. Push: Add a new element to the top of the stack
1. Unstack: Remove the top element of the stack

Application of life

0. Stacked plates: If we want to reach the middle of a stack of plates, we need to move the top plate to get the plate we want
1. Cars in a parking lot: If the parking lot is full of cars and you want to move your car, you need to move other cars out of the way to make way for your car

Program application (function stack)

Function A calls function B, function B calls function C and function C calls function D

0. A Push into the stack (unfinished)
1. A calls B to push B onto the stack
2. And so on
3. D The stack is removed
4. C The execution completes and the stack is removed
5. And so on

PS: Recursion is prone to stack overflow

The stack structure

We can usually implement the stack structure using linked lists and arrays

0. Stack packaging structure:

   Var stack = new stack() stack.psuh() function stack(){this.items = [] // stack()} var stack = new stack() stack.psuh()Copy the code

   Because the class in JS is based on the object, we encapsulate a stack class, in which we can define the attributes and methods of the stack. After encapsulation, we can realize the operation of loading and unloading the stack mentioned above by calling it.

1. Operating encapsulation

   Here we have two encapsulation methods, one is to add methods for object instances, the other is to add methods for classes through prototypes, we generally use prototypes to encapsulate, save memory

   This.push = function() {// Stack. Prototype. Push = function(element) {}Copy the code

   Add top element to stack: Use the push method for stack encapsulation

   Stack.prototype.push = function (element) {
       this.items.push(element)
   }
   Copy the code

   Remove the top element from the stack: Use the pop() method to wrap the element

   Stack.prototype.pop = function () {
       return this.items.pop()
   }
   Copy the code

   View top stack element: Return the top stack element by calling the length of the array

   Stack.prototype.peek = function () {
       return this.items[this.items.length - 1]
   }
   Copy the code

   Nulling: Stack nulling is also done by the length of the array

   Stack.prototype.isEmpty = function () {
       return this.items.length === 0
   }
   Copy the code

   Take the stack length

   Stack.prototype.size = function () {
       return this.items.length
   }
   Copy the code

   Stack conversion string: through the declaration of string variables, the stack traversal, through the characteristics of JS string, string concatenation, and finally return its string

   Stack.prototype.toString = function (element) {
       var reString = ''
       for(let i = 0; i < this.items.length; i++){
           reString += this.items[i] + ''
       }
       return reString
   }
   Copy the code

use

1. To push 1,20 onto a stack of [1,20]

   Stack. Push (1) stack. Push (20), the console. The log (stack)Copy the code

2. If I take the top of the stack at this point the top of the stack is 20, so I return 20

   console.log(stack.peek())
   Copy the code

3. Concatenating stack elements returns a value of 120, which concatenates stack elements

   console.log(stack.toString())
   Copy the code

Decimal – > binary DE conversion

Decimal and binary conversion is a common operation in computers. Let’s first understand how they are converted

For example: 100(base 10) conversion

100/2 = 50 residual 0, 50/2 = 25 residual 0, 25/2 = 12 residual 1, 12/2 = 6 residual 0, 6/2 = 3 residual 0, 3/2 = 1, residual 1, 1/2 = 0 residual 1

You get 1100100, which is the result of converting the decimal number 100 to binary

So now that we know how decimal to binary works, we can encapsulate decimal to binary according to the properties of the stack

function TtoT(tNumber) {
    var stack = new stack
    while (tNumber > 0) {
        stack.push(tNumber%2)
        iNumber = Math.floor(tNumber/2)
    }
    return stack.UtoString
}
Copy the code

We according to the properties of the stack into after the first, to transform digital transformation, push the conversion Numbers for the remainder of a division 2, and through the variable to hold the result of the current to get ready for the next calculation, finally get to we converted stack, of course we can put our above the toString method of encapsulation, it upside down, A string that yields binary results.

Stack.prototype.UtoString = function (element) {
    var reString = ''
      for (let i = this.items.length; i > 0; i--) {
        reString += this.items[i - 1] + ''
      }
      return reString
}
Copy the code