Introduction to stack
A stack is a first in, then out, ordered list. 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 becomes the Top of the stack, and the other end is the fixed end, which becomes the bottom of the stack. According to the definition of stack, the elements put into the stack first are at the bottom of the stack. The last placed element is at the Top of the stack, while the deleted element is just the opposite. The last placed element is deleted first, and the first placed element is deleted last.
Application scenario 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.

Conversion and evaluation of expressions (infix expression to suffix expression)

Traversal of binary tree

The depth first search method of graphics.
Quick start to stack
Use the array to simulate the use of the stack. Since the stack is an ordered list, of course, the structure of the array can be used to store the data content of the stack. Next, we will use the data to simulate the operations such as out of the stack and in the stack.
Thought analysis of realizing stack
 Use arrays to simulate stacks
 Define a top to represent the top of the stack and initialize it to  1
 When data is added to the stack, top++;stack[top] = data;
 Stack out operation, int value = stack[top];top–,return value
code implementation
 Create an ArrayStackDomo exercise class
 Define an ArrayStack to represent the stack
class ArrayStack{ private int maxSize; //Stack size private int[] stack; //Array, array simulation stack, data is placed in the array private int top = 1; //Top indicates the top of the stack. Initialization to  1 indicates no data }
 Write constructor
public ArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; }
 Judge stack full
