catalogue

• 1. Basic concept of stack
• 2. Simple implementation of stack
• 3. Code analysis
• 4. Application scenario
• 5. Summary

In the first chapter, we talked about the specific data storage structure of data, which is mainly used for data recording.

This chapter mainly talks about an auxiliary tool for conceiving algorithms - stack, which is used to perform specific tasks.

1. Basic concept of stack

stack is an abstract data structure (ADT), which can be implemented with other data structures, such as the array mentioned above.

It is a data structure with limited access, which follows the rule of first in and last out (FILO), that is, the principle of the last out of the stack.

It is like a bullet clip. First press the bullet into the clip, press it to the bottom, and finally shoot it out.

According to the characteristics of stack, stack can play an important role in tree search and depth first search (DFS)

2. Simple implementation of stack

public class MyStack {
    //Store
    private int[] array;
    //Top of stack
    private int top;
    //Maximum capacity
    private int max;

    public MyStack(int size){
        max = size;
        top = -1;
        array = new int[size];
    }

    //Press in data
    public void push(int x){
        if((top+1)<max){
            array[++top]=x;
        }
    }

    //Pop up data
    public int pop(){
        return array[top--];
    }

    //Get stack top data
    public int peek(){
        return array[top];
    }

    //Is the stack empty
    public boolean isEmpty(){
        return top==-1;
    }

    //Is the stack full
    public boolean isFull(){
        return top == max-1;
    }

    public static void main(String[] args) {
        MyStack stack = new MyStack(10);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println(stack.peek());
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

Look at the test results:

Above, we implemented a simple stack with an array. Point to the top element with top. Press in and pop-up only need to move the top pointer and judge whether it exceeds the maximum capacity.

However, the problem with this stack is that the capacity is limited. We must initialize a capacity of an appropriate size in order to fully place the data and will not waste the capacity.

This is difficult to do. Let's refer to the implementation of stack in java to optimize the following stack

3. Code analysis

We can refer to the implementation class of public class stack < E > extends vector < E >. The actual JDK recommends using Deque's implementation class to implement the stack.

This Stack is for reference only:

 protected Object[] elementData;//use Object Store data

//Added capacity expansion mechanism
//Create an array with a size of twice the current capacity
//Move old data to new array
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Let's see how ArrayQueue implements stack:

//ArrayDeque poll Implementation method of    
public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }

head = (h + 1) & (elements.length - 1);

A clever design is generally head+1. When the head reaches the end of the array, set the head to 0.

4. Application scenario

Using the characteristics of stack, we can use stack to reverse characters

//Put the previously stored int[]Change to Object[]    
public static void main(String[] args) {
        MyStack stack = new MyStack(20);
        String str = "Hello World!";
        char[] chars = str.toCharArray();
        for(char c: chars){
            stack.push(c);
        }
        while (!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }

Operation results:

With the previous small example, we are taking an example to realize the application. We may need to parse an expression represented by a string of characters,

In general, you can convert a string into an inverse Polish expression (suffix expression) to calculate

For example, change (a+b) * (c+d) into (ab+cd)+*

Just do a simple calculation in pairs

/**
     * Convert to inverse Polish expression
     * @param strList
     * @return
     */
    public List<String> initRPN(List<String> strList){
        List<String> returnList = new ArrayList<String>();
        //Stack used to store operators
        Stack stack = new Stack();
//      stack.push(LOWESTSING);
        int length = strList.size();
        for(int i=0;i<length;i++ ){
            String str = strList.get(i);
            if(isNumber(str)){
                returnList.add(str);
            }else{
                if(str.equals(OPSTART)){
                    //'('Direct stack
                    stack.push(str);
                }else if(str.equals(OPEND)){
                    //')'
                    //Perform the stack out operation until the stack is empty or encounters the first left parenthesis   
                    while (!stack.isEmpty()) {   
                        //Stack the string at the top of the stack   
                        String tempC = stack.pop();   
                        if (!tempC.equals(OPSTART)) {   
                            //If it is not an open parenthesis, put the string directly at the end of the inverse list   
                            returnList.add(tempC);   
                        }else{   
                            //If it is an open bracket, exit the loop operation   
                            break;   
                        }   
                    }   
                }else{
                    if (stack.isEmpty()) {
                        //If the stack is empty   
                        //Stack the current string directly   
                        stack.push(str);   
                    }else{
                        //Stack is not empty,Comparison operator priority order
                        if(precedence(stack.top())>=precedence(str)){
                            //If the priority of the element at the top of the stack is greater than that of the current element, then
                            while(!stack.isEmpty() && precedence(stack.top())>=precedence(str)){
                                returnList.add(stack.pop());
                            }
                        }
                        stack.push(str);
                    }
                }
            }
        }
        //If the stack is not empty, all elements in the stack will be out of the stack and placed at the end of the inverse Polish linked list   
        while (!stack.isEmpty()) {
            returnList.add(stack.pop());
        }
        return returnList;
    }

 /**
     * It doesn't matter whether the priority order is set or not
     * @return
     */
    private int precedence(String str){
        char sign = str.charAt(0);
        switch(sign){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
            case '%':
                return 3;
            case '(':
            case ')':
//          case '#':
            default:
                return 0;

        }
    }

/**
 * Whether it is an integer or floating-point number, but the default is -05.15, which is also considered to be the correct format
 * @param str
 * @return
 */
private boolean isNumber(String str){
    Pattern p = Pattern.compile("^(-?\\d+)(\\.\\d+)?$");
    Matcher m = p.matcher(str);
    boolean isNumber = m.matches();
    return isNumber;
}

The operation is to compare the characters in the stack and list the characters in the common code.

5. Summary

According to the characteristics of stack first in and last out, we can realize a variety of functions.

The stack makes the program less error prone by providing restrictive access methods push() and pop().

The stack only operates on the top elements of the stack, and the time complexity of out stack and in stack is O (1)

The operation of the stack is independent of the number of data in the stack, so there is no need to compare and move.