This is the 11th day of my participation in the First Challenge 2022

First, the basic concept of stack

The stack is also a kind of linear table, but different from other linear tables, the stack is divided into top and bottom of the stack and only operations are allowed from the top of the stack, namely push or pop operations, so the operation of the stack follows the principle of “Last In First Out”.

Due to the particularity of the stack, its methods are relatively less than other linear tables, but the nature of the stack is also an array, the data in the stack is also continuous, with the size attribute, but only one end can operate, mainly including the following methods

int size(a); // Get the number of elements in the stack
boolean isEmpty(a); // Check whether the stack is empty
void push(T element); // Push operation
T pop(a); // Unstack
T top(a); // Get the top element of the stack
void clear(a); // Clear the stack
Copy the code

Second, the realization of stack

The inside of the stack can be implemented using dynamic arrays, that is, as a private property of the stack, if the dynamic array is inherited, it does not comply with the stack elements can only operate from the top of the stack. New Module 04- stack in data-Structures project, package com.citi.stack, stack entity class stack, In addition, the List interface, AbstractList abstract class and ArrayList dynamic array in the previously implemented data structure were copied to the List package below citi package, and the utils package was copied to the Citi package.

public class Stack<T> {

    // Private property ArrayList
    private List<T> list = new ArrayList<T>();

 
    public int size(a){
        return null;
    }

    public boolean isEmpty(a){
        return false;
    }

    public void push(T element){}public T pop(a){

        return null
    }

    public T top(a){
        return null; }}Copy the code

Size (), the stack is based on the dynamic array ArrayList, and the stack size is the size of the dynamic array

public int size(a){
    return list.size();
}
Copy the code

IsEmpty (). Similarly, if the ArrayList isEmpty, the stack isEmpty, and the stack’s data is stored in the private ArrayList property

public boolean isEmpty(a){
    return list.isEmpty();
}
Copy the code

Push (), the top of the stack is the end of the dynamic array, and to add an element from the top of the stack is to add an element from the end of the array

public void push(T element){
    list.add(element);
}
Copy the code

Pop () removes the element from the top of the stack that is the last element of the dynamic array and calls the remove method

public T pop(a){
    return list.remove(list.size() - 1);
}
Copy the code

Top (), get the element at the end of the dynamic array, call get method, index size-1

public T top(a){
    return list.get(list.size() - 1);
}
Copy the code

Clear (), which calls the clear method in the dynamic array to clear the stack

public void clear(a){
    list.clear();
}
Copy the code

Add the StackTest class StackTest

public class StackTest {

    Stack stack = null;

    @Before
    public void init(a){
        stack = new Stack<>();
        stack.push(11);
        stack.push(10);
        stack.push(20);
        System.out.println("Init Stack " + stack);
    }

    @Test
    public void push(a) {
        stack.push(30);
        System.out.println("After Push " + stack);
    }

    @Test
    public void pop(a) {
        stack.pop();
        System.out.println("After Pop " + stack);
    }

    @Test
    public void top(a) {
        System.out.println("Get Top "+ stack.top()); }}Copy the code

Adding the toString() method to the Stack also calls the toString() method of a dynamic array

@Override
public String toString(a) {
    return list.toString();
}
Copy the code

Execute all the test methods to verify the Stack

Third, the application of stack

Because the stack can only operate the characteristics of elements from the top of the stack, all the implementation including forward and backward, restore and undo functions are the use of stack data characteristics, such as browser forward and backward function can be summarized as two stack data structure to achieve.

Page1, page2, page3, page1, page2, page3, page1, page2, page3, page1, page2, page3, page1, page2, page3, page1, page2, page3, page1, page2, page3 The browser is also displaying page3.

Click the back button to pop the top element of the first stack and push it to the second stack. The top element of the first stack becomes page2, and all browsers display page2. Click the back button again and pop up the top element of the first stack and push it into the second stack, so the top element of the first stack is page1, and the browser is displaying page1; If you click the forward button, it is equivalent to pop up the top element of the second stack page2 and push it into the first stack as the top element of the stack. At this time, the actual page of the browser is page2

Valid parentheses

LeetCode problem 20: Valid parentheses

Given a string s containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid

class Solution {
public boolean isValid(String s) {}}Copy the code

Use the data characteristics of Stack to solve: First traversal string, if there are any left characters (brackets on the left side) is a push to the stack, if you meet the right characters from a character will be compared with the stack elements, if agree, to bring up this element, until the end if the stack is empty, that is a valid parentheses, if the stack is empty, that is not a valid parentheses, if you meet the right character when the stack is empty, It’s also invalid parentheses.

First, define a stack to hold the left character

// Define a stack
Stack<Character> stack = new Stack<>();
Copy the code

If it encounters a right string, it first checks whether the stack is empty, and returns false if the stack is empty. It then retrieves the top element of the stack, and checks whether the top element is a pair with the right character traversed, otherwise returns false

for (int i = 0; i < len; i++) {
    char c = s.charAt(i);
    if (c == '(' || c == '[' || c == '{') {/ / into the stack
        stack.push(c);
    } else { / / a parenthesis
        // Check whether the stack is empty
        if (stack.isEmpty()) return false;
        // Pops the top element of the stack
        char left = stack.pop();
        // Determine if the top element is paired with the traversed right character
        if (left == '('&& c ! =') ') return false;
        if (left == '['&& c ! ='] ') return false;
        if (left == '{'&& c ! ='} ') return false; }}Copy the code

Finally, check whether the stack is empty

return stack.isEmpty();
Copy the code

The complete code

public boolean isValid(String s) {

    // Define a stack
    Stack<Character> stack = new Stack<>();
    int len = s.length();

    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {/ / into the stack
            stack.push(c);
        } else { / / a parenthesis
            // Check whether the stack is empty
            if (stack.isEmpty()) return false;
            // Pops the top element of the stack
            char left = stack.pop();
            // Determine if the top element is paired with the traversed right character
            if (left == '('&& c ! =') ') return false;
            if (left == '['&& c ! ='] ') return false;
            if (left == '{'&& c ! ='} ') return false; }}return stack.isEmpty();
}
Copy the code