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 2022-04-15-16: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*6-4 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 2022-04-16-11:12
*/
public class Calculator {
public static void main(String[] args) {
//Define an expression
String expression = "7+2*6-4";
//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 2022-04-16-11:12
*/
public class Calculator {
public static void main(String[] args) {
//Define an expression
String expression = "7*2*2-5+1-5+3-4";
//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.