快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)與算法之棧(動力節(jié)點Java學(xué)院整理)

更新時間：2017年04月12日 11:40:26 投稿：mrr

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)與算法之棧，棧是先進后出的數(shù)據(jù)的結(jié)構(gòu)，本文通過文字說明與實例代碼相結(jié)合的形式給大家介紹的非常詳細(xì)，需要的朋友跟著小編一起學(xué)習(xí)吧

stack，中文翻譯為堆棧，其實指的是棧，heap，堆。這里講的是數(shù)據(jù)結(jié)構(gòu)的棧，不是內(nèi)存分配里面的堆和棧。

棧是先進后出的數(shù)據(jù)的結(jié)構(gòu)，好比你碟子一個一個堆起來，最后放的那個是堆在最上面的。

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

棧

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

其實還是覺得設(shè)置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的數(shù)組類型改為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

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

這是可以用棧來實現(xiàn)的工具。

棧中數(shù)據(jù)入棧和出棧的時間復(fù)雜度為常數(shù)O(1)，因為與數(shù)據(jù)個數(shù)無關(guān)，直接壓入彈出，操作時間短，優(yōu)勢便在這里，如果現(xiàn)實生活的使用只需用到先進后出的順序而且只用到進出數(shù)據(jù)的比較，那就可以使用棧了。

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

您可能感興趣的文章: