Stack: how to realize the judgment of valid brackets?

author | The way of immeasurable testing edit | Small Fine

Valid brackets , Brush over LeetCode Yes, maybe I'm familiar with this problem .

1. Opening question ： Valid parenthesis [1]

If I ask you to solve this problem now , What kind of solution will you think of ？

That's what we're going to talk about today “ Stack ” This data structure . With this question , Let's learn today's content .

2. How to understand “ Stack ”？

About stacks , There is a very appropriate game -- Hanoi . When playing this game , We all put them one by one from bottom to top ; When I pick it up , We also take... One by one from top to bottom , You can't pull it out of the middle . First in, first out , The advanced come out later , That's typical “ Stack ” structure .

From the operational characteristics of the stack , Is a kind of the stack “ Operation is restricted ” The linear table , Insert and delete data only at one end . Definition of stack [2]： Stack （stack） Also known as the stack , It's an operationally constrained linear table . A linear table limited to insert and delete operations only at the end of the table . This end is called the top of the stack , relatively , Call the other end the bottom of the stack . Inserting a new element into a stack is also called a push 、 Push or push , It's putting a new element on top of the top of the stack , Make it the new top element ; Removing an element from a stack is also called making a stack or backing a stack , It removes the top element of the stack , Make its adjacent elements the new top of the stack .

3. How to implement stack

From the definition of stack just now , We can see that , The stack consists of two main operations , Push and pull , That is to insert a data at the top of the stack and delete a data from the top of the stack . After understanding the definition of stack , Let's take a look at how to code a stack .

【 This article USES the swift Language to write code , Readers, don't be afraid of difficulties because of different programming languages , What matters is thinking and logic , Language is just a way of expression . You can express your logic in your own familiar language , Try to write first 】

Talking is cheap,show you the code.

class Stack {
    // Initialize array 
    var datas = [Int]()
    // The stack, 
    func pop() -> Int? {
        return datas.popLast()
    }
    // Into the stack, 
    func push(obj: Int) {
        datas.append(obj)
    }
    // Stack top object 
    func top() -> Int? {
        return datas.last
    }
}

Copy

4. The application of stack in the actual development process

• Stack application in function call

func calculate() {
    let a = 3
    let b = 5
    var result = 0
    result = add(x: a, y: b)
    print(result)
}

func add(x: Int, y: Int) -> Int {
    var sum= 0
    sum = x + y
    return sum
}

Copy

We can see that from the code ,calculate() The function is called add() function , Pass in temporary variables a and b, Get calculation results , Finally print result Value .

In order to let you clearly see the function stack corresponding to this process 、 Stack operation , I drew a picture . The figure shows , In carrying out the add() Function time , Function call stack .

• recursive

In the algorithm, , One idea that is often used is recursive thinking . The famous Fibonacci sequence [3]

F(0) =0,F(1) =1,F(n) = F(n-1)+F(n-2)（n≥2,n∈N*）

Calculation F(n) You need to calculate first F(n-1) and F(n-2) Calculation F(n-1) You need to calculate first F(n-2) and F(n-3) Calculation F(n-2) You need to calculate first F(n-2) and F(n-3) ··· The final effect is , There will be many intermediate values pushed into the stack , That's why , When n Very big time , It will consume a lot of memory . So in actual development , Master these underlying development foundations , It will help you choose the right technical solution .

5. Conceptual differentiation ： Data structure stack VS Stack in memory

When learning the basics of computer , We know that there are stack areas and heap areas in memory . What's the difference between it and the stack in the data structure , Are they the same concept ？

Stack in memory and Data structure stack It's not a concept , It can be said that the stack in memory is the real physical area , The stack in a data structure is an abstract data storage structure .

Memory space is logically divided into three parts ： Code section 、 Static data area and dynamic data area , Dynamic data area is divided into stack area and heap area .

Code section ： Binary code to store method body . Advanced scheduling （ Job scheduling ）、 Intermediate dispatch （ Memory scheduling ）、 Low level scheduling （ Process scheduling ） Control code area to execute code switching .

Static data area ： Store global variables 、 Static variables 、 Constant , Constants include final Modifier constants and String Constant . The system automatically allocates and recycles .

The stack area ： Store parameters of run method 、 local variable 、 Return value . Automatically allocated and recycled by the system .

Heap area ：new The reference or address of an object is stored in the stack area , Point to the real data that the object stores in the heap .

6. The beginning of the answer

Okay , I think now you have fully understood the concept of stack . Let's go back to the thinking question at the beginning , How to realize the judgment of valid brackets ？ In fact, using the idea of stack can perfectly solve this problem .

We started to analyze ：

• 1. If it starts with a right parenthesis )、]、}, Obviously illegal , Go straight back to false
• 2. If it's left parenthesis (、[、{, Just press the stack . If it's right bracket )、]、}, stay stack Match with the top element of the stack if there is a value , If the match passes, the element at the top of the stack will be out of the stack , Otherwise go straight back to false.

Here is swift Problem solving implementation code

class Solution {
      
    func isValid(_ s: String) -> Bool {
        
        if s.count == 0  { return false }
        var stack = [String]()
        let dict: [String:String] = ["(":")","[":"]","{":"}"]
        
        for c in s {
            if dict.keys.contains(c.description) {
                stack.append(c.description) // If it's a left bracket, put it on the stack 
            }else {
                if stack.count > 0 && c.description == dict[stack.last!] { // If it's right bracket , And the matching is out of the stack 
                    stack.removeLast()
                }else {
                    return false
                }
            }
        }
        return stack.count == 0
    }
}

Copy

stay LeetCode There are also solutions in many languages , Here's a python[4] Solution method

7. Content summary

Let's review today's content . Stack is a data structure with limited operation , Only stack in and stack out operations are supported . Last in first out is its biggest feature . We also know that stack in data structure and stack in memory are not the same concept . We also understand some applications of stack in actual development , And using recursion , When n It's worth a lot of time , A large number of temporary variables will be pressed into the stack and consume memory . And finally solve it through the core idea of stack LeetCode Classic algorithm problems in .

I believe you have really mastered the data structure of stack . Then hurry to knock the code to practice ！

Reference material ：

• 1. Valid parenthesis : https://leetcode-cn.com/problems/valid-parentheses
• 2. Definition of stack : https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin
• 3. Fibonacci sequence : https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
• 4.python Language implementation : https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/