Java数据结构学习笔记之二Java数据结构与算法之栈(Stack)实现详解编程语言

  本篇是java数据结构与算法的第2篇，从本篇开始我们将来了解栈的设计与实现，以下是本篇的相关知识点：

  栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：

由图我们可看成栈只能从栈顶存取元素，同时先进入的元素反而是后出，而栈顶永远指向栈内最顶部的元素。到此可以给出栈的正式定义：栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。栈的基本操作创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不支持对指定位置进行删除，插入，其接口Stack声明如下：

 1 /* 

 2 * 栈接口抽象数据类型 

 3 */ 

 4 public interface Stack T { 

 6 /** 

 7 * 栈是否为空 

 8 * @return 

 9 */ 

10 boolean isEmpty(); 

12 /** 

13 * data元素入栈 

14 * @param data 

15 */ 

16 void push(T data); 

18 /** 

19 * 返回栈顶元素,未出栈 

20 * @return 

21 */ 

22 T peek(); 

24 /** 

25 * 出栈,返回栈顶元素,同时从栈中移除该元素 

26 * @return 

27 */ 

28 T pop(); 

29 }

  顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然我们还可以采用内部数组实现顺序栈，在这里我们使用内部数据组来实现栈，至于以顺序表作为基础的栈实现，将以源码提供。这里先声明一个顺序栈其代码如下，实现Stack和Serializable接口：

 1 /* 

 2 * 顺序栈的实现 

 3 */ 

 4 public class SeqStack T implements Stack T ,Serializable { 

 6 private static final long serialVersionUID = -5413303117698554397L; 

 8 /** 

 9 * 栈顶指针,-1代表空栈 

10 */ 

11 private int top=-1; 

13 /** 

14 * 容量大小默认为10 

15 */ 

16 private int capacity=10; 

18 /** 

19 * 存放元素的数组 

20 */ 

21 private T[] array; 

23 private int size; 

25 public SeqStack(int capacity){ 

26 array = (T[]) new Object[capacity]; 

27 } 

29 public SeqStack(){ 

30 array= (T[]) new Object[this.capacity]; 

31 } 

32 //.......省略其他代码 

33 }

其获取栈顶元素值的peek操作过程如下图（未删除只获取值）：

以上是获取栈顶元素的操作，代码如下：

 1 /** 

 2 * 获取栈顶元素的值,不删除 

 3 * @return 

 4 */ 

 5 @Override 

 6 public T peek() { 

 7 if(isEmpty()) 

 8 new EmptyStackException(); 

 9 return array[top]; 

10 }

从栈添加元素的过程如下（更新栈顶top指向）：

以上是入栈操作，代码如下：

 1 /** 

 2 * 添加元素,从栈顶(数组尾部)插入 

 3 * 容量不足时，需要扩容 

 4 * @param data 

 5 */ 

 6 @Override 

 7 public void push(T data) { 

 8 //判断容量是否充足 

 9 if(array.length==size) 

10 ensureCapacity(size*2+1);//扩容 

12 //从栈顶添加元素 

13 array[++top]=data; 

14 }

栈弹出栈顶元素的过程如下（删除并获取值）：

以上是出栈操作，代码如下：

 1 /** 

 2 * 从栈顶(顺序表尾部)删除 

 3 * @return 

 4 */ 

 5 @Override 

 6 public T pop() { 

 7 if(isEmpty()) 

 8 new EmptyStackException(); 

 9 size--; 

10 return array[top--]; 

11 }

到此，顺序栈的主要操作已实现完，是不是发现很简单，确实如此，栈的主要操作就这样，当然我们也可以通过前一篇介绍的MyArrayList作为基础来实现顺序栈，这个也比较简单，后面也会提供带代码，这里就不过多啰嗦了。下面给出顺序栈的整体实现代码：

 1 import java.io.Serializable; 

 2 import java.util.EmptyStackException; 

 4 /* 

 5 * 顺序栈的实现 

 6 */ 

 7 public class SeqStack T implements Stack T ,Serializable { 

 9 private static final long serialVersionUID = -5413303117698554397L; 

 11 /** 

 12 * 栈顶指针,-1代表空栈 

 13 */ 

 14 private int top=-1; 

 16 /** 

 17 * 容量大小默认为10 

 18 */ 

 19 private int capacity=10; 

 21 /** 

 22 * 存放元素的数组 

 23 */ 

 24 private T[] array; 

 26 private int size; 

 28 public SeqStack(int capacity){ 

 29 array = (T[]) new Object[capacity]; 

 30 } 

 32 public SeqStack(){ 

 33 array= (T[]) new Object[this.capacity]; 

 34 } 

 36 public int size(){ 

 37 return size; 

 38 } 

 41 @Override 

 42 public boolean isEmpty() { 

 43 return this.top==-1; 

 44 } 

 46 /** 

 47 * 添加元素,从栈顶(数组尾部)插入 

 48 * @param data 

 49 */ 

 50 @Override 

 51 public void push(T data) { 

 52 //判断容量是否充足 

 53 if(array.length==size) 

 54 ensureCapacity(size*2+1);//扩容 

 56 //从栈顶添加元素 

 57 array[++top]=data; 

 59 size++; 

 60 } 

 62 /** 

 63 * 获取栈顶元素的值,不删除 

 64 * @return 

 65 */ 

 66 @Override 

 67 public T peek() { 

 68 if(isEmpty()) 

 69 new EmptyStackException(); 

 70 return array[top]; 

 71 } 

 73 /** 

 74 * 从栈顶(顺序表尾部)删除 

 75 * @return 

 76 */ 

 77 @Override 

 78 public T pop() { 

 79 if(isEmpty()) 

 80 new EmptyStackException(); 

 81 size--; 

 82 return array[top--]; 

 83 } 

 85 /** 

 86 * 扩容的方法 

 87 * @param capacity 

 88 */ 

 89 public void ensureCapacity(int capacity) { 

 90 //如果需要拓展的容量比现在数组的容量还小,则无需扩容 

 91 if (capacity size) 

 92 return; 

 94 T[] old = array; 

 95 array = (T[]) new Object[capacity]; 

 96 //复制元素 

 97 for (int i=0; i size ; i++) 

 98 array[i]=old[i]; 

 99 } 

101 public static void main(String[] args){ 

102 SeqStack String s=new SeqStack (); 

103 s.push("A"); 

104 s.push("B"); 

105 s.push("C"); 

106 System.out.println("size- "+s.size()); 

107 int l=s.size();//size 在减少,必须先记录 

108 for (int i=0;i i++){ 

109 System.out.println("s.pop- "+s.pop()); 

110 } 

112 System.out.println("s.peek- "+s.peek()); 

113 } 

114 }

  了解完顺序栈，我们接着来看看链式栈，所谓的链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。其操作过程如下图：

从图可以看出，无论是插入还是删除直接操作的是链表头部也就是栈顶元素，因此我们只需要使用不带头结点的单链表即可。代码实现如下，比较简单，不过多分析了：

 1 import com.zejian.structures.LinkedList.singleLinked.Node; 

 3 import java.io.Serializable; 

 5 /* 

 6 * 栈的链式实现 

 7 */ 

 8 public class LinkedStack T implements Stack T ,Serializable{ 

10 private static final long serialVersionUID = 1911829302658328353L; 

12 private Node T top; 

14 private int size; 

16 public LinkedStack(){ 

17 this.top=new Node (); 

18 } 

20 public int size(){ 

21 return size; 

22 } 

25 @Override 

26 public boolean isEmpty() { 

27 return top==null || top.data==null; 

28 } 

30 @Override 

31 public void push(T data) { 

32 if (data==null){ 

33 throw new StackException("data can/t be null"); 

34 } 

35 if(this.top==null){//调用pop()后top可能为null 

36 this.top=new Node (data); 

37 }else if(this.top.data==null){ 

38 this.top.data=data; 

39 }else { 

40 Node T p=new Node (data,this.top); 

41 top=p;//更新栈顶 

42 } 

43 size++; 

44 } 

46 @Override 

47 public T peek() { 

48 if(isEmpty()){ 

49 throw new EmptyStackException("Stack empty"); 

50 } 

52 return top.data; 

53 } 

55 @Override 

56 public T pop() { 

57 if(isEmpty()){ 

58 throw new EmptyStackException("Stack empty"); 

59 } 

61 T data=top.data; 

62 top=top.next; 

63 size--; 

64 return data; 

65 } 

66 //测试 

67 public static void main(String[] args){ 

68 LinkedStack String sl=new LinkedStack (); 

69 sl.push("A"); 

70 sl.push("B"); 

71 sl.push("C"); 

72 int length=sl.size(); 

73 for (int i = 0; i length; i++) { 

74 System.out.println("sl.pop- "+sl.pop()); 

75 } 

76 } 

77 }

11884.html