近日了解一下棧的概念，LIFO，后進先出，順手寫了幾個實現，添加泛型支持，特貼于此：
/**
* 定義一個不可變棧
*
* @author xiaomin
*
* @param <T>
*/
public class DefaultStack<T extends Serializable> implements Stack<T> {
private int size;
private Object[] values;
private int curr;
public DefaultStack(int size) {
this.size = size;
curr = -1;
values = new Object[size];
}
@Override
public void push(T t) {
if ((size - 1) == curr) {
throw new UnsupportedOperationException("The Stack is full now !");
}
curr++;
values[curr] = t;
}
@SuppressWarnings("unchecked")
@Override
public T pop() {
if (curr < 0) {
throw new UnsupportedOperationException("The Stack is empty now !");
}
return (T) values[curr--];
}
@Override
public boolean end() {
return curr == -1;
}
}
有三個實現：
/**
* 定義一個鏈接結構的棧
*
* @author xiaomin
*
* @param <T>
*/
public class LinkStack<T extends Serializable> implements Stack<T> {
/**
* 定義一個節點
*
* @author xiaomin
*
*/
private class Node implements Serializable {
private static final long serialVersionUID = 1L;
private T value;
private Node pre;
// 構造一個空值
public Node() {
value = null;
pre = null;
}
public Node(T value, Node pre) {
this.value = value;
this.pre = top;
}
}
private Node top = new Node();
@Override
public void push(T t) {
top = new Node(t, top);
}
@Override
public T pop() {
T value = top.value;
if (!end())
top = top.pre;
return value;
}
@Override
public boolean end() {
return top.value == null && top.pre == null;
}
}
/**
* 定義一個不可變棧
*
* @author xiaomin
*
* @param <T>
*/
public class DefaultStack<T extends Serializable> implements Stack<T> {
private int size;
private Object[] values;
private int curr;
public DefaultStack(int size) {
this.size = size;
curr = -1;
values = new Object[size];
}
@Override
public void push(T t) {
if ((size - 1) == curr) {
throw new UnsupportedOperationException("The Stack is full now !");
}
curr++;
values[curr] = t;
}
@SuppressWarnings("unchecked")
@Override
public T pop() {
if (curr < 0) {
throw new UnsupportedOperationException("The Stack is empty now !");
}
return (T) values[curr--];
}
@Override
public boolean end() {
return curr == -1;
}
}
/**
* 定義一個容量可變的棧
*
* @author xiaomin
*
* @param <T>
*/
public class ListStack<T extends Serializable> implements Stack<T> {
private List<T> list = null;
public ListStack() {
list = new ArrayList<T>();
}
public ListStack(int size) {
list = new ArrayList<T>(size);
}
@Override
public void push(T t) {
list.add(t);
}
@Override
public T pop() {
if (list.isEmpty()) {
throw new EmptyStackException();
}
return list.remove(list.size() - 1);
}
@Override
public boolean end() {
return list.isEmpty();
}
}
測試代碼如下：
public static void main(String[] args) {
System.out.println("link stack ...\n");
Stack<Integer> linkStack = new LinkStack<Integer>();
int times = 10;
testMethod(linkStack, times);
System.out.println("\ndefault stack ...\n");
Stack<Integer> defaultStack = new DefaultStack<Integer>(times);
testMethod(defaultStack, times);
System.out.println("\nlist stack with enouch space...\n");
Stack<Integer> listStack = new ListStack<Integer>();
testMethod(listStack, times*2);
}
private static void testMethod(Stack<Integer> linkStack, int times) {
Random random = new Random(47);
for (int i = 0; i < times; i++) {
int value = i * random.nextInt(times);
System.out.println("節點 " + (i + 1) + " : " + value);
linkStack.push(value);
}
System.out.println("*********************************");
int nums = times;
while (!linkStack.end()) {
System.out.println("節點 " + (nums--) + " : " + linkStack.pop());
}
}以上代碼簡單易懂，這里不做過多解釋。