Java实现数据结构的栈和队列

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

Java代码 

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

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

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

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() {   
        // 将数组中的数据置为null, 方便GC进行回收   
        for (int i = 0; i = 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  implements MyStack { 
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 = 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  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;   
    }   
       
    /**  
     * 将数据封装成结点  
     */  
    private final class Node {   
        private Node pre;   
        private T data;   
    }   
}  

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

/** 
* 将数据封装成结点 
*/ 
private final class Node { 
private Node pre; 
private T data; 
} 
}

两种实现的比较, 主要比较数据入栈和出栈的速度:

Java代码  
@Test  
public void testSpeed() {   
    MyStack stack = new MyArrayStack();   
    int num = 10000000;   
    long start = System.currentTimeMillis();   
    for (int i = 0; i  stack = new MyArrayStack(); 
int num = 10000000; 
long start = System.currentTimeMillis(); 
for (int i = 0; i  myStack = new MyArrayStack();   
    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();   
}  

private String conversion(int num, int n) { 
MyStack myStack = new MyArrayStack(); 
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 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();   
}  

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. 行编辑: 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.

使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果: 

 
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);   
    }   
    // 反转字符串   
    sb.reverse();   
    return sb.toString();   
}  

转载出处：http://coolxing.iteye.com/blog/1468674