One , Stack
Stack （stack） Also known as stack , It is a linear table with limited operation . A linear table that restricts insertion and deletion operations only at the end of the table . This end is called the top of the stack , Relatively , Call the other end the bottom of the stack . Inserting new elements into a stack is also called stack entry , Put or press the stack , It puts new elements on top of the top of the stack , Make it a new top of stack element ; Deleting elements from a stack is also called stack exit or stack exit , It is to delete the top element of the stack , Make its adjacent elements new top of stack elements .
Two , Application scenarios of stack
1, Subroutine call
Before calling to subroutine , The address of the next instruction is first put on the stack , The address will not be thrown until the subroutine is executed , To go back to the original procedure .
2, Handling recursive calls
Similar to subroutine call , Except for the address of the next instruction , Also store parameters , Regional variables and other data .
3, Expression conversion
Infix expression to suffix expression
4, Traversal of binary tree
5, Depth first search method for graphics
Three , Stack implementation of comprehensive calculator （ Infix expression ）
1, Thinking analysis
* Through a index value （ Indexes ）, To traverse our expressions
* If it is found to be a number, put it directly into the stack
* If the current symbol stack is found to be empty , Just go straight to the stack
*
If the symbol stack is found to have an operator , We'll make a comparison , If the priority of the current operator is less than or equal to the operator in the stack , You need to start from the stack pop Make a symbol , Do the operation , You'll get the results , Input data stack , Then put the current operator on the symbol stack , If the priority of the current operator is higher than that of the stack operator , Just go straight to the symbol stack .
* When the expression is scanned , In order from the number stack and symbol stack pop The corresponding numbers and symbols are given , And calculate .
* Finally, there is only one number in the stack , This is the result of the expression .
2, Code instance
（1）ArrayStack Tools
package dataStructure.stack; public class ArrayStack { private int maxSize; //
Stack size private int[] stack; // array , Array emulation stack , The data is placed in the array private int top = -1;//
top Represents the top of the stack , Initialize to -1 // constructor public ArrayStack(int maxSize) { this.maxSize = maxSize;
stack = new int[this.maxSize]; } // Add a method , You can return the value at the top of the current stack , But not really pop public int
peek() { return stack[top]; } // Stack full public boolean isFull() { return top ==
maxSize - 1; } // Stack empty public boolean isEmpty() { return top == -1; } // Push -push
public void push(int value) { // First judge whether the stack is full if(isFull()) {
System.out.println(" Stack full "); return; } top++; stack[top] = value; } // Out of the stack -pop,
Return the data at the top of the stack public int pop() { // First judge whether the stack is empty if(isEmpty()) { // Throw an exception throw new
RuntimeException(" Stack empty , no data ~"); } int value = stack[top]; top--; return value; }
// Show the stack [ Traversal stack ], Traversal time , You need to display data from the top of the stack public void list() { if(isEmpty()) {
System.out.println(" Stack empty , no data ~~"); return; } // You need to display data from the top of the stack for(int i = top; i >=
0 ; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } }
// Returns the priority of the operator , Priority is determined by the programmer , Priority is expressed in numbers // The bigger the number is , 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 has only +, - , * , / } }
// Determine 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 It is used to store the results of calculation 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;
} }
（2） Test class
package dataStructure.stack; public class Calculator { public static void
main(String[] args) { // According to the teacher's ideas , Complete the operation of the expression String expression = "100/5+2*3-1"; //
25 // Create two stacks , Counting stack , A symbol stack ArrayStack numStack = new ArrayStack(10); ArrayStack
operStack = new ArrayStack(10); // Define the required related variables int index = 0;// For scanning int num1 = 0;
int num2 = 0; int oper = 0; int res = 0; char ch = ' '; // Each scan will get char Save to ch
String keepNum = ""; // For splicing Multibit number // start while Cyclic scanning expression while (true) {
// In turn expression Each character of the ch = expression.substring(index, index + 1).charAt(0);
// judge ch What is it? , Then do the corresponding treatment if (operStack.isOper(ch)) {// If it is an operator // Determine whether the current symbol stack is empty if
(!operStack.isEmpty()) {
// If the symbol stack has an operator , We'll make a comparison , If the priority of the current operator is less than or equal to the operator in the stack , You need to start from the stack pop Give two numbers ,
// From the symbol stack pop Make a symbol , Do the operation , You'll get the results , Input data stack , Then put the current operator on 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);
// The result of the operation is counted as a 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 stack operator , Just go straight to the symbol stack . operStack.push(ch); } } else { // If it is empty, direct access to symbol stack ..
operStack.push(ch); // 1 + 3 } } else { // If it's a number , Then it is directly put into the data stack //numStack.push(ch - 48);
//? "1+3" '1' => 1 // Analysis ideas //1. When dealing with multiple bits , If you can't find a number, put it on the stack immediately , Because he may be a multi digit //2.
In process number , Need to expression Of the expression index I'll see another one later , If it's a number, scan it , If it's a symbol, it's on the stack //3. So we need to define a variable
character string , For splicing // Processing multiple bits keepNum += ch; // If ch Already expression Last of all , Just go straight to the stack if (index ==
expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else {
// Determine whether the next character is a number , If it's a number , Just keep scanning , If it is an operator , Then put it on the stack // Notice the last one , no index++ if
(operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// If the last bit is an operator , Then put it on the stack keepNum = "1" perhaps "123"
numStack.push(Integer.parseInt(keepNum)); // important !!!!!! keepNum empty keepNum = "";
} } } // Give Way index + 1, And judge whether to scan expression last . index++; if (index >=
expression.length()) { break; } } // When the expression is scanned , In order Number stack and symbol stack pop The corresponding numbers and symbols are given , And running .
while (true) { // If the symbol stack is empty , Then calculate to the final result , There is only one number in the stack 【 result 】 if (operStack.isEmpty()) {
break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop();
res = numStack.cal(num1, num2, oper); numStack.push(res);// Push }
// Count the last number of the stack ,pop Out , That's the result int res2 = numStack.pop(); System.out.printf(" expression %s = %d",
expression, res2); } }
3, console output
Technology
Daily Recommendation