本篇內(nèi)容主要講解“Java中的棧實現(xiàn)方法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“Java中的棧實現(xiàn)方法”吧!

創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元東阿做網(wǎng)站,已為上家服務(wù),為東阿各地企業(yè)和個人服務(wù),聯(lián)系電話:028-86922220

棧的實現(xiàn)

棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu), 首先定義了棧需要實現(xiàn)的接口：

public interface MyStack {      /**       * 判斷棧是否為空       */     boolean isEmpty();      /**       * 清空棧       */     void clear();      /**       * 棧的長度       */     int length();      /**       * 數(shù)據(jù)入棧       */     boolean push(T data);      /**       * 數(shù)據(jù)出棧       */     T pop();  }

棧的數(shù)組實現(xiàn)，底層使用數(shù)組：

public class MyArrayStack implements MyStack {      private Object[] objs = new Object[16];      private int size = 0;       @Override     public boolean isEmpty() {          return size == 0;      }       @Override     public void clear() {          // 將數(shù)組中的數(shù)據(jù)置為null, 方便GC進行回收          for (int i = 0; i < size; i++) {              objs[size] = null;          }          size = 0;      }       @Override     public int length() {          return size;      }       @Override     public boolean push(T data) {          // 判斷是否需要進行數(shù)組擴容          if (size >= objs.length) {              resize();          }          objs[size++] = data;          return true;      }       /**       * 數(shù)組擴容       */     private void resize() {          Object[] temp = new Object[objs.length * 3 / 2 + 1];          for (int i = 0; i < size; i++) {              temp[i] = objs[i];              objs[i] = null;          }          objs = temp;      }       @SuppressWarnings("unchecked")      @Override     public T pop() {          if (size == 0) {              return null;          }          return (T) objs[--size];      }       @Override     public String toString() {          StringBuilder sb = new StringBuilder();          sb.append("MyArrayStack: [");          for (int i = 0; i < size; i++) {              sb.append(objs[i].toString());              if (i != size - 1) {                  sb.append(", ");              }          }          sb.append("]");          return sb.toString();      }  }  

棧的鏈表實現(xiàn)，底層使用鏈表：

public class MyLinkedStack implements MyStack {      /**       * 棧頂指針       */     private Node top;      /**       * 棧的長度       */     private int size;            public MyLinkedStack() {          top = null;          size = 0;      }            @Override     public boolean isEmpty() {          return size == 0;      }            @Override     public void clear() {          top = null;          size = 0;      }            @Override     public int length() {          return size;      }            @Override     public boolean push(T data) {          Node node = new Node();          node.data = data;          node.pre = top;          // 改變棧頂指針          top = node;          size++;          return true;      }            @Override     public T pop() {          if (top != null) {              Node node = top;              // 改變棧頂指針              top = top.pre;              size--;              return node.data;          }          return null;      }            /**       * 將數(shù)據(jù)封裝成結(jié)點       */     private final class Node {          private Node pre;          private T data;      }  }

兩種實現(xiàn)的比較，主要比較數(shù)據(jù)入棧和出棧的速度：

@Test public void testSpeed() {      MyStack stack = new MyArrayStack();      int num = 10000000;      long start = System.currentTimeMillis();      for (int i = 0; i < num; i++) {          stack.push(new Person("xing", 25));      }      long temp = System.currentTimeMillis();      System.out.println("push time: " + (temp - start));      while (stack.pop() != null)          ;      System.out.println("pop time: " + (System.currentTimeMillis() - temp));  }

MyArrayStack中入棧和出棧10,000,000條數(shù)據(jù)的時間：

push time：936

pop time：47

將MyArrayStack改為MyLinkedStack后入棧和出棧的時間：

push time：936

pop time：126

可見兩者的入棧速度差不多，出棧速度MyArrayStack則有明顯的優(yōu)勢。

為什么測試結(jié)果是這樣的？可能有些朋友的想法是數(shù)組實現(xiàn)的棧應(yīng)該具有更快的遍歷速度，但增刪速度應(yīng)該比不上鏈表實現(xiàn)的棧才對。但是棧中數(shù)據(jù)的增刪具有特殊性：只在棧頂入棧和出棧。也就是說數(shù)組實現(xiàn)的棧在增加和刪除元素時并不需要移動大量的元素，只是在數(shù)組擴容時需要進行復(fù)制。而鏈表實現(xiàn)的棧入棧和出棧時都需要將數(shù)據(jù)包裝成Node或者從Node中取出數(shù)據(jù)，還需要維護棧頂指針和前驅(qū)指針。

棧的應(yīng)用舉例

1. 將10進制正整數(shù)num轉(zhuǎn)換為n進制

private String conversion(int num, int n) {      MyStack myStack = new MyArrayStack();      Integer result = num;      while (true) {          // 將余數(shù)入棧          myStack.push(result % n);          result = result / n;          if (result == 0) {              break;          }      }      StringBuilder sb = new StringBuilder();      // 按出棧的順序倒序排列即可      while ((result = myStack.pop()) != null) {          sb.append(result);      }      return sb.toString();  }

2. 檢驗符號是否匹配. '['和']', '('和')'成對出現(xiàn)時字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的。

遍歷字符串的每一個char, 將char與棧頂元素比較. 如果char和棧頂元素配對, 則char不入棧, 否則將char入棧. 當遍歷完成時棧為空說明字符串是合法的。

public boolean isMatch(String str) {      MyStack myStack = new MyArrayStack();      char[] arr = str.toCharArray();      for (char c : arr) {          Character temp = myStack.pop();          // 棧為空時只將c入棧          if (temp == null) {              myStack.push(c);          }          // 配對時c不入棧          else if (temp == '[' && c == ']') {          }           // 配對時c不入棧          else if (temp == '(' && c == ')') {          }           // 不配對時c入棧          else {              myStack.push(temp);              myStack.push(c);          }      }      return myStack.isEmpty();  }

3. 行編輯: 輸入行中字符'#'表示退格, '@'表示之前的輸入全都無效。

使用棧保存輸入的字符, 如果遇到'#'就將棧頂出棧, 如果遇到@就清空棧. 輸入完成時將棧中所有字符出棧后反轉(zhuǎn)就是輸入的結(jié)果：

private String lineEdit(String input) {      MyStack myStack = new MyArrayStack();      char[] arr = input.toCharArray();      for (char c : arr) {          if (c == '#') {              myStack.pop();          } else if (c == '@') {              myStack.clear();          } else {              myStack.push(c);          }      }            StringBuilder sb = new StringBuilder();      Character temp = null;      while ((temp = myStack.pop()) != null) {          sb.append(temp);      }      // 反轉(zhuǎn)字符串      sb.reverse();      return sb.toString();  }

到此，相信大家對“Java中的棧實現(xiàn)方法”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！