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