,
Introduction to 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.
- According to the definition of stack, the first element put in the stack is at the bottom of the stack, the last element put in is at the top of the stack, while the deleted element is just the opposite. The last element put in is deleted first, and the first element is deleted last
- The concepts of pop and push are illustrated graphically
Application scenario of stack
1)
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
Go back to the original program.
2)
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 heap
Stack.
3)
Conversion of expressions
[
Infix expression to suffix expression
]
And evaluation
(
Practical solution
)
.
4)
Traversal of binary tree.
5)
Graphics depth first
(depth
one
first)
Search method.
Quick start to stack
1)
Array is used to simulate the use of stack. Since stack is an ordered list, of course, the structure of array can be used to store the data content of stack,
Next, we use array to simulate stack out, stack in and other operations.
2)
Analysis of implementation ideas
,
And draw a schematic diagram
Array simulation stack implementation
class ArrayStack{
private int top = -1; //Stack top
private int[] arr; //Array for simulation
private int maxSize; //Maximum capacity
//Initialize array
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
}
/**
* Determine whether the stack is full
* @return
*/
public boolean isFull(){
return top == maxSize-1;
}
/**
* Judge stack empty
*/
public boolean isEmpty(){
return top == -1;
}
/**
* Push
* @param num New stack value
*/
public void push(int num){
if (isFull()) {
System.out.println("Stack full");
return;
}
arr[++top] = num;
}
/**
* Out of stack
* @return Return stack top data
*/
public int pop(){
if (isEmpty()){
System.out.println("Stack empty");
return -1;
}
return arr[top--];
}
/**
* View stack top
* @return
*/
public int peek(){
if (isEmpty()){
System.out.println("Stack empty");
return -1;
}
return arr[top];
}
/**
* Traversing the stack needs to start from the top of the stack
*/
public void iteratorStack(){
if (isEmpty()){
System.out.println("Stack empty");
return;
}
for (int i = top; i > 0; i--) {
System.out.printf("%d\t",arr[i]);
}
}
}Using stack to implement a calculator
Idea:
package shangguigu2.Stack;
public class Calaculator {
public static void main(String[] args) {
//Complete the expression calculation according to the previous idea
String expression = "301+2*6-2";
ArrayStack2 numsStack = new ArrayStack2(100); //Number stack
ArrayStack2 oprStack = new ArrayStack2(100); //Symbol stack
//Define related variables
int index = 0,num1 = 0,num2 = 0,oper = 0,res = 0;
char ch = ' '; //The char obtained from each scan is saved here
String keepNum = "";//Multi bit number for splicing
//Start scanning
while (true){
//Get each character in turn
ch = expression.substring(index,index+1).charAt(0);
//Judge what ch is and deal with it accordingly
if (oprStack.isOpr(ch)){
//If it is a symbol, check whether the symbol stack is empty. If it is empty, enter it directly into the stack
if (!oprStack.isEmpty()){
//There are operators to compare the priority. If the priority of the current symbol is less than or equal to the operator in the stack
//You need to calculate from two numbers pop in the number stack and one symbol pop in the symbol stack to get the result into the number stack. Then put the current operator on the symbol stack
//If the priority of the current operator is higher than that of the operator in the stack, it is directly put into the symbol stack
if(oprStack.priority(ch) <= oprStack.priority(oprStack.peek())){
//If yes, operate from the number stack pop two numbers
num1 = numsStack.pop();
num2 = numsStack.pop();
oper = oprStack.pop();
res = numsStack.cal(num1,num2,oper);
numsStack.push(res);
//Finally, push the current symbol to the symbol stack
oprStack.push(ch);
}else {
//If the current symbol has a higher priority, it is directly put into the symbol stack
oprStack.push(ch);
}
}else {
//If it is empty, directly put it on the stack
oprStack.push(ch);
}
}else {//If it is digital processing
//numsStack.push(ch - 48); //-48 is because 1 corresponds to the ASC code table
//When processing multi bit numbers, if a number cannot be found, it will be immediately put on the stack. The situation of multi bit numbers should be considered.
//When processing the number, you need to scan several times until the symbol is scanned, so as to process the multi bit number
//Therefore, you need to define a string variable to splice multiple bits.
//Number of processing bits
keepNum+=ch;
//If it is already the last bit of the expression, it is directly put on the stack
if (index == expression.length()-1){
numsStack.push(Integer.parseInt(keepNum));
}else {
//Judge whether the next character is a number. If it is a number, continue scanning. If it is a match, enter the stack
if (oprStack.isOpr(expression.substring(index+1,index+2).charAt(0))){ //Lean back
//Stack if operator
numsStack.push(Integer.parseInt(keepNum));
//Empty keepNum
keepNum = "";
}
}
}
index++;
if (index >= expression.length()){
break;
}
}
//When the expression is scanned, the corresponding numbers and symbols are pop out from the number stack and symbol stack in sequence, and run
while (true){
//If the symbol stack is empty, the calculation ends and there is only one result in the number stack
if (oprStack.isEmpty()){
break;
}
num1 = numsStack.pop();
num2 = numsStack.pop();
oper = oprStack.pop();
res = numsStack.cal(num1,num2,oper);
numsStack.push(res);
}
System.out.println("expression:"+expression+"="+numsStack.pop());
}
}
class ArrayStack2{
private int top = -1; //Stack top
private int[] arr; //Array for simulation
private int maxSize; //Maximum capacity
//Initialize array
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
}
/**
* Determine whether the stack is full
* @return
*/
public boolean isFull(){
return top == maxSize-1;
}
/**
* Judge stack empty
*/
public boolean isEmpty(){
return top == -1;
}
/**
* Push
* @param num New stack value
*/
public void push(int num){
if (isFull()) {
System.out.println("Stack full");
return;
}
arr[++top] = num;
}
/**
* Out of stack
* @return Return stack top data
*/
public int pop(){
if (isEmpty()){
System.out.println("Stack empty");
return -1;
}
return arr[top--];
}
/**
* View stack top
* @return
*/
public int peek(){
if (isEmpty()){
System.out.println("Stack empty");
return -1;
}
return arr[top];
}
/**
* Traversing the stack needs to start from the top of the stack
*/
public void iteratorStack(){
if (isEmpty()){
System.out.println("Stack empty");
return;
}
for (int i = top; i > 0; i--) {
System.out.printf("%d\t",arr[i]);
}
}
/**
* The priority of the return operator is determined by the programmer. The higher the number, the higher the priority
*/
public int priority(int opr){
if (opr == '*' || opr == '/'){
return 1;
}else if (opr == '+' || opr == '-'){
return 0;
}
return -1;
}
/**
* Determine whether it is an operator
* @param val
* @return
*/
public boolean isOpr(char val){
return val == '+' || val == '-' || val == '*' || val == '/';
}
public int cal(int num1,int num2,int opr){
int res = 0; //Store calculation results
switch (opr){
case '+':
res = num1+num2;
break;
case '-':
res = num2-num1;
break;
case '*':
res = num1*num2;
break;
case '/':
res = num2/num1;
break;
default:
break;
}
return res;
}
}