数据结构：栈
- 栈的定义
- 栈的数据结构
-
- 栈的顺序存储结构
- 栈的链式存储结构
- JAVA中的栈
- 栈的应用
栈的定义
栈是一种只能在表尾进行插入或者删除操作的线性表。
允许插入和删除的一端叫栈顶，另一端叫栈底，无任何元素叫空栈（空表），是一种先入后出的线性表。
栈的插入操作叫进栈，也有叫压栈、入栈。（如图）
栈的删除操作叫出栈，也有叫弹栈。（如图）
栈的数据结构
栈的顺序存储结构
栈的顺序存储结构也是线性表的存储结构，可以用数组实现。
public class ArrayStack<T> {
private int DEFAULT_SIZE = 5;//默认大小
private Object[] objs;
private int topIndex = 0;//用来纪录当前栈顶的下标
public ArrayStack(int DEFAULT_SIZE) {
this.DEFAULT_SIZE = DEFAULT_SIZE;
objs = new Object[DEFAULT_SIZE];
}
public ArrayStack() {
objs = new Object[DEFAULT_SIZE];
}
/**
* 进栈
* @param t 进栈元素
*/
public void push(T t) {
//表示当前数组已经没有多余空间(要扩容)
if (topIndex > DEFAULT_SIZE - 1) {
objs = AddSize(objs, DEFAULT_SIZE / 2);
}
objs[topIndex] = t;
topIndex++;
}
/**
* 出栈
* @return true 表示出栈成功，false表示栈为空，出栈失败
*/
public boolean pop() {
if (topIndex < 0) {
return false;
}
//清空栈顶
objs[topIndex--] = null;
return true;
}
/**
* @param objs 表示要扩容的数组
* @param size 表示要数组要增加多大
* @return 返回扩容后的新数组
*/
private Object[] AddSize(Object[] objs, int size) {
int newSize = objs.length + size;
Object[] newObj = new Object[newSize];
System.arraycopy(objs, 0, newObj, 0, objs.length);
return newObj;
}
}
| 优点 | 缺点 |
|---|---|
| 存取定位方便 | 需要提前分配空间，当空间不足时则需要扩容，影响性能，如果不扩容就会造成溢出 |
栈的链式存储结构
栈的链式存储结构可以用线性表的链式存储结构来实现。
public class LinkStack<T> {
//表示栈的大小
private int size;
//栈顶元素
private Node top;
private class Node<T> {
private Node next;//存放后继节点
private T data;//数据域
public Node(T data, Node next) {
this.next = next;
this.data = data;
}
public Node() {
}
}
/**
* 入栈
* @param data
*/
public void push(T data) {
top = new Node<>(data, top);
size++;
}
/**
* 出栈
* @return
*/
public T pop() {
if (top == null) {
return null;
}
Node<T> node = top;
top = top.next;
node.next = null;
size--;
return node.data;
}
}
| 优点 | 缺点 |
|---|---|
| 不用提前申请空间，动态分配存储空间 | 因为多了存放指针的操作，会额外增加内存 |
总结：如果栈的元素数量固定，建议用链式存储结构，而元素数量变化不定，则建议用链式存储结构。
JAVA中的栈
JDK封装了Stack的类。位于java.util的包名下。
package java.util;
public class Stack<E> extends Vector<E> {
/**
* 无参的构造函数
*/
public Stack() {
}
/*
* 压栈
*/
public E push() {
//压栈
addElement(item);
//返回压入栈中的元素
return item;
}
/**
* 出栈
*/
public synchronized E pop() {
E obj;
int len = size();
//获取栈顶的元素
obj = peek();
//把栈顶元素置为空，并把可用数组长度减一
removeElementAt(len - 1);
return obj;
}
}
主要看压栈的方法 addElement：
//这是个线程安全的方法
public synchronized void addElement(E obj) {
modCount++;
//扩容
ensureCapacityHelper(elementCount + 1);
//压栈给栈顶赋值 lementData为vector的object[]数组
elementData[elementCount++] = obj;
}
比较复杂的是扩容的方法ensureCapacityHelper：
private void ensureCapacityHelper(int minCapacity) {
// 如果当前栈中的元素再加一比elementData的数组长度大，则需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//传入实际栈的数量
private void grow(int minCapacity) {
// 先把旧的数组长度赋值给oldCapacity
int oldCapacity = elementData.length;
//capacityIncrement 为自定义要增加的长度（扩容因子），没有设置则默认为0，stack没有设置这个变量，这里数组的长度为newCapacity =oldCapacity +oldCapacity .
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果新产生的数组长度小于实际需要的数组长度，则使用实际长度。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新产生的数组长度大于 Integer.MAX_VALUE - 8 则等于Integer.MAX_VALUE 或 者Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//真正在这里扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.copyOf方法：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
//拿到数组类型，并新建newLength长度的数组。
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//把original的数组从0开始，复制到名为copy，下标为0开始的新数组上，到original数组长度跟newLength的最小值的地方（一般都是original.length）。
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//返回带有元数据的新数组
return copy;
}
出栈方法 pop()调用了peek()与removeElementAt()
先看peek()
public synchronized E peek() {
//获取栈中元素数量
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
//直接返回数组下标为index的元素
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
再看出栈的主要方法removeElementAt：
public synchronized void removeElementAt(int index) {
//计数器加1
modCount++;
//如果下标大于数组总长度抛异常
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
//如果下标为负数抛异常
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
//获取需要复制数组元素的个数（用可用的数组减去栈顶的下标再减一，减一是因为下标是从0开始）
int j = elementCount - index - 1;
if (j > 0) {
//重新构造数组，这里主要是移除非栈顶的元素，栈没有用到。
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//有效数量键1
elementCount--;
//清空数组中最后一个元素清空
elementData[elementCount] = null; /* to let gc do its work */
}
可以看到java提供的栈stack用了线性表的顺序存储结构。
java提供的stack可以直接使用，不用关心栈溢出问题，调用stack的push()、pop(),就可以进行入栈出栈操作。
但有一个缺点是当Stack快速入栈多个元素后再恢复回来，在元素不变的前提下，其实elementCount数组的长度会增加，这个数组会一直占有着内存，造成内存浪费。
栈的应用
- Android中的atcivity栈。
- 递归函数（如斐波那契数列的实现）。
- 四则运算中的中缀表达式与后缀表达式的计算。
参考：大话数据结构
下一节 数据结构：队列