Summarize these two days to learn about stacks in JS data structures

Do not learn, do not know, a learn startled. You can use the idea of data structures to implement algorithms that can reduce the time complexity from O(n^2) to O(1), although it is just some array API encapsulation

Why learn data structures

1. Are languages connected

I often hear many seniors say that programming languages are the same, and if you master one, it is easy to master other languages. However, I personally think that each language has its own advantages and disadvantages, and each language has its own strengths and weaknesses, and each language has its own strengths and weaknesses. For example, Node.js, which allows front-end engineers to step into the back-end field, is only used as the middle layer in many companies, and can’t really replace the back-end like Java and C. For example, the machine language Python, such a nearly universal language, in the face of high-performance computing, the use of many Python libraries, the bottom is also C language implementation. Therefore, I think what is really connected is not language, but data structure and algorithm. Data structures and algorithms exist independently of programming languages, different languages have different implementations, but the inherent logic will not change, the reflected programming ideas will not change.

2. A personal experience

In the previous interview, I went to a company that offered online courses. At that time, both the written test and the first two aspects were relatively smooth, but when it came to the final interview with the department head, I was confused. The boss was a former senior engineer at Baidu, with a background in computer science, with a special focus on data structures and algorithms. After a few pleasantries began to enter the theme, (the beginning of the nightmare) after seeing my pen test questions, asked me why this quick row write so? I was writing ruan Yifeng teacher’s version, I did not speak, and then asked me, you do not know that this writing will not only increase the time complexity, even space complexity will consume it? My meng circle shook his head, and then asked me, you know heap sort? I again meng circle shook his head, and then asked me, do you know time complexity? I helplessly shook his head; How can you know if your code is good or bad if you don’t even know the most basic data structure? If you encounter a bug that someone can solve in half an hour, you may spend two hours… After a deep education, I went out to talk with HR. The final result was that I got the offer, but the level was low and the money was also low. I always thought the front has nothing to do with data structures and algorithms, they can realize the business function, but after this interview, I broke before the point of view, and even write business, also have to write a good also have write general, a nested loop before, each layer increase the time complexity of a class, so I decided to start learning data structures and algorithms.

3. Learn the goals of the data structure

Data structure is to summarize the essence of refined many of the storage management and use of data model, behind these patterns is the essence of programming ideas, these ideas of understanding need time, don’t take it for granted that learned several data structures can play an important role in the work, but learned to data structures, is self-evident to the promotion of their own capabilities.

Let’s get to the point

Data structure — stack

1. Stack definition

A stack is a special linear table, which can only be operated on one end of the linear table. Operations are allowed at the top of the stack, but not at the bottom of the stack. Stack features: first in, last out (last in, first out).

The following figure shows how the stack works

A stack is, in a sense, like an open box, in which the thing that goes in first is always pushed under by the thing that goes in later, so if you want to take out the thing that’s stuck, you have to take out the top thing first, which is the thing that goes in later.

Just like the badminton bucket in our daily life

2. Realization of stack

From the point of view of data storage, there are two ways to realize the stack, one is based on the array, one is based on the linked list, array is the simplest way to achieve the stack, this paper to the basic array.

The basic operations of the stack include creating the stack, destroying the stack, removing the stack, loading the stack, getting the top element of the stack, getting the size of the stack, and emptying the stack.

We define the following stack methods:

  • Push adds an element to the top of the stack (adds a badminton to the bucket)
  • Pop Top stack element (take a badminton ball from the top of the bucket)
  • Top returns the element at the top of the stack (look at the badminton at the top of the bucket, but don’t take it out)
  • IsEmpty checks whether the stack isEmpty (see if it runs out of shuttlecock)
  • Size returns the number of elements in the stack (count how many shuttlecocks are left in the bucket)
  • Clear the stack (empty the shuttlecock out of the bucket and throw it away)

Then we use the es6 class implementation of the above method to create a stack.js file

class Stack {
  constructor() { this.items = []; // Use array to store data} push(item) {this.items. Push (item); // push an element onto the stack}pop() {
    returnthis.items.pop(); // Remove the top element from the stack}top() {
    returnthis.items[this.items.length - 1]; // return the top element}isEmpty() {
    returnthis.items.length === 0; // return if the stack is empty}size() {
    returnthis.items.length; // return the stack size}clear() { this.items = []; // Clear stack}}Copy the code

After reading the above code, you may be surprised to find that the stack implemented here is only a layer of array encapsulation.

Is it just a layer of encapsulation?

  • Given an array, you can index any element, but given a stack, can you manipulate any element? The stack only allows you to operate on the element at the top of the stack, which is the last element in the array, and this limitation actually gives us a way to think about it, which is the nature of the stack, last in, first out.
  • Since the bottom implementation of stack is actually an array, what stack can do, array can also do ah, why create a stack, is not redundant? Encapsulation is for better use, and it’s much easier to think on the shoulder of a stack than on the shoulder of an array, as you’ll see in the exercises below.
3. Stack application

Tell me about an interview question I met before. Give me a string and determine whether the parentheses in it come in pairs

Ss () () ss (SSS (ss) (ss) ss) legal

Ss () () ss (SSS (ss) (ss) ss)) is not legal

If we use the method of array or object, we can also solve this problem. Today we will try to use stack to solve this problem.

  • Traversal string
  • If it’s an open parenthesis, it’s pushed onto the stack
  • If it is a close bracket, check whether the stack is empty. If it is not, remove the top element of the stack (that is, the left bracket in the stack), and the parentheses cancel out. If it is not empty, the left parenthesis is missing and false is returned
  • At the end of the loop, see if the stack size is 0. If it is not 0, there are no pairs, and if it is 0, it all cancels out.

3.1.3 using the stack to analyze whether it is very simple, look at the code implementation

{
       function isDouuble(str) {
          const stack = new Stack();
          const len = str.length;
          for (let i = 0; i < len; i++) {
            const item = str[i];
            if (str[i] === "(") { stack.push(item); / / into the stack}else if (item === ")") {
              if (stack.isEmpty()) {
                return false;
              } else{ stack.pop(); }}}return stack.size() === 0;
        }
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss)")); // true
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss)(")); // false
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss))")); // false
        console.log(isDouuble("()ss()ss(sss(ss)(ss)ss))(")); // false
      }
Copy the code

3.2.1 Implement a stack of MIN methods

Implement a stack that, in addition to the common push and pop methods, provides a min method that returns the smallest element in the stack with o(1) time.

The analysis can be realized by using two stacks, one for storing data, the other for storing the smallest data in the stack; Using the idea of divide and conquer in programming, you want to do it separately

  • Define two stacks, dataStack and minStack;
  • For dataStack stack, normal PSUH, POP implementation is fine;
  • The minStatck stack is supposed to store the smallest value in the stack, so when the minStack is empty, the data pushed in is the smallest. If it is not empty, then the element at the top of the minStack is the smallest. If the element is smaller than the element at the top of the stack, just push it in, so that the top of the minStack is always the smallest in the stack.

3.2.3 Code Implementation (time complexity is O(1))

 {
        class MinStack {
          constructor() { this.dataStack = new Stack(); This.minstack = new Stack(); Push (item) {this.datastack.push (item); this.datastack.push (item); // General operationif(this.minStack.isEmpty() || item < this.minStack.top()) { this.minStack.push(item); // Make sure the minStack top is the smallest value}else{ this.minStack.push(this.minStack.top()); // Keep both stacks the same size}}pop() {
            this.minStack.pop();
            returnthis.dataStack.pop(); // Return the real number}min() {
            returnthis.minStack.top(); }} const minstack = new MinStack();
        minstack.push(3);
        minstack.push(2);
        minstack.push(6);
        minstack.push(8);
        console.log(minstack.min()); // 2
        console.log(minstack.pop()); // 8
        minstack.push(1);
        console.log(minstack.min()); // 1
      }
Copy the code
4. Stack summary

It doesn’t matter whether the bottom layer of the stack uses an array or not. What matters is that the last in, first out feature of the stack is that we can only operate on the top element of the stack. We must ignore how the bottom layer of the stack is implemented, and only care about the properties of the stack.