Learn about today's record stack

Stack

Stack (stack)
A stack is an ordered list of Filo first in last out.
Stack is a special linear table that restricts the insertion and deletion of elements in a linear table to the same end of the linear table. The end that allows insertion and deletion is the changing end, which is called the top of the stack, and the other end is the fixed end, which is called the bottom of the stack.

Use of stack

• Subroutine call: before jumping to the subroutine, the address of the next instruction will be stored in the stack until the subroutine is executed, and then the address will be taken out to return to the original program.
• Handling recursive calls: similar to subroutine calls, except that in addition to storing the address of the next instruction, parameters, area variables and other data are also stored in the stack.
• Expression conversion [infix expression to suffix expression] and evaluation (actual solution).
• Traversal of binary tree.
• The depth first search method of graphics.

Array to simulate stack

package com.tunan.stack;

import java.util.Scanner;

public class ArrayStackDemo {

	public static void main(String[] args) {

		//test
		ArrayStack arrayStack = new ArrayStack(4);
		String key = "";
		boolean loop = true;
		Scanner scanner = new Scanner(System.in);
		
		while(loop) {
			System.out.println("show: Display stack");
			System.out.println("exit: Exit stack");
			System.out.println("push: Push ");
			System.out.println("pop: Out of stack");
			System.out.println("Please enter your choice");
			key = scanner.next();
			switch (key) {
			case "show":
				arrayStack.showStack();
				break;
			case "push":
				System.out.println("Please enter the stack parameters");
				int value = scanner.nextInt();
				arrayStack.push(value);
				break;
			case "pop":
				try {
					int res = arrayStack.pop();
					System.out.printf("Out of stack data is%d \n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case "exit":
				scanner.close();
				loop = false;
				System.out.println("Exit successful");
				break;

			default:
				break;
			}
		}
		

	}

}

//Array stack, create an array simulation class
class ArrayStack {
	private int maxSize; //Maximum capacity of stack
	private int[] stack;//Stack data is stored in the array
	private int top = -1;//Indicates the top of the stack, initialized to - 1
	
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[maxSize];
	}
	//Judge stack full
	public boolean isFull() {
		return top == maxSize - 1;
	}
	//Judge stack empty
	public boolean isEmpty() {
		return top == -1;
	}
	//Stack operation
	public void push(int val) {
		if(isFull()) {
			System.out.println("The stack is full and cannot be loaded");
			return;
		}
		top++;
		stack[top]=val;
	}
	//Out of stack operation
	public int pop() {
		if(isEmpty()) {
			//Throw exception
			throw new RuntimeException("Stack empty, unable to perform stack out operation");
		}
		int res = stack[top];
		top--;
		return res;
	}
	//Traversal stack
	public void showStack(){
		if(isEmpty()) {
			System.out.println("Stack empty");
			return;
		}
		for (int j=top; j>-1;j--){
			System.out.printf("stack[%d] = %d \n", j, stack[j]);
		}
	}
	
	
}

The operation of array simulation stack is relatively simple, so here is a further application of array simulation stack:

Implement calculator operation

Here, we first implement a simple infix expression calculation operation. The so-called infix is the most commonly seen expression form, such as
722-5+1-5+3-4/2

The idea of this operation is:

The code implementation is as follows:

package com.tunan.stack;

public class Calculator {

