Data structure – stack

A directory

What’s the difference between a free front end and a salted fish

The preface

Returns the directory

Classic Opening: What is a stack?

A stack is an ordered collection that follows LIFO.

Don’t understand? Here’s an example:

• You have a pile of books, the first one is at the bottom, and if there are so many books that you can’t get to the bottom book, if you want to get to the bottom book, you have to move the last one every time so that you can get to the bottom book.
• In the kitchen stack, take the dishes on top and the bottom of the stack last.

There are two array methods: push() and pop().

Yes, suppose we have an array:

• const arr = [1, 2, 3, 4];

If we need to stack inside, we add elements through arr.push() and push elements out through arr.pop().

Of course, the simulation stack is more than these methods, we continue to look at ~

Three simulation implementation stack

Returns the directory

First, declare some methods for the stack:

• push(element): Adds one or more elements to the top of the stack
• pop(): Removes the element at the top of the stack and returns it
• peek(): View the element at the top of the stack
• isEmpty(): Checks whether the stack is empty and returns if it istrueOtherwise returnfalse
• clear(): Clears all elements in the stack
• size: Returns the number of elements in the stack, methods andlengthsimilar

Then, we try to implement these methods:

Implementation code:

function Stack() {
  let items = [];
  this.push = function(element) {
    items.push(element);
  };
  this.pop = function() {
    const pop = items.pop();
    return pop;
  };
  this.peek = function() {
    return items[items.length - 1];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
}

let stack = new Stack();
stack.push(1);
// stack: [1]

stack.pop();
// stack: []

stack.push(1);
stack.push(2);
// stack: [1, 2]

stack.peek();
// Console: 2

stack.isEmpty();
// Console: false

stack.clear();
// stack: []

stack.size();
/ / 0
Copy the code

Of course, if you only read jsliang’s articles without pictures or videos, you will be easily confused. Here Jsliang suggests reading articles of various leaders or further understanding through several cases in the following chapters:

• How do I implement a stack manually in JavaScript
• Algorithms and Data Structures in JS — Stack

Quad conversion algorithm

Returns the directory

If you’ve ever gone through college, you’ve probably run into an old professor who tells you to convert from decimal to binary.

If you haven’t heard of it yet, jsliang is here to introduce you

4.1 Converting from decimal to binary

Returns the directory

How does it go from base 10 to base 2?

• Base 10 to base 2

5% 10% 2 = 0 | 10/2 = 5 2 = 1 | 5/2 = 2% 2 = 0 | 2/2 = 1 2 = 1 1/2 = | 0 1%Copy the code

In this case, base 10 is converted to base 2 to become 1010.

• Base 10 25 to base 2

25% 2 = 1 | 25/2 = 12 12% 2 = 0 | 12/2 = 6 2 = 0 6% 3% 2 = 3 = 1 | | 6/2 3/2 = 1 2 = 1 1/2 = | 0 1%Copy the code

Here, base 25 of 10 is converted to base 2 to 11001.

So, here’s the decryption:

1. We know that the base 10 is zeron.
2. Place n at the bottom of the stack for each mod of 2.
3. Take n divided by 2 as the number for the next loop (round down, leaving out decimal places).
4. Repeat steps 2 and 3 until n equals 0.
5. The stack values are extrapolated in order to obtain the final result.

With that said, look at the code:

const decimalToBinary = (num) = > {
  const result = [];
  while (num > 0) {
    result.push(num % 2);
    num = Math.floor(num / 2);
  }
  return result.reverse().join(' ');
};

console.log(decimalToBinary(10)); / / '1010'
console.log(decimalToBinary(25)); / / '11001'
Copy the code

Is it So easy

Of course, in order to prevent confusion, we can also modify:

const decimalToBinary = (num) = > {
  const stack = [];
  let result = ' ';
  while (num > 0) {
    stack.push(num % 2);
    num = Math.floor(num / 2);
  }
  for (let i = stack.length - 1; i >= 0; i--) {
    result += stack[i];
  }
  return result;
};

console.log(decimalToBinary(10)); / / '1010'
console.log(decimalToBinary(25)); / / '11001'
Copy the code

So, we’re done converting from decimal to binary

4.2 Any base conversion up to decimal and 16

Returns the directory

So, since this works so well, can we change it to decimal and convert it to any base up to hexadecimal?

The answer is yes.

@param {Number} Number Specifies the Number to be converted to. @param {Number} binarySystem specifies the Number to be converted to
const arbitraryBaseConversion = (number, binarySystem) = > {
  const stack = [];
  const digits = '0123456789ABCDEF';
  while (number > 0) {
    stack.push(digits[Math.floor(number % binarySystem)]);
    number = Math.floor(number / binarySystem);
  }
  return stack.reverse().join(' ');
}

console.log(arbitraryBaseConversion(10.2)); / / '1010'
console.log(arbitraryBaseConversion(100.2)); / / '1100100'
console.log(arbitraryBaseConversion(10.16)); // 'A'
console.log(arbitraryBaseConversion(100.16)); / / '64'
Copy the code

In this way, we complete the decimal to hexadecimal arbitrary base method ~

Five balanced parentheses

Returns the directory

Let’s try balancing parentheses again:

Leetcode-cn.com/problems/va…

Given one that only includes'('.') '.'{'.'} '.'['.'] 'To determine whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string. Example 1: Enter:"()"Output:trueExample 2: Enter:"[the] {} ()"Output:trueExample 3: Enter:"(]"Output:falseExample 4: Enter:"([]"Output:falseExample 5: Enter:"{[]}"Output:true
Copy the code

If you want to try it yourself, you can try the code below:

/** * @param {string} s * @return {boolean} */
var isValid = function(s) {};Copy the code

How do you do that with stacks?

/** * @name balanced parentheses * @param {string} s * @return {Boolean} */
const isValid = (s) = > {
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    if (
      (s[i] === ') ' && stack[stack.length - 1= = ='(')
      || (s[i] === '] ' && stack[stack.length - 1= = ='[')
      || (s[i] === '} ' && stack[stack.length - 1= = ='{')
    ) {
      stack.pop();
    } else{ stack.push(s[i]); }}console.log(stack);
  return stack.length === 0;
};

console.log(isValid('()'));     // true
console.log(isValid('[] {} ()')); // true
console.log(isValid('(]'));     // false
console.log(isValid('(/)'));   // false
console.log(isValid('{[]}'));   // true
Copy the code

Case 1

Take ()[]{} for example:

1. judge(Not close parentheses, so push the stack,stack = [ '(' ];
2. judge)Closed parentheses, so push out the stack,stack = [];
3. judge[Not close parentheses, so push the stack,stack = [ '[' ];
4. judge]Closed parentheses, so push out the stack,stack = [];
5. judge{Not close parentheses, so push the stack,stack = [ '{' ];
6. judge}Closed parentheses, so push out the stack,stack = [];

Finally, stack.length is 0, so it is true.

Case 2

Take ([)] again for example:

1. judge(Not close parentheses, so push the stack,stack = [ '(' ];
2. judge[Not close parentheses, so push the stack,stack = [ '(', '[' ];
3. judge)It’s closing parentheses, but the top element of the stack is[Rather than(, so still push the stack,stack = [ '(', '[', ')' ];
4. judge]It’s closing parentheses, but the top element of the stack is)Rather than[, so still push the stack,stack = [ '(', '[', ')', ']' ];

Finally, stack.length is 4, so it is false.

Thus, we learn more about the form of the stack by balancing the parentheses.

Six summarize

Returns the directory

After base conversion and balance parentheses these two topics, presumably friends should have a deeper understanding of stack.

Of course, we still have some problems not solved, such as: Hannotta and so on, but because jsliang did not find the corresponding topic (only hannotta description), so here is not trembling, next time we meet and add here.

Do not toss the front end, and what is the difference between salted fish!

Jsliang will update a LeetCode problem every day, so as to help friends consolidate the foundation of native JS, understand and learn algorithms and data structures.

Prodigal Excalibur will update the interview questions every day to drive everyone to study, keep learning and thinking every day, and make progress every day!

Scan the qr code above, pay attention to the jsliang public account (left) and prodigal Son Excalibur public account (right), let us toss together!

Jsliang document library 由 Liang JunrongusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on theGithub.com/LiangJunron…On the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.