I. Introduction (Stack)

1. Basic concepts

  • A stack is an ordered list of entries followed by an exit
  • A stack is a special kind of linear table that limits the insertion and deletion of elements in a linear table to the same end of the table. A segment that is allowed to be inserted or deleted. The changing end is the top of the stack, and the fixed end is the bottom of the stack.
  • The first element on the stack is at the bottom, and the last element is at the top. Deleting elements is just the opposite.
  • The two basic operations on the stack, pop and Push, are as follows:

Into the stack:

The stack:

2. Application scenarios

  • Function call: Before executing the subfunction sequence, the address of the subfunction is stored on the stack until the subfunction is completed, and then the address is popped back to the original function.
  • Handling recursive calls: Similar to function calls, arguments, region variables, and other data are stored on the stack in addition to the address of the child function
  • Expression transformation (infix expression into postfix expression) and evaluation
  • Traversal of binary trees
  • Depth-first search algorithm

Two, stack code implementation

1. Analysis of ideas

2. Code implementation

// Create a new class to define the stack
class StackList{
    private int maxSize; // represents the stack size
    private int top; // represents the top of the stack
    private int[] stack; // Define an array representing the stack

    public StackList(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    // Check whether the stack is full
    public boolean isFull(a){
        return top == maxSize;
    }

    // Check whether the stack is empty
    public boolean isEmpty(a){
        return top == -1;
    }

    / / into the stack
    public void push(int value){
        // Check whether the stack is full
        if(isFull()){
            System.out.println("Stack full ~ ~");
            return;
        }
        top++;
        stack[top] = value;
    }

    / / out of the stack
    public int pop(a){
        // Check whether the stack is full
        if(isEmpty()){
            // Throw an exception
            throw new RuntimeException("Stack is empty." ");
        }
        int value = stack[top];
        top--;
        return value;
    }

    / / display the stack
    public void show(a){
        if (isEmpty()){
            System.out.println("Stack empty, no data.");
            return;
        }
        // Display data from the top of the stack
        for (int i = top; top >= 0; top--){
            System.out.printf("Stack[%d]=%d/n",i,stack[i]); }}}Copy the code

The test case

public static void main(String[] args){
        StackList stack = new StackList(4);
        String key = "";
        boolean loop = true; // Control whether to exit
        Scanner scanner = new Scanner(System.in);

        while (loop){
            System.out.println("Show: display stack");
            System.out.println("Exit: Exit the program");
            System.out.println("Push: stack");
            System.out.println("Pop: the stack");
            System.out.println("Please enter your choice");
            key = scanner.next();
            switch (key){
                case "show":{
                    stack.show();
                    break;
                }
                case "exit":{
                    scanner.close();
                    loop = false;
                    break;
                }
                case "push": {
                    System.out.println("Please enter a number.");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                }
                case "pop": {
                    try {
                        int res = stack.pop();
                        System.out.printf("The data out of the stack is %d\n",res);
                    } catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break; }}}}Copy the code

Third, the application of stack

1. Integrated calculator

2. Prefix, infix, and suffix expressions