栈之链式存储结构链栈
链栈
栈的链式存储结构成为链栈。链栈是没有头结点，头结点就是栈顶指针top。
代码结构
package list;
public interface Stackable;公共接口类
public class Node;公共结点类
class LinkedStack implements Stackable;实现栈接口的链栈类
class TestLinkedStack;测试类
公共接口类
package list;
public interface Stackable<T> {
public int Length();
public boolean isEmpty();
public boolean isFull();
public boolean Push(T element);
public T Pop();
}公共结点类
package list;
public class Node<T> {
private T data;
private Node<T> next;
Node() {
this(null,null);
}
Node(T data) {
this(data,null);
}
Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
public void setData(T data) {
this.data = data;
}
public void setNext(Node<T> next) {
this.next = next;
}
public T getData() {
return this.data;
}
public Node<T> getNext() {
return this.next;
}
public String toString() {
return getData();
}
}实现栈接口的链栈类
//链栈实现类，链栈没有头结点，当链栈为空表时，top = null;
class LinkedStack<T> implements Stackable<T> {
private Node<T> top; LinkedStack() {
this(null);
} //建链栈，element非空引用时，建带top的链栈
LinkedStack(T element) {
if(element != null) {
top = new Node<T>(element);
}
} //获取链栈，长度
public int Length() {
if(top == null) {return 0;}
else {
int k = 0;
Node<T> temp = top;
while(temp != null) {
k++;
temp = temp.getNext();
}
return k;
}
} //当top==null时，是空栈
public boolean isEmpty() {
return top == null;
} //链栈没有满栈的概念
public boolean isFull() {return false;} //压栈
public boolean Push(T element) {
if(element == null) return false;
Node<T> node = new Node<T>(element);
node.setNext(top);
top = node;
return true;
} //弹栈
public T Pop() {
if(isEmpty()) return null;
T temp = top.getData();
top = top.getNext();
return temp;
} //重写父类toString方法
public String toString() {
if(isEmpty()) return "[ ]";
int len = Length();
Node<T> temp = top;
StringBuffer sb = new StringBuffer("[ ");
while(temp != null) {
sb.append(temp.getData()+" ");
temp = temp.getNext();
}
sb.append("]");
return sb.toString();
}
}
测试类
//*****************************************************************
//*栈之链式存储结构链栈-JAVA实现
//*@author Nora-Xie
//*@time 2013-10-06PM16:20
//*****************************************************************
package list; import list.Node; public class TestLinkedStack {
public static void main(String[] args) {
Stackable<String> stack = new LinkedStack<String>("A");
System.out.println(stack.Length());
System.out.println(stack);
stack.Push("B");
stack.Push("C");
System.out.println(stack.Length()+" "+stack);
stack.Pop();
System.out.println(stack.Length()+" "+stack);
}
}
链栈和顺序栈对比
顺序栈和链栈的插入、删除操作时间复杂度都是O(1);
顺序栈需要事先确定数组的长度，有可能存在浪费内存空间的情况；
链栈虽然不需要事先确定表长，但因为需要存储链式指针，同时加大了内存开销；
因此，如果数据元素变化不可预测，时大时小，最好使用链栈；如果它的变化空间在可控范围内，则可以考虑使用顺序栈。