I. Introduction (Stack)
1. Basic concepts
- A stack is an ordered list of entries followed by an exit
- A stack is a special kind of linear table that limits the insertion and deletion of elements in a linear table to the same end of the table. A segment that is allowed to be inserted or deleted. The changing end is the top of the stack, and the fixed end is the bottom of the stack.
- The first element on the stack is at the bottom, and the last element is at the top. Deleting elements is just the opposite.
- The two basic operations on the stack, pop and Push, are as follows:
Into the stack:
The stack:
2. Application scenarios
- Function call: Before executing the subfunction sequence, the address of the subfunction is stored on the stack until the subfunction is completed, and then the address is popped back to the original function.
- Handling recursive calls: Similar to function calls, arguments, region variables, and other data are stored on the stack in addition to the address of the child function
- Expression transformation (infix expression into postfix expression) and evaluation
- Traversal of binary trees
- Depth-first search algorithm
Two, stack code implementation
1. Analysis of ideas
2. Code implementation
// Create a new class to define the stack
class StackList{
private int maxSize; // represents the stack size
private int top; // represents the top of the stack
private int[] stack; // Define an array representing the stack
public StackList(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
// Check whether the stack is full
public boolean isFull(a){
return top == maxSize;
}
// Check whether the stack is empty
public boolean isEmpty(a){
return top == -1;
}
/ / into the stack
public void push(int value){
// Check whether the stack is full
if(isFull()){
System.out.println("Stack full ~ ~");
return;
}
top++;
stack[top] = value;
}
/ / out of the stack
public int pop(a){
// Check whether the stack is full
if(isEmpty()){
// Throw an exception
throw new RuntimeException("Stack is empty." ");
}
int value = stack[top];
top--;
return value;
}
/ / display the stack
public void show(a){
if (isEmpty()){
System.out.println("Stack empty, no data.");
return;
}
// Display data from the top of the stack
for (int i = top; top >= 0; top--){
System.out.printf("Stack[%d]=%d/n",i,stack[i]); }}}Copy the codeThe test case
public static void main(String[] args){
StackList stack = new StackList(4);
String key = "";
boolean loop = true; // Control whether to exit
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("Show: display stack");
System.out.println("Exit: Exit the program");
System.out.println("Push: stack");
System.out.println("Pop: the stack");
System.out.println("Please enter your choice");
key = scanner.next();
switch (key){
case "show":{
stack.show();
break;
}
case "exit":{
scanner.close();
loop = false;
break;
}
case "push": {
System.out.println("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; }}}}Copy the code