栈的数组实现

栈是一种先进后出的数据结构, 定义栈需要实现的接口:

public interface MyStack<T> {   
    /**  
     * 判断栈是否为空  
     */  
    boolean isEmpty();   
    /**  
     * 清空栈  
     */  
    void clear();   
    /**  
     * 栈的长度  
     */  
    int length();   
    /**  
     * 数据入栈  
     */  
    boolean push(T data);   
    /**  
     * 数据出栈  
     */  
    T pop();   

    //取栈顶元素
    public T peek(); 
}  

栈的数组实现, 底层使用数组:

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() {   
        // 将数组中的数据置为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) {   
        // 判断是否需要进行数组扩容   
        if (size >= objs.length) {   
            resize();   
        }   
        objs[size++] = data;   
        return true;   
    }   
  
    /**  
     * 数组扩容  
     */  
    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];   
    }   
  

     @SuppressWarnings("unchecked")   
     @Override  
     public T peek(){
       if(size==0)
         return null;
       return (T) objs[size-1];
     }

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

栈的应用举例

1. 将10进制正整数num转换为n进制

private String conversion(int num, int n) {   
    MyStack<Integer> myStack = new MyArrayStack<Integer>();   
    Integer result = num;   
    while (true) {   
        // 将余数入栈   
        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. 检验符号是否匹配. '['和']', '('和')'成对出现时字符串合法.
例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.

  遍历字符串的每一个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();   
}  

文章来自:http://coolxing.iteye.com/blog/1468674