1. What is a stack?

  • A stack is a special kind of linear table that can only be operated on at one end
  • The operation of adding elements to the stack, commonly called push, is pushed
  • The operation of removing an element from the stack, commonly called pop, is out of the stack
  • A stack has a bottom and a top. The first thing to push is the bottom of the stack, and the last thing to push is the top of the stack
  • Stack follows the principle of Last in first out, LIFO

2. Realization of stack

  • The stack is implemented as a dynamic array

See data Structures and Algorithms – Dynamic arrays for detailed implementation of dynamic arrays

Public class Stack<E> {private List<E> List = new ArrayList<>(); Public void clear() {// Call ArrayList's clear method list.clear(); } public int size() {// Call ArrayList's size method return list.size(); } public Boolean isEmpty() {return list.isempty (); return list.isempty (); Public void push(E element) {// ArrayList adds element list.add(element); Return list.remove(list.size() -1); return list.remove(list.size() -1); return list.remove(list.size() -1); Return list.get(list.size() -1); return list.get(list.size() -1); }}Copy the code

3. Application of stack

  • Browser forward and backward

  • Picture repair of the revocation and restoration of the realization

Principle: Two stacks A and B are created, one to record the order in which A is pushed and the other to record the order in which B is pushed.

1, when we browse the web, open baibu.com – taobao.com – qq.com at one time. Push A in turn

2. When we go backwards, pop out of stack A and place qq.com – taobao.com in sequence. Push B in turn.

3. As it moves forward, it pops out of stack B and pushes into stack A.

4. When A new page opens again, push jd.com onto stack A and clear stack B

4, leetCode algorithm exercises

4.1, leetCode algorithm –20. Valid parentheses

Interview questions link: leetcode-cn.com/problems/va…

[] {[()]}”, {[()]}”, {[()]}

Solution 1: comparative method

When a string contains “[]”, “()”, “{}”, replace it with a null character. If the string length is empty, the match is valid.

class Solution {    
    public boolean isValid(String s) {        
        while (s.contains("[]") || s.contains("()") || s.contains("{}") ){            
            s = s.replace("[]","");            
            s = s.replace("()","");            
            s = s.replace("{}","");        
        }        
        return s.isEmpty();    
    }
}
Copy the code

Solution two: stack

Disintegration idea: we can use the stack to implement. 1,” {“,” [“,” (“, we call the left character. “} “,”] “,”) “, we call the right character 2. When we encounter the left character, we press the stack. When the right character is encountered, the top element of the stack is compared to the right character. If a match is a valid character, it pops off the stack. If a mismatch is an invalid character, it pops off the stack. 3, the right character is compared to the top of the stack, pop the top of the stack element, and finally compare, stack empty is a valid character. Otherwise, invalid character.

Class Solution {public Boolean isValid(String s) {// Create Stack<Character> Stack = new Stack<>(); Int len = s.length(); int len = s.length(); For (int I = 0; i < len; Char c = s.charat (I); char c = s.charat (I); / / if it is left parenthesis if (c = = '[' | | c = =' (' | | c = = '{') {/ / pressure stack stack. Push (c);} else {/ / if it is right parenthesis / / if the stack is empty, no left parenthesis, Char left = stack.pop(); // Left == '[' &&c!= ']') Return false; if (left = = '(' && c! =') '); return false if (left = = '{}' && c! = ' ') return false;}} / / the stack is empty, Return stack.isEmpty();}}Copy the code