java中用LinkedList实现堆栈和队列

堆栈和队列

1、 堆栈

使用 LinkedList 实现堆栈：

 

/**

* 使用 LinkedList 双向链表实现堆栈

* 2008.12.21

*/

 

import java.util.LinkedList;

 

public class Stack<T> {

    private LinkedList<T> list = new LinkedList<T>();

 

    public Stack() {

    }

    public void clear() {

        list.clear();

    }

    public boolean isEmpty() {

        return list.isEmpty();

    }

    public T topElement() {

        if (isEmpty()) {

            throw new java.util.EmptyStackException();

        }

        return list.getLast();

    }

    public T pop() {

         if (isEmpty()) {

            throw new java.util.EmptyStackException();

        }

        return list.removeLast();

    }

    public void push(T element) {

        list.addLast(element);

    }

    public String toString() {

        return list.toString();

    }

}

在 java.util 包中通用型堆栈类的实现是 Vector 类的扩展，其中添加了一个构造函数以及 5 个方法。可以通过下面的声明和初始化来创建一个堆栈：

java.util.Stack stack = new java.util.stack();

注意 push() 的返回类型不是 void ，而是 Object ：压入的对象就是该方法的返回值。要读取栈顶元素而不将它从栈中删除，可以使用 peek() 方法。 Push() 和 peek() 返回的都是原始栈顶元素，而非它的复制，因此，可以使用这些方法修改栈顶元素。定义一个包含共有双精度域 d 的类 C ，那么就可以对栈顶的对象进行如下修改：

((C)stack.push(new C())).d = 12.3;

((C)stack.peek()).d = 12.3;

堆栈的 Java 实现带有潜在的危险，因为它并不是一个真正的堆栈，而只是具备和堆栈相关的方法的结构。查看 java 的源代码，可以看到它不过是继承了 Vector ： class Stack<E> extends Vector<E> ，所以它也继承了 Vector 的所有方法。实际使用中可能会有如下语句：

stack.setElementAt(new Integer(5), 1);

stack.removeElementAt(3);

这违反了堆栈的完整性。堆栈是只能在其一端访问元素的结构，而在这个 Stack 类中并非如此。

 

2、 队列

与堆栈不同，队列是两端都被使用的结构：一端用于添加新元素而另一端用于删除元素。

使用 LinkedList 实现队列：

/**

* 使用 LinkedList 双向链表实现队列

* 2008.12.21

*/

 

import java.util.LinkedList;

 

public class Queue<T> {

    private LinkedList<T> list = new LinkedList<T>();

 

    public Queue() {

    }

    public void clear() {

        list.clear();

    }

    public boolean isEmpty() {

        return list.isEmpty();

    }

    public T firstElement() {

        if (isEmpty()) {

            throw new java.util.EmptyStackException();

        }

        return list.getFirst();

    }

    public T dequeue() {

        if (isEmpty()) {

            throw new java.util.EmptyStackException();

        }

        return list.removeFirst();

    }

    public void enqueue(T element) {

        list.addLast(element);

    }

    public String toString() {

        return list.toString();

    }

}