棧的Java實現(xiàn)和棧的應(yīng)用舉例

作者：coolxing 2012-03-29 15:15:49

例子和習(xí)題出自數(shù)據(jù)結(jié)構(gòu)(嚴蔚敏版), 作者使用Java進行實現(xiàn)。轉(zhuǎn)載請注明作者和出處, 如有謬誤, 歡迎在評論中指正。

棧的實現(xiàn)

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

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

棧的數(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進行回收  
        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();  
    }  
}&nbsp;&nbsp;

棧的鏈表實現(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é)點  
     */ 
    private final class Node {  
        private Node pre;  
        private T data;  
    }  
}

兩種實現(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ù)的時間：

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<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. 檢驗符號是否匹配. '['和']', '('和')'成對出現(xiàn)時字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的。

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

public boolean isMatch(String str) {  
    MyStack<Character> myStack = new MyArrayStack<Character>();  
    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<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();  
}

原文鏈接：http://coolxing.iteye.com/blog/1468674

【編輯推薦】

實戰(zhàn)是硬道理：記Java技術(shù)面試
Java設(shè)計模式：責任鏈
Java中的Enum的使用與分析
按權(quán)重選取目標的Java算法
談?wù)凧ava的自動裝箱和拆箱

責任編輯：林師授來源： coolxing的博客

Java