栈的特点

1. 先进后出（FILO）或者  后进先出（LIFO）
2. 增删元素皆是在栈顶操作
3. 一次只能删除一个数据项：当前栈顶元素
4. 只允许访问一个数据项：当前栈顶元素

---

 

所需条件

1. 一个链结点类Link，里面包含了需要存储的数据data和一个Link类型的引用变量next
2. 一个封装了链表操作元素的行为类MyLinkList，里面包含了一个Link类型的引用变量first和若干个方法

---

 

分析实现

　确定栈具有的功能：入栈push()、出栈pop()、查看栈顶元素getTop()、判空isEmpty()、判长length()、清空clear()

---

 

代码实现

1. Link类

1 public class Link { 2  3     public Object data; 4     public Link next; 5  6     public Link(Object data) { 7         this.data = data; 8         this.next = null; 9     }10 11     public void displayLink() {12         System.out.print(data + "\t");13     }14 }

 

2. MyLinkList类

1 public class MyListList { 2  3     private Link first; 4  5     /** 6      * 判断链表是否为空 7      * @return 8      */ 9     public boolean isEmpty() {10         return (first == null);11     }12 13     /**14      * 在头结点处插入元素15      * @param data16      */17     public void insertFirst(Object data) {18         Link newLink = new Link(data);19         newLink.next = first;20         first = newLink;21     }22 23     /**24      * 删除头结点25      * @return26      */27     public Object deleteFirst() {28         if (isEmpty()) {29             return null;30         }31         Link temp = first;32         first = first.next;33         return temp.data;34     }35 36     /**37      * 获得头结点存储的数据38      * @return39      */40     public Object getFirstData() {41         return first.data;42     }43     44     /**45      * 获得链表的长度46      * @return47      */48     public int length() {49         Link current = first;50         int count = 0;51         while (current != null) {52             count++;53             current = current.next;54         }55         return count;56     }57 58     /**59      * 清空链表60      */61     public void clearList() {62         Link current = first;63         while (current != null) {64             deleteFirst();65             current = current.next;66         }67     }68 }

 

3. 链栈类

1 public class LinkStack { 2  3     private MyListList myListList; 4  5     public LinkStack() { 6         this.myListList = new MyListList(); 7     } 8  9     public boolean isEmpty(){10         return myListList.isEmpty();11     }12 13     public void push(Object data) {14         myListList.insertFirst(data);15     }16 17     public Object pop() {18         return myListList.deleteFirst();19     }20 21     public void clear() {22         myListList.clearList();23     }24 25     public int length() {26         return myListList.length();27     }28 29     public Object getTop() {30         return myListList.getFirstData();31     }32 }

 

4. 测试

1 public class LinkStackTest { 2  3     public static void main(String[] args) { 4  5         LinkStack linkStack = new LinkStack(); 6  7         System.out.println( "栈是否为空? " + linkStack.isEmpty()); 8  9         linkStack.push(10);10         linkStack.push(20);11         linkStack.push(30);12         linkStack.push(0);13 14         System.out.println("栈长: " + linkStack.length());15 16         System.out.println("栈顶元素: " + linkStack.getTop());17 18         // 清空栈19         linkStack.clear();20 21         System.out.println( "栈是否为空? " + linkStack.isEmpty());22 23         linkStack.push(2);24         linkStack.push(1);25         linkStack.push(6);26         linkStack.push(3);27         linkStack.push(5);28         // 取出栈元素，并打印29         while(!linkStack.isEmpty()){30             Object pop = linkStack.pop();31             System.out.print(pop + "\t");32         }33         System.out.println();34     }35 }

 

5. 结果

栈是否为空? true栈长: 4栈顶元素: 0栈是否为空? true5    3    6    1    2

 

---

 

总结

1. 使用链表作为底层实现，可以任意扩容，这一点比用数组实现好太多；
2. 插入、查找、删除所需时间都是O(1)，因为都是对栈顶元素操作。

---

 

对比链接：

 

---