重学数据结构（二、栈）
1、栈的定义和特点
栈(Stack)又称堆栈， 是限制在表的一端进行插入和删除运算的线性表。
如果要拿一个东西对比，羽毛球筒比较合适。
栈遵循后进先出（ Last-in-first-out，LIFO）的原则。
比如上面的羽毛球筒，只能将最顶端的羽毛球移出，也只能将新的羽毛球放到最顶端——这两种操作分别称作入栈（ Push）和出栈（ Pop）。入栈和出栈的示意图如下：
最顶端的羽毛球叫栈顶栈顶 (top),最底端的羽毛球称为栈底 (bottom)。
2、栈的基本操作
栈的基本操作除了入栈和出栈外， 还有栈的初始化、 栈空的判定， 以及取栈顶元素等。
根据这些操作，我们定义一个接口：
/**
* @Author 三分恶
* @Date 2020/8/26
* @Description 栈接口
*/
public interface Stack { public int getSize(); //返回栈中元素数目 public boolean isEmpty(); //判空 public Object top(); //取栈顶元素但不删除 public void push(Object element); //入栈 public Object pop(); //出栈
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
线性表有顺序和链式两种实现，栈同样有两种实现。
3、顺序栈
这里我们通过一个可扩容的数组来实现。
/**
* @Author 三分恶
* @Date 2020/8/26
* @Description 顺序栈--数组实现
*/
public class ArrayStack implements Stack{ private static int defaultSize=15; //默认容量 private int size; //实际容量：实际存储元素个数 private Object[] data; //存放元素的数组 /** * 无参构造方法：按默认容量构造元素数组 */ public ArrayStack() { data=new Object[defaultSize]; size=0; } /** * 有参构造方法：指定元素数组容量 * @param size */ public ArrayStack(int size){ data=new Object[size]; } public int getSize() { return size; } public boolean isEmpty() { return size==0; } /** * 取栈顶元素:不删除栈顶元素 * @return */ public Object top() { if (isEmpty()) throw new RuntimeException("栈空"); size--; return data[size-1]; } /** * 入栈 * @param element */ public void push(Object element) { //数组已满，扩容 if (size==data.length){ //扩容两倍的新数组 Object [] newData=new Object[size<<1]; //拷贝数组 System.arraycopy(data,0,newData,0,size); data=newData; } //栈顶上插入新元素 data[size]=element; size++; } /** * 出栈 * @return */ public Object pop() { if (isEmpty()) throw new RuntimeException("栈空"); Object top=data[size-1]; data[size-1]=null; size--; return top; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
时间复杂度分析：
- getSize()：O(1)
- isEmpty()：O(1)
- top()：O(1)
- push()：平均O(1)，最坏（扩容）O(n)
- pop(): O(1)
3、链栈
链栈指的是链式存储结构实现的栈。在前面的学习中，我们已经完成了单向链表的实现，代码如下，具体说明可查看上一篇内容：
现在我们通过单向链表来实现链栈：
/**
* @Author 三分恶
* @Date 2020/8/26
* @Description
*/
public class ListStack implements Stack{ //单向链表 private SinglyLinkedList list; /** * 构造函数：初始化单向链表 */ public ListStack(){ list=new SinglyLinkedList(); } /** * 获取栈的容量 * @return */ public int getSize() { return list.getSize(); } public boolean isEmpty() { return list.getSize()==0; } /** * 取栈顶元素 * @return */ public Object top() { //取列表的尾节点 return list.get(list.getSize()-1); } /** * 入栈 * @param element */ public void push(Object element) { //队列尾插入 list.addTail(element); } /** * 出栈 * @return */ public Object pop() { int topIndex=list.getSize()-1; //列表为节点 Object top=list.get(topIndex); //删除尾结点 list.remove(topIndex); return top; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
时间复杂度分析：
- getSize()：O(1)
- isEmpty()：O(1)
- top()：O(1)
- push()：O(1)
- pop(): O(1)
4、java中的栈
在Java中有一个java.util.Stack类，它实现了栈的结构。
它是Vector的子类，也自定义了一些作为栈的方法。
java.util.Stack类是Vector的子类，实际上并不建议使用它。
在Java中还有另外一个集合，可以作为栈使用，它就是LinkedList。LinkedList中实现了push、pop方法。具体可以查看LinkedList源码阅读笔记。
源码地址：https://gitee.com/LaughterYoung/data-structure-learn.git
上一篇：重学数据结构（一、线性表）
下一篇：重学数据结构（三、队列）
本文为学习笔记类博客，主要资料来源如下！
参考：
【1】：邓俊辉 编著. 《数据结构与算法》
【2】：王世民 等编著 . 《数据结构与算法分析》
【3】： Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】：严蔚敏、吴伟民 编著 . 《数据结构》
【5】：程杰 编著 . 《大话数据结构》
【6】：Java Stack 类
文章来源: blog.csdn.net，作者：三分恶，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/sinat_40770656/article/details/108197144
- 点赞
- 收藏
- 关注作者
评论（0）