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

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

棧的實(shí)現(xiàn)

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

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

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

public class MyArrayStack<T> implements MyStack<T> {      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進(jìn)行回收          for (int i = 0; i < size; i++) {              objs[size] = null;          }          size = 0;      }       @Override     public int length() {          return size;      }       @Override     public boolean push(T data) {          // 判斷是否需要進(jìn)行數(shù)組擴(kuò)容          if (size >= objs.length) {              resize();          }          objs[size++] = data;          return true;      }       /**       * 數(shù)組擴(kuò)容       */     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();      }  }&nbsp;&nbsp;

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

public class MyLinkedStack<T> implements MyStack<T> {      /**       * 棧頂指針       */     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é)點(diǎn)       */     private final class Node {          private Node pre;          private T data;      }  }

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

@Test public void testSpeed() {      MyStack<Person> stack = new MyArrayStack<Person>();      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ù)的時(shí)間：

push time：936

pop time：47

將MyArrayStack改為MyLinkedStack后入棧和出棧的時(shí)間：

push time：936

pop time：126

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

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

棧的應(yīng)用舉例

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

private String conversion(int num, int n) {      MyStack<Integer> myStack = new MyArrayStack<Integer>();      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. 檢驗(yàn)符號是否匹配. '['和']', '('和')'成對出現(xiàn)時(shí)字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的。

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

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

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

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

private String lineEdit(String input) {      MyStack<Character> myStack = new MyArrayStack<Character>();      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中的棧實(shí)現(xiàn)方法”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

分享名稱：Java中的棧實(shí)現(xiàn)方法
文章轉(zhuǎn)載：http://chinadenli.net/article40/jsioho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、虛擬主機(jī)、App開發(fā)、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)