Java Data Structure and Algorithm stack of Power Node Java College collation

stack, Chinese translation stack, actually refers to the stack, heap, heap. We're talking about the stack of data structures, not the heap and stack in memory allocation.

A stack is a structure of data that comes in and goes out, as if you were stacking dishes one by one, with the last one on top.

A queue is a queue to buy apples. The one who goes first can buy first.

The stack

public class Stack { 
   private int array[]; 
   private int max; 
   private int top; 
   public Stack(int max){ 
     this.max = max; 
     array = new int[max]; 
     top = 0; 
   } 
   public void push(int value){ 
     if(isFull()){ 
       System.out.println("full,can not insert"); 
       return; 
     } 
     array[top++]=value; 
   } 
   public int pop(){ 
     return array[--top]; 
   } 
   public boolean isEmpty(){ 
     if(top == 0){ 
       return true; 
     } 
     return false; 
   } 
   public boolean isFull(){ 
     if(top == max ){ 
       return true; 
     } 
     return false; 
   } 
   public void display(){ 
     while(!isEmpty()){ 
       System.out.println(pop()); 
     } 
   } 
   public static void main(String[] args) { 
     Stack s = new Stack(5); 
     s.push(1); 
     s.push(3); 
     s.push(5); 
     s.push(5); 
     s.push(5); 
     s.display(); 
   } 
 } 

Remember i++ and ++i. If i=1, then array[i++]=2, array[1]=2. The next time you use i, i will change to 2.

top points to 0, because every time you add 1 to push1, you add top=max to the last element. As the first in and then out, the first out is the last in, just where the ES30en-1 is.

Correct output:

5
5
5
3
1

1. Use of stacks -- Reverse word order.

 public String reverse(String in){ 
     String out=""; 
     for (int i = 0; i < in.length(); i++) { 
       char c = in.charAt(i); 
       push(c); 
     } 
     while(!isEmpty()){ 
       out+=pop(); 
     } 
     return out; 
   } 
   public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     String string = s.nextLine(); 
     Stack st = new Stack(string.length()); 
     System.out.println(st.reverse(string));      
   } 

Change the array type of Stack to char.

Read input can also be read with IO.

 public static void main(String[] args) { 
   InputStreamReader is = new InputStreamReader(System.in); 
   BufferedReader b = new BufferedReader(is); 
   String string=""; 
   try { 
     string = b.readLine(); 
   } catch (IOException e) { 
     e.printStackTrace(); 
   } 
   Stack st = new Stack(string.length()); 
   System.out.println(st.reverse(string)); 
 } 

2. Use of the stack -- delimiter matching.

 public int charat(char c){ 
   for (int i = 0; i < array.length; i++) { 
     if(c == array[i]) 
       return i; 
   } 
   return array.length; 
 } 
 public void match(String in){ 
   String out=""; 
   for (int i = 0; i < in.length(); i++) { 
     char c = in.charAt(i); 
     if(c == '{' || c == '(' || c == '[' ){ 
       push(c); 
     } 
     if(c == '}' || c == ')' || c == ']'){ 
       char temp = pop(); 
      if(c == '}' && temp != '{'|| c == ')' && temp != '('|| c == ']' && temp != ']'){ 
         System.out.println("can not match in "+i); 
       } 
     } 
   } 
   while(!isEmpty()){ 
     char c = pop(); 
     if(c == '{'){ 
       System.out.println("insert } to match "+charat(c)); 
     } 
     if(c == '[' ){ 
       System.out.println("insert ] to match "+charat(c)); 
     } 
     if(c == '(' ){ 
       System.out.println("insert ) to match "+charat(c)); 
     } 
   } 
 } 
 public static void main(String[] args) { 
   Scanner s = new Scanner(System.in); 
   String string = s.nextLine(); 
   Stack st = new Stack(string.length()); 
   st.match(string); 
 } 
 result :  
 klsjdf(klj{lkjjsdf{) 
 can not match in 19 
 insert } to match 1 
 insert ) to match 0 

Compare ({[first push, once encountered)}] with the element that pops out. If it matches, it matches. If 1 is not)}], the left symbol of the stack will pop up at the end, indicating the specific location of the missing specific right symbol type.

This is a tool that can be implemented using the stack.

The time complexity of data push and push in the stack is constant O(1), because it has nothing to do with the number of data, direct press and pop out, short operation time, the advantage is here, if the use of real life only needs the order of in and out and only the comparison of data in and out, then the stack can be used.