文章目录
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(); //出栈 }
线性表有顺序和链式两种实现，栈同样有两种实现。
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; } }
时间复杂度分析：
- 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; } }
时间复杂度分析：
- 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
