Java數據結構與算法之棧(動力節點Java學院整理)

stack，中文翻譯為堆棧，其實指的是棧，heap，堆。這裡講的是數據結構的棧，不是內存分配裡面的堆和棧。

棧是先進後出的數據的結構，好比你碟子一個一個堆起來，最後放的那個是堆在最上面的。

隊列就是排隊買蘋果，先去的那個可以先買。

棧

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(); 
   } 
 } 

其實還是覺得設置top為-1好計算一點，記住這裡的i++和++i，如果i=1，那麼array[i++]=2，指的是array[1]=2，下次用到i的時候i的值才會變2，而++i就是直接使用i=2。

top指向0，因為每次都push一個元素加一，那麼添加到最後一個元素的時候top=max。由於先進後出，那麼先出的是最後進的，剛剛為top-1所在的位置。

正確輸出：

 5 
 5 
 5 
 3 
 1 

一、棧的使用——單詞逆序。

 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));      
   } 

將Stack的數組類型改為char即可。

讀取輸入也可以用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)); 
 } 

二、棧的使用——分隔符匹配。

 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 

將({[先壓入棧，一旦遇到)}]便與彈出的元素比較，若吻合，則匹配。如果一直沒有)}]，最後便會彈出棧的左符號，提示是在具體哪個位置，缺少的具體的右符號類型。

這是可以用棧來實現的工具。

棧中數據入棧和出棧的時間復雜度為常數O(1)，因為與數據個數無關，直接壓入彈出，操作時間短，優勢便在這裡，如果現實生活的使用只需用到先進後出的順序而且只用到進出數據的比較，那就可以使用棧了。

以上所述是小編給大家介紹的Java數據結構與算法之棧(動力節點Java學院整理)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對網站的支持！