聂永的博客

记录工作/学习的点点滴滴。

JAVA Stack(栈)学习代码

近日了解一下栈的概念,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());
}
}

以上代码简单易懂,这里不做过多解释。

posted on 2010-10-05 11:36 nieyong 阅读(2236) 评论(0)  编辑  收藏 所属分类: Java


只有注册用户登录后才能发表评论。


网站导航:
 

公告

所有文章皆为原创,若转载请标明出处,谢谢~

新浪微博,欢迎关注:

导航

<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(58)

随笔分类(130)

随笔档案(151)

个人收藏

最新随笔

搜索

最新评论

阅读排行榜

评论排行榜