This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

📢 Hello everyone, I am Xiao Cheng, a sophomore front-end enthusiast

📢 This article explains stacks in data structures

📢 Thank you very much for reading

📢 May you be true to yourself and love life

💡 content preview

  • What is a stack?
  • What are the methods of stack structure
  • Implementing a stack
  • LeetCodeIn actual combat

📢 twitter

This article will summarize the first data structure you’ll learn: the stack. The use of the stack in the front end is also very extensive, such as: function call stack, base conversion, valid parentheses these issues are involved in the stack structure let’s take a look

What is the stack structure?

A stack is a special kind of linear list that can be implemented as an array or linked list. It’s usually implemented as an array, but it’s very different from an array. In the case of arrays, we can take an element from the array at will, and we can insert an element anywhere in the array. But for the stack structure, compared to the array, it only allows fetching and inserting operations at the top of the stack. Therefore, the stack has the characteristics of first in, last out

Figure, you can visualize a stack structure

It’s like a bucket in life. You can only put things in through the top and take things out through the top

In life there are many examples, such as: loaded badminton ball bucket, we can only take the top of the badminton, on the top

So there’s a top of a stack and a bottom of a stack

The top of the stack can be visually understood as the mouth of the barrel

The bottom of the stack could be the bottom of the bucket

In JS, the familiar execution context also uses the stack structure to maintain, the bottom of the stack is the global scope (GO), the execution context of the current executing code is successively added to the stack, the element on the top of the stack is always the execution context object.

What are the methods of stack structure?

Just like the general data structure, it has insert and remove methods, we call them: on and off the stack to enrich the methods in the stack, we implement some more, for example, to determine whether the top of the stack is empty, return the number of elements in the stack, empty the stack, return the top of the stack element

methods meaning
push() Add a new element to the top of the stack
pop() Removes the top element of the stack and returns the removed element
peek() Returns the top element of the stack without changing the stack
isEmpty() Check whether the stack is empty
clear() Removes all elements from the stack
size() Returns the number of elements in the stack

Let’s implement each of them

👇 👇 👇

Three, handwritten implementation of a stack structure

Here I use the array to realize the stack this data structure, because the JS array encapsulates a large number of native API, through these API is very convenient to achieve our function

1. Create a Stack class

Let’s start by creating a class class and using stackData arrays to store our data

class Stack {
  constructor() {
    this.stackData = []; }}Copy the code

2. Implement push method

And the way to do that, that’s the advantage of using an array because of the stack rules, we can only add at the top of the stack, which is the last bit of the array, which corresponds to the push method of the array so the way to do that is to call the push method of the array

push(element) {
    this.stackData.push(element)
}
Copy the code

3. Implement pop methods

And the way to get out of the stack, based on last in, first out, is to get the top element of the stack, which is equivalent to getting the last bit of the array so we can use the pop method of the array to do that

The pop method deletes the last bit of the array and returns the deleted value

pop() {
    this.stackData.pop()
}
Copy the code

The implementation of the stack and the stack, a simple stack structure has been basically implemented, let’s try it

First we need to create a new object example, and then call the appropriate method to demonstrate this

const stack = new Stack()
stack.push(9)
stack.push(4)
stack.pop()
stack.push(6)
Copy the code

Effect of dynamic figure

You can see that each time you add an element to the end of the array, when you pop, you pop the element from the end of the array

4. Implement peek method

Peek looks at the top element of the stack, the last element of the array, and does not change the stack

The implementation method is also very simple, we just return the last bit of the array

peek() {
    return this.stackData[this.stackData.length - 1]}Copy the code

Use the PEEK method

const stack = new Stack()
stack.push(9)
stack.peek() / / 9
Copy the code

5. Implement the size method

Size method: returns the number of elements in the stack, that is, the length of the array

size() {
    return this.stackData.length
}
Copy the code

Call size

const stack = new Stack()
stack.push(9)
stack.push(4)
stack.size() / / 2
Copy the code

6. Implement isEmpty

IsEmpty: checks to see if there is a value in the current stack, and returns true if it isEmpty

Let’s just make a judgment about length

isEmpty() {
    return !this.stackData.length
}
Copy the code

Use the isEmpty method

const stack = new Stack()
stack.push(9) 
stack.isEmpty()  // false is not null
Copy the code

7. Implement clear method

Clear method: clear the stack, that is, reset the stack

clear() {
    this.stackData = []
}
Copy the code

8. Complete stack structure

class Stack {
    constructor() {
        this.stackData = []
    }
    / / into the stack
    push(element) {
        this.stackData.push(element)
    }
    / / out of the stack
    pop() {
        this.stackData.pop()
    }
    // Get the top of stack
    peek() {
        return this.stackData[this.stackData.length - 1]}// Check if it is null
    isEmpty() {
        return !this.stackData.length
    }
    / / empty stack
    clear() {
        this.stackData = []
    }
    // Returns the number of elements
    size() {
        return this.stackData.length
    }
}
Copy the code

LeetCode actual combat

20. Valid brackets

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

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.

This is a classic problem, and we can use last-in, first-out of the stack, because we need the left and right parentheses to match

  • When we encounter an open parenthesis, we push that parenthesis onto the stack
  • When we encounter a close parenthesis, we need to determine whether the current top of the stack matches the parenthesis
  • If yes, the system continues to iterate. If no, the system returnsfalse
  • There is also a special case when the input stringsIs the length of theAn odd numberIt is impossible to satisfy the question

So we can write code

var isValid = function (s) {
    // Create a new stack
    const stack = [];
    // If the type of the parenthesis matches the type of the parenthesis at the top of the stack, it will be removed from the stack
    for (let i = 0; i < s.length; i++) {
        // If it is odd, pop false
        if (s.length % 2= = =1) {
            return false
        }
        const c = s[i];
        // An open parenthesis push is encountered
        if (c === '(' || c === '{' || c === '[') {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1]
            if (
                (t === '(' && c === ') ')||
                (t === '[' && c === '] ')||
                (t === '{' && c === '} ')
            ) {
                stack.pop()
            } else {
                return false}}; }return stack.length === 0
}
Copy the code

📖 summary

  1. Using arrays to encapsulate a stack structure
  2. Understand the basic method of stack structure
  3. Have a better understanding of data structures

That concludes this article about stacks, and I’m sure you’ll learn a lot from it. The next article will take you through the mysteries of queues

You are welcome to follow this column and stay tuned for the latest articles

Finally, I may not be clear enough in many places, please forgive me

💌 if the article has any mistakes, or have any questions, welcome to leave a message, also welcome private letter exchange