public boolean isFull(){ return top == maxSize  1; //When the top of the stack is equal to the size of the stack, it indicates that the stack is full }
 Judge whether the stack is empty
public boolean isEmpty(){ return top == 1; }
 Write the push method
public void push(int value){ //Determine whether the stack is full if (isFull()){ System.out.println("Stack full"); return; } top++; stack[top] = value; }
 Write the stack method pop to return the data at the top of the stack
public int pop(){ //First judge whether the stack is empty if (isEmpty()){ //Throw exception throw new RuntimeException("Stack empty,no data~"); } int value = stack[top]; top; return value; }
 Write the case of the display stack [traversing the stack]. When convenient, you need to display data from the top of the stack.
public void list(){ if (isEmpty()){ System.out.println("Stack empty, no data~~"); return; } for(int i = top; i >= 0; i){ System.out.printf("stack[%d]=%d\n",i,stack[i]); } }
test
public static void main(String[] args) { //Test whether ArrayStack is correct //First create an ArrayStack object  > represent stack ArrayStack stack = new ArrayStack(4); String key =""; boolean loop =true;//Controls whether to exit the menu Scanner scanner =new Scanner(System.in); while (loop){ System.out.println("show: Indicates the display stack"); System.out.println("exit: Exit program"); System.out.println("push: Indicates adding data to the stack(Push )"); System.out.println("pop: Indicates fetching data from the stack(Out of stack)"); System.out.print("Please enter your choice:"); key=scanner.next(); switch (key){ case "show": stack.list(); break; case "exit": scanner.close(); loop=false; break; case "push": System.out.print("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; default: break; } System.out.println(""); } System.out.println("The program has exited"); }
 Stack test
 Test display stack
 Test out stack
Complete code
import java.util.Scanner; /** * @author mengzhichao * @create 2022041516:28 */ public class ArrayStackDemo { public static void main(String[] args) { //Test whether ArrayStack is correct //First create an ArrayStack object  > represent stack ArrayStack stack = new ArrayStack(4); String key =""; boolean loop =true;//Controls whether to exit the menu Scanner scanner =new Scanner(System.in); while (loop){ System.out.println("show: Indicates the display stack"); System.out.println("exit: Exit program"); System.out.println("push: Indicates adding data to the stack(Push )"); System.out.println("pop: Indicates fetching data from the stack(Out of stack)"); System.out.print("Please enter your choice:"); key=scanner.next(); switch (key){ case "show": stack.list(); break; case "exit": scanner.close(); loop=false; break; case "push": System.out.print("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; default: break; } System.out.println(""); } System.out.println("The program has exited"); } } //Define an ArrayStack to represent the stack class ArrayStack{ private int maxSize; //Stack size private int[] stack; //Array, array simulation stack, data is placed in the array private int top = 1; //Top indicates the top of the stack. Initialization to  1 indicates no data //constructor public ArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; } //Stack full public boolean isFull(){ return top == maxSize  1; //When the top of the stack is equal to the size of the stack, it indicates that the stack is full } //Stack empty public boolean isEmpty(){ return top == 1; } //Stack push public void push(int value){ //Determine whether the stack is full if (isFull()){ System.out.println("Stack full"); return; } top++; stack[top] = value; } //Out of stack  pop to return the data at the top of the stack public int pop(){ //First judge whether the stack is empty if (isEmpty()){ //Throw exception throw new RuntimeException("Stack empty,no data~"); } int value = stack[top]; top; return value; } //Display the stack [convenience stack]. When traversing, you need to display data from the top of the stack public void list(){ if (isEmpty()){ System.out.println("Stack empty, no data~~"); return; } for(int i = top; i >= 0; i){ System.out.printf("stack[%d]=%d\n",i,stack[i]); } } }
A practical requirement of stack
Suppose we enter a string of expressions. How does the computer get the result? What if it is implemented by stack?
7 + 2 ∗ 6 − 4 7+2*64 7+2∗6−4
Calculation idea of using stack to complete expression

Traverse our expression through an index value (index)

If we find that it is a number, we will put it on the stack directly

If we find that the scanned symbol is a symbol, it can be divided into the following situations. If we find that the current symbol stack is empty, we can directly enter the stack. If there are operators in the symbol stack, we can compare them. If the priority of the current operator is less than or equal to that of the operators in the stack, we need to pop two numbers from the number stack and pop a symbol from the symbol stack for operation. The results will be put into the number stack, Then put the current operator into the symbol stack. If the priority of the current operator is greater than that of the operator in the stack, it will be directly put into the symbol stack.

When the expression is scanned, the corresponding numbers and symbols are pop out of the number stack and symbol stack in sequence, and the operation is carried out.

Finally, there is only one number in the number stack, which is the result of the expression.
Complete code implementation
/** * @author mengzhichao * @create 2022041611:12 */ public class Calculator { public static void main(String[] args) { //Define an expression String expression = "7+2*64"; //Create two stacks, a number stack and a symbol stack CalculatorArrayStack numStack = new CalculatorArrayStack(100); CalculatorArrayStack operStack = new CalculatorArrayStack(100); int index = 0; //For scanning int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch =' '; //Save the char obtained from each scan in ch //Start scan expression of while loop while (true){ //Get every character of experssion at one time ch = expression.substring(index,index+1).charAt(0); //Judge what ch is and deal with it accordingly if (operStack.isOper(ch)){ //If operator //Judge whether the current symbol stack is empty if (!operStack.isEmpty()){ //If the symbol stack has operators, compare them. If the priority of the current operator is less than or equal to that of the operators in the stack, //You need to pop two numbers from the number stack and pop a symbol from the symbol stack, //Carry out the operation, put the obtained result into the number stack, and then put the current operator into the symbol stack 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 result of the operation on the stack numStack.push(res); //Then put the current operator on the symbol stack operStack.push(ch); }else { //If the priority of the current operator is higher than that of the operator in the stack, it will be directly put into the symbol stack operStack.push(ch); } }else { //If it is empty, direct access symbol stack operStack.push(ch); // 7 * 2 } }else { numStack.push(ch  48); } //Let index + 1 and judge whether to scan to the end of expression index++; if (index >= expression.length()){ break; } } //When the expression is scanned, the corresponding numbers and symbols are pop out of the number stack and symbol stack in sequence, and the operation is carried out. while (true){ //If the symbol stack is empty, the final result will be calculated, and there is only one number [result] in the number stack if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); numStack.push(res); } //pop out the last number of the stack, which is the result int res2 = numStack.pop(); System.out.printf("expression%s = %d",expression,res2); } } //Create a stack first class CalculatorArrayStack{ private int maxSize; //Stack size private int[] stack; //Array, array simulation stack, data is placed in the array private int top = 1; //Top indicates the top of the stack. Initialization to  1 indicates no data //constructor public CalculatorArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; } //Stack full public boolean isFull(){ return top == maxSize  1; //When the top of the stack is equal to the size of the stack, it indicates that the stack is full } //Stack empty public boolean isEmpty(){ return top == 1; } //Stack push public void push(int value){ //Determine whether the stack is full if (isFull()){ System.out.println("Stack full"); return; } top++; stack[top] = value; } //Returns the value at the top of the stack without any modification public int peek(){ return stack[top]; } //Out of stack  pop to return the data at the top of the stack public int pop(){ //First judge whether the stack is empty if (isEmpty()){ //Throw exception throw new RuntimeException("Stack empty,no data~"); } int value = stack[top]; top; return value; } //Display the stack [convenience stack]. When traversing, you need to display data from the top of the stack public void list(){ if (isEmpty()){ System.out.println("Stack empty, no data~~"); return; } for(int i = top; i >= 0; i){ System.out.printf("stack[%d]=%d\n",i,stack[i]); } } //Returns the priority of the operator. The priority is determined by the programmer. The priority is 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; //Assume that the current expression is only +, , */ } } //Judge whether it is an operator public boolean isOper(char val){ return val == '+'  val == ''  val == '*'  val == '/'; } //computing method public int cal(int num1,int num2,int oper){ int res = 0; //res is used to store the calculation 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; //Result return } }
Run and test
After testing, we found that the results calculated by the program are consistent with those calculated by us, but we don't know if you have found a problem. When we change 7 in the expression to 70, our calculation results will have some problems.
How to solve this problem? Let's keep looking down!
Analysis of function optimization ideas and code improvement

When processing a multi bit number, it can't be found that it is a number and immediately put it on the stack, because it may be a multi bit number

When processing numbers, you need to look at one bit after the index of the expression. If it is a number, it will be scanned. If it is a symbol, it will be put on the stack

Therefore, we need to define a variable string for splicing
/** * @author mengzhichao * @create 2022041611:12 */ public class Calculator { public static void main(String[] args) { //Define an expression String expression = "7*2*25+15+34"; //Create two stacks, a number stack and a symbol stack CalculatorArrayStack numStack = new CalculatorArrayStack(100); CalculatorArrayStack operStack = new CalculatorArrayStack(100); int index = 0; //For scanning int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch =' '; //Save the char obtained from each scan in ch String keepNum = ""; //Multi bit number for splicing //Start scan expression of while loop while (true){ //Get every character of experssion at one time ch = expression.substring(index,index+1).charAt(0); //Judge what ch is and deal with it accordingly if (operStack.isOper(ch)){ //If operator //Judge whether the current symbol stack is empty if (!operStack.isEmpty()){ //If the symbol stack has operators, compare them. If the priority of the current operator is less than or equal to that of the operators in the stack, //You need to pop two numbers from the number stack and pop a symbol from the symbol stack, //Carry out the operation, put the obtained result into the number stack, and then put the current operator into the symbol stack 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 result of the operation on the stack numStack.push(res); //Then put the current operator on the symbol stack operStack.push(ch); }else { //If the priority of the current operator is higher than that of the operator in the stack, it will be directly put into the symbol stack operStack.push(ch); } }else { //If it is empty, direct access symbol stack operStack.push(ch); // 7 * 2 } }else { // numStack.push(ch  48); //Analysis ideas //1. When processing multi digit numbers, if it cannot be found that it is a number, it will be immediately put into the stack, because it may be multi digit numbers //2. When processing numbers, you need to look at one bit after the index of the expression. If it is a number, it will be scanned. If it is a symbol, it will be put on the stack //3. Therefore, we need to define a variable string for splicing //Number of processing bits keepNum += ch; //If ch is already the last bit of expression, it is directly put on the stack. if (index == expression.length()  1){ numStack.push(Integer.parseInt(keepNum)); }else { //Judge whether the next character is a number. If it is a number, continue scanning. If it is an operator, put it on the stack //Note that it's the last one, not the index++ if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { //If the last bit is an operator, put keepNum = "1" or "123" on the stack numStack.push(Integer.parseInt(keepNum)); //important!!!!!!, keepNum empty keepNum = ""; } } } //Let index + 1 and judge whether to scan to the end of expression index++; if (index >= expression.length()){ break; } } //When the expression is scanned, the corresponding numbers and symbols are pop out of the number stack and symbol stack in sequence, and the operation is carried out. while (true){ //If the symbol stack is empty, the final result will be calculated, and there is only one number [result] in the number stack if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); numStack.push(res); } //pop out the last number of the stack, which is the result int res2 = numStack.pop(); System.out.printf("expression%s = %d",expression,res2); } } //Create a stack first class CalculatorArrayStack{ private int maxSize; //Stack size private int[] stack; //Array, array simulation stack, data is placed in the array private int top = 1; //Top indicates the top of the stack. Initialization to  1 indicates no data //constructor public CalculatorArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; } //Stack full public boolean isFull(){ return top == maxSize  1; //When the top of the stack is equal to the size of the stack, it indicates that the stack is full } //Stack empty public boolean isEmpty(){ return top == 1; } //Stack push public void push(int value){ //Determine whether the stack is full if (isFull()){ System.out.println("Stack full"); return; } top++; stack[top] = value; } //Returns the value at the top of the stack without any modification public int peek(){ return stack[top]; } //Out of stack  pop to return the data at the top of the stack public int pop(){ //First judge whether the stack is empty if (isEmpty()){ //Throw exception throw new RuntimeException("Stack empty,no data~"); } int value = stack[top]; top; return value; } //Display the stack [convenience stack]. When traversing, you need to display data from the top of the stack public void list(){ if (isEmpty()){ System.out.println("Stack empty, no data~~"); return; } for(int i = top; i >= 0; i){ System.out.printf("stack[%d]=%d\n",i,stack[i]); } } //Returns the priority of the operator. The priority is determined by the programmer. The priority is 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; //Assume that the current expression is only +, , */ } } //Judge whether it is an operator public boolean isOper(char val){ return val == '+'  val == ''  val == '*'  val == '/'; } //computing method public int cal(int num1,int num2,int oper){ int res = 0; //res is used to store the calculation 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; //Result return } }
Retest
The problem was successfully solved.