java与数据结构(6)---java实现链栈

栈之链式存储结构链栈

链栈

栈的链式存储结构成为链栈。链栈是没有头结点，头结点就是栈顶指针top。

代码结构

package list;

　　public interface Stackable;公共接口类

　　public class Node;公共结点类

　　class LinkedStack implements Stackable;实现栈接口的链栈类

　　class TestLinkedStack;测试类

公共接口类

 1 package list;
 2 
 3 public interface Stackable<T> {
 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 }

View Code

公共结点类

 1 package list;
 2 
 3 public class Node<T> {
 4     private T data;
 5     private Node<T> 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<T> 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<T> next) {
25         this.next = next;
26     }
27 
28     public T getData() {
29         return this.data;
30     }
31 
32     public Node<T> getNext() {
33         return this.next;
34     }
35 
36     public String toString() {
37         return getData();
38     }
39 }

View Code

实现栈接口的链栈类

 1 //链栈实现类，链栈没有头结点，当链栈为空表时，top = null;
 2 class LinkedStack<T> implements Stackable<T> {
 3     private Node<T> top;
 4     
 5     LinkedStack() {
 6         this(null);
 7     }
 8 
 9     //建链栈，element非空引用时，建带top的链栈
10     LinkedStack(T element) {
11         if(element != null) {
12             top = new Node<T>(element);
13         }
14     }
15     
16     //获取链栈，长度
17     public int Length() {
18         if(top == null) {return 0;}
19         else {
20             int k = 0;
21             Node<T> 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<T> node = new Node<T>(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<T> 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 }

View Code

测试类

 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<String> stack = new LinkedStack<String>("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 }

View Code

链栈和顺序栈对比

顺序栈和链栈的插入、删除操作时间复杂度都是O(1);

顺序栈需要事先确定数组的长度，有可能存在浪费内存空间的情况；

链栈虽然不需要事先确定表长，但因为需要存储链式指针，同时加大了内存开销；

因此，如果数据元素变化不可预测，时大时小，最好使用链栈；如果它的变化空间在可控范围内，则可以考虑使用顺序栈。