	public static void main(String[] args) {
		//Give an expression
		String expression = "7*2*2-5+1-5+3-4/2";//How to deal with multi bit number
		//Create two stacks, number stack and symbol stack
		calStack numStack = new calStack(10);
		calStack operStack = new calStack(10);
		//Define related variables
		int index = 0;//Scanning
		int num1 = 0;
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' ';//Save the char obtained from each scan to ch
		String keepNum = "";//Multi bit number for splicing
		//Start while scan
		while(true) {
			//Get each bit in expression in turn, using the string method
			ch = expression.substring(index, index+1).charAt(0);
			//Judge whether this bit is a number or a symbol
			if(operStack.isOper(ch)) {//If operator
				if(!operStack.isEmpty()){
					//If it is not empty, you need to judge the priority
					//If the priority is less than or equal to the stack top priority, you need to pop out the corresponding operation
					if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						//Put the operation result on the stack
						numStack.push(res);
						//Then put the current symbol into the symbol stack
						operStack.push(ch);
						
					} else {//Otherwise, directly stack
						operStack.push(ch);
					}
					
				}else {//If it is empty, directly put it on the stack
					operStack.push(ch);
				}
				
			} else {//If it is a number, directly enter the number stack
				//numStack. push(ch - 48); //' 1 '- > 1 * * * compared with acsll code, the difference between characters and numbers is 48
				//Considering the number of multiple bits, you need to continue scanning after the index. If it is a number, you need to splice
				keepNum += ch;
				if(index == expression.length() - 1){
					numStack.push(Integer.parseInt(keepNum));
				} else{
					if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))) {
						//String to int, "123" - > 123
						numStack.push(Integer.parseInt(keepNum));
						//keepNum must be emptied!!!
						keepNum = "";
					}
				}
				
			}
			index++;
			if(index >= expression.length()) {
				break;
			}
		}
		
		//When the scanning is completed, the corresponding data from the number stack and symbol stack pop can be calculated
		while(true) {
			//If the symbol stack is empty, the end of calculation -- only one bit left in the number stack is the result
			if(operStack.isEmpty()){
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		System.out.printf("expression %s = %d\n", expression, numStack.pop());
	}
}


//Create a stack to add the functions required by the calculator
class calStack {
	private int maxSize; //Maximum capacity of stack
	private int[] stack;//Stack data is stored in the array
	private int top = -1;//Indicates the top of the stack, initialized to - 1
	
	public calStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[maxSize];
	}
	//View the stack top value but do not perform the stack out operation
	public int peek() {
		if(isEmpty()) {
			//Throw exception
			throw new RuntimeException("Stack empty, unable to perform stack out operation");
		}
		int res = stack[top];
		return res;
	}
	
	//Judge stack full
	public boolean isFull() {
		return top == maxSize - 1;
	}
	//Judge stack empty
	public boolean isEmpty() {
		return top == -1;
	}
	//Stack operation
	public void push(int val) {
		if(isFull()) {
			System.out.println("The stack is full and cannot be loaded");
			return;
		}
		top++;
		stack[top]=val;
	}
	//Out of stack operation
	public int pop() {
		if(isEmpty()) {
			//Throw exception
			throw new RuntimeException("Stack empty, unable to perform stack out operation");
		}
		int res = stack[top];
		top--;
		return res;
	}
	//Traversal stack
	public void showStack(){
		if(isEmpty()) {
			System.out.println("Stack empty");
			return;
		}
		for (int j=top; j>-1;j--){
			System.out.printf("stack[%d] = %d \n", j, stack[j]);
		}
	}
	//Returns the priority of the operator, expressed in numbers
	//The higher the number, the higher the priority
	public int priority(int oper) {
		if(oper == '*' || oper == '/'){
			return 1;
		} else if(oper == '+' || oper == '-') {
			return 0;
		} else {
			return -1;
		}
	}
	//Determine whether it is an operator
	public boolean isOper(char val) {
		return val == '+' || val == '-' || val == '*' || val == '/';
	}
	//Judge whether it is a value
	//Either operator or value
	
	//computing method
	public int cal(int num1, int num2, int oper){
		int res = 0;//Used to store results
		switch (oper) {
		case '+':
			res = num1 + num2;
			break;
		case '-':
			res = num2 - num1;//Pay attention to the order
			break;
		case '*':
			res = num1 * num2;
			break;
		case '/':
			res = num2 / num1;
			break;

		default:
			break;
		}
		return res;
	}
	
}

It can be seen that the calculation process is cumbersome, which is also the short board of infix expression. Although it is convenient for people to read, it is not friendly to the computer, and the above program does not take into account the parentheses.

In the next section, I will continue to introduce the expressions of prefixes, infixes and suffixes, as well as the expression of realizing inverse Polish.