堆栈(stack)又称为栈或堆叠,是计算机科学中的一种抽象数据类型,只允许在有序的线性数据集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。
栈类似于我们现实中的客栈,用于临时存储数据。但它 LIFO 的性质不太符合人类的行为,不过却非常符合人类存放东西的行为,这导致它对于数据的临时处理非常有用。可以把它想象成子弹的弹夹、装小球的试管、咖啡店堆叠的纸杯等…
栈的基本操作
操作 | API | 描述 |
---|---|---|
添加数据 | Push |
向栈中压入数据 |
移除数据 | Pop |
从栈中弹出数据 |
查看栈顶 | Peek |
查看栈顶部的数据 |
一个基本的栈必须实现以上的 API,有的地方会写道最基本的操作是 Push
和 Pop
,但这两个仅仅只是对栈的数据操作,但我们对栈的所有操作并非一直都是数据读写操作。
Peek
操作是对栈的状态的描述之一,Peek
操作可以让我们知道栈是否为空,栈顶元素的状态,而栈的长度、栈顶一下的其他元素这些信息并不是我们必须关心的。
栈的实现
栈的实现分为两种:链表实现和顺序表实现
链表实现并不需要关心栈的容量,实现起来较为方便。顺序表实现由于在初始化栈的时候需要设定顺序表的长度,因此涉及到了判断是否栈满和是否扩容的操作。
先定义一个栈的虚基类,继承 Vector,设定好必需的 API:
public abstract class Vector<E> {
/**
* 容器当前元素数量
*/
protected int size = 0;
/**
* 判断该容器是否为空
*
* @return 为空则返回 true
*/
public synchronized boolean isEmpty() {
return this.size == 0;
}
/**
* 获取概况容器中元素的数量
*
* @return 元素的数量
*/
public synchronized int getSize() {
return this.size;
}
}
public abstract class Stack<E> extends Vector<E> {
/**
* 将元素压入栈
*
* @param element 待入栈元素
* @return 若成功入队返回 true
*/
public abstract boolean push(E element);
/**
* 弹出栈顶的元素
*
* @return 栈顶的元素
*/
public abstract E pop();
/**
* 获取栈顶部的元素
*
* @return 容器头部的元素
*/
public abstract E peek();
}
栈的链表实现
/**
* 栈的链表实现
*
* @param <E> 元素类型
*/
public class LinkedListStack<E> extends Stack<E> {
SingleLinkedListNode<E> head = new SingleLinkedListNode<>(null, null);
public LinkedListStack() {}
@Override
public synchronized boolean push(E element) {
this.head.next = new SingleLinkedListNode<>(element, this.head.next);
this.size += 1;
return true;
}
@Override
public synchronized E peek() {
if (isEmpty()) {
return null;
}
return this.head.next.data;
}
@Override
public synchronized E pop() {
if (isEmpty()) {
return null;
}
SingleLinkedListNode<E> res = this.head.next;
this.head.next = res.next;
res.next = null;
this.size -= 1;
return res.data;
}
}
栈的顺序表实现
import java.util.Arrays;
/**
* 栈的数组实现
*
* @param <E> 栈内元素类型
*/
public class ArrayStack<E> extends Stack<E> {
/**
* 栈初始容量
*/
private int capacity;
/**
* 当前栈顶元素的下标,若栈为空则为 -1
*/
private int top = -1;
/**
* 是否可扩容,若为 false,则数组容量固定无法扩容,默认可扩容
*/
private boolean isExtendible = true;
/**
* 负载因子,当数量达到容量乘以负载因子,则数组进行扩容,默认存储满员才扩容
*/
private int factor = 1;
/**
* 栈数组
*/
private Object[] elements;
/**
* 关闭无参构造函数
*/
private ArrayStack(){}
/**
* 顺序栈,默认可拓展,拓展因子为 1
*
* @param capacity 初始容量
*/
public ArrayStack(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
/**
* 顺序栈,默认可拓展
*
* @param capacity 初始容量
* @param factor 拓展因子
*/
public ArrayStack(int capacity, int factor) {
this.capacity = capacity;
this.elements = new Object[capacity];
this.factor = factor;
}
public ArrayStack(int capacity, boolean isExtendible, int factor) {
this.capacity = capacity;
this.isExtendible = isExtendible;
this.factor = isExtendible ? factor : 1;
this.elements = new Object[capacity];
}
@Override
public synchronized boolean push(E element) {
return isExtendible ? pushWithExtension(element) : pushWithoutExtension(element);
}
/**
* 入栈操作,如果栈容量不够则进行拓展
*
* @param element 待入栈元素
* @return 成功入栈返回 true
*/
private boolean pushWithExtension(E element) {
ensureCapacity();
this.size += 1;
this.elements[++top] = element;
return true;
}
/**
* 入栈操作,不进行容量拓展
*
* @param element 待入栈元素
* @return 成功入栈返回 true
*/
private boolean pushWithoutExtension(E element) {
if (this.size == this.capacity)
return false;
this.size += 1;
this.elements[++top] = element;
return true;
}
@Override
@SuppressWarnings("unchecked")
public synchronized E peek() {
if (isEmpty()) {
return null;
}
return (E) this.elements[top];
}
@Override
@SuppressWarnings("unchecked")
public synchronized E pop() {
if (isEmpty()) {
return null;
}
this.size -= 1;
return (E) this.elements[top--];
}
/**
* 调节容量,如果容量超出调节因子,则进行扩容
*/
private void ensureCapacity() {
if (this.size + 1 <= this.capacity * factor) {
return;
}
capacity += 1;
this.elements = Arrays.copyOf(this.elements, capacity);
}
}