栈之链式存储结构链栈
链栈
栈的链式存储结构成为链栈。链栈是没有头结点，头结点就是栈顶指针top。
代码结构
package list;
public interface Stackable;公共接口类
public class Node;公共结点类
class LinkedStack implements Stackable;实现栈接口的链栈类
class TestLinkedStack;测试类
公共接口类
1 package list; 2 3 public interface Stackable{ 4 5 public int Length(); 6 7 public boolean isEmpty(); 8 9 public boolean isFull();10 11 public boolean Push(T element);12 13 public T Pop();14 15 }
公共结点类
1 package list; 2 3 public class Node{ 4 private T data; 5 private Node next; 6 7 Node() { 8 this(null,null); 9 }10 11 Node(T data) {12 this(data,null);13 }14 15 Node(T data, Node next) {16 this.data = data;17 this.next = next;18 }19 20 public void setData(T data) {21 this.data = data;22 }23 24 public void setNext(Node next) {25 this.next = next;26 }27 28 public T getData() {29 return this.data;30 }31 32 public Node getNext() {33 return this.next;34 }35 36 public String toString() {37 return getData();38 }39 }
实现栈接口的链栈类
1 //链栈实现类，链栈没有头结点，当链栈为空表时，top = null; 2 class LinkedStackimplements Stackable { 3 private Node top; 4 5 LinkedStack() { 6 this(null); 7 } 8 9 //建链栈，element非空引用时，建带top的链栈10 LinkedStack(T element) {11 if(element != null) {12 top = new Node (element);13 }14 }15 16 //获取链栈，长度17 public int Length() {18 if(top == null) { return 0;}19 else {20 int k = 0;21 Node temp = top;22 while(temp != null) {23 k++;24 temp = temp.getNext();25 }26 return k;27 }28 }29 30 //当top==null时，是空栈31 public boolean isEmpty() {32 return top == null;33 }34 35 //链栈没有满栈的概念36 public boolean isFull() { return false;}37 38 //压栈39 public boolean Push(T element) {40 if(element == null) return false;41 Node node = new Node (element);42 node.setNext(top);43 top = node;44 return true;45 }46 47 //弹栈48 public T Pop() {49 if(isEmpty()) return null;50 T temp = top.getData();51 top = top.getNext();52 return temp;53 }54 55 //重写父类toString方法56 public String toString() {57 if(isEmpty()) return "[ ]";58 int len = Length();59 Node temp = top;60 StringBuffer sb = new StringBuffer("[ ");61 while(temp != null) {62 sb.append(temp.getData()+" ");63 temp = temp.getNext();64 }65 sb.append("]");66 return sb.toString();67 }68 }
测试类
1 //***************************************************************** 2 //*栈之链式存储结构链栈-JAVA实现 3 //*@author Nora-Xie 4 //*@time 2013-10-06PM16:20 5 //***************************************************************** 6 package list; 7 8 import list.Node; 9 10 public class TestLinkedStack {11 public static void main(String[] args) {12 Stackable stack = new LinkedStack ("A");13 System.out.println(stack.Length());14 System.out.println(stack);15 stack.Push("B");16 stack.Push("C");17 System.out.println(stack.Length()+" "+stack);18 stack.Pop();19 System.out.println(stack.Length()+" "+stack);20 }21 } 链栈和顺序栈对比
顺序栈和链栈的插入、删除操作时间复杂度都是O(1);
顺序栈需要事先确定数组的长度，有可能存在浪费内存空间的情况；
链栈虽然不需要事先确定表长，但因为需要存储链式指针，同时加大了内存开销；
因此，如果数据元素变化不可预测，时大时小，最好使用链栈；如果它的变化空间在可控范围内，则可以考虑使用顺序栈。