【Java数据结构学习笔记之二】Java数据结构与算法之栈(Stack)实现
【Java数据结构学习笔记之二】Java数据结构与算法之栈(Stack)实现
Angel_Kitty
发布于 2018-04-09 15:54:11
发布于 2018-04-09 15:54:11
本篇是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> {
5
6 /**
7 * 栈是否为空
8 * @return
9 */
10 boolean isEmpty();
11
12 /**
13 * data元素入栈
14 * @param data
15 */
16 void push(T data);
17
18 /**
19 * 返回栈顶元素,未出栈
20 * @return
21 */
22 T peek();
23
24 /**
25 * 出栈,返回栈顶元素,同时从栈中移除该元素
26 * @return
27 */
28 T pop();
29 }顺序栈的设计与实现
顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然我们还可以采用内部数组实现顺序栈，在这里我们使用内部数据组来实现栈，至于以顺序表作为基础的栈实现，将以源码提供。这里先声明一个顺序栈其代码如下，实现Stack和Serializable接口：
1 /*
2 * 顺序栈的实现
3 */
4 public class SeqStack<T> implements Stack<T>,Serializable {
5
6 private static final long serialVersionUID = -5413303117698554397L;
7
8 /**
9 * 栈顶指针,-1代表空栈
10 */
11 private int top=-1;
12
13 /**
14 * 容量大小默认为10
15 */
16 private int capacity=10;
17
18 /**
19 * 存放元素的数组
20 */
21 private T[] array;
22
23 private int size;
24
25 public SeqStack(int capacity){
26 array = (T[]) new Object[capacity];
27 }
28
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);//扩容
11
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;
3
4 /*
5 * 顺序栈的实现
6 */
7 public class SeqStack<T> implements Stack<T>,Serializable {
8
9 private static final long serialVersionUID = -5413303117698554397L;
10
11 /**
12 * 栈顶指针,-1代表空栈
13 */
14 private int top=-1;
15
16 /**
17 * 容量大小默认为10
18 */
19 private int capacity=10;
20
21 /**
22 * 存放元素的数组
23 */
24 private T[] array;
25
26 private int size;
27
28 public SeqStack(int capacity){
29 array = (T[]) new Object[capacity];
30 }
31
32 public SeqStack(){
33 array= (T[]) new Object[this.capacity];
34 }
35
36 public int size(){
37 return size;
38 }
39
40
41 @Override
42 public boolean isEmpty() {
43 return this.top==-1;
44 }
45
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);//扩容
55
56 //从栈顶添加元素
57 array[++top]=data;
58
59 size++;
60 }
61
62 /**
63 * 获取栈顶元素的值,不删除
64 * @return
65 */
66 @Override
67 public T peek() {
68 if(isEmpty())
69 new EmptyStackException();
70 return array[top];
71 }
72
73 /**
74 * 从栈顶(顺序表尾部)删除
75 * @return
76 */
77 @Override
78 public T pop() {
79 if(isEmpty())
80 new EmptyStackException();
81 size--;
82 return array[top--];
83 }
84
85 /**
86 * 扩容的方法
87 * @param capacity
88 */
89 public void ensureCapacity(int capacity) {
90 //如果需要拓展的容量比现在数组的容量还小,则无需扩容
91 if (capacity<size)
92 return;
93
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 }
100
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<l;i++){
109 System.out.println("s.pop->"+s.pop());
110 }
111
112 System.out.println("s.peek->"+s.peek());
113 }
114 }链式栈的设计与实现
了解完顺序栈，我们接着来看看链式栈，所谓的链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。其操作过程如下图：
从图可以看出，无论是插入还是删除直接操作的是链表头部也就是栈顶元素，因此我们只需要使用不带头结点的单链表即可。代码实现如下，比较简单，不过多分析了：
1 import com.zejian.structures.LinkedList.singleLinked.Node;
2
3 import java.io.Serializable;
4
5 /*
6 * 栈的链式实现
7 */
8 public class LinkedStack<T> implements Stack<T> ,Serializable{
9
10 private static final long serialVersionUID = 1911829302658328353L;
11
12 private Node<T> top;
13
14 private int size;
15
16 public LinkedStack(){
17 this.top=new Node<>();
18 }
19
20 public int size(){
21 return size;
22 }
23
24
25 @Override
26 public boolean isEmpty() {
27 return top==null || top.data==null;
28 }
29
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 }
45
46 @Override
47 public T peek() {
48 if(isEmpty()){
49 throw new EmptyStackException("Stack empty");
50 }
51
52 return top.data;
53 }
54
55 @Override
56 public T pop() {
57 if(isEmpty()){
58 throw new EmptyStackException("Stack empty");
59 }
60
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-09-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录