09、数据结构与算法 - 实战：栈
栈（stack）是一个有序线性表，只能在表的一端（成为栈顶，top）执行插入和删除操作。最后插入的元素是第一个被删除的。所以栈也称为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out，FILO）线性表。
两个栈操作都有专用名称，一个称为入栈（push），表示在栈中插入一个元素；另一个称为出栈（pop），表示从栈中删除一个元素。
试图对一个空栈执行出栈操作称为下溢（underflow）；试图对一个满栈执行插入操作称为溢出（overflow）。
常用的实现方式：
1、 基于简单数组的实现方式；
2、 基于动态数组的实现方式；
3、 基于链表的实现方式；
简单数组的实现有一个局限性，就是栈的最大空间必须预先声明且不能改变。一旦对满栈执行入栈操作将出现溢出异常。
/**
* 简单数组实现栈
*/
public class ArrayStack {
/**
* 栈顶
*/
private int top;
/**
* 栈的容量
*/
private int capacity;
/**
* 实现栈的数组
*/
private int[] array;
/**
* 无参构造方法
*/
public ArrayStack() {
this.capacity = 1;
this.array = new int[this.capacity];
this.top = -1;
}
/**
* 有参构造方法
* @param capacity 数组的大小
*/
public ArrayStack(int capacity) {
this.capacity = capacity;
this.array = new int[this.capacity];
this.top = -1;
}
/**
* 判断栈是否为空
* @return true 是空栈 false 不是空栈
*/
public boolean isEmpty() {
return (top == -1);
}
/**
* 判断栈是否已满
* @return true 是满栈 false 不是满栈
*/
public boolean isFull() {
return (top == (capacity - 1));
}
/**
* 获取栈中元素个数
* @return 栈中元素个数
*/
public int size() {
return (top + 1);
}
/**
* 入栈
* @param data 需要入栈的数据
*/
public void push(int data) {
if (isFull()) {
System.out.println("栈溢出！");
} else {
top++;
array[top] = data;
}
}
/**
* 出栈
* @return 出栈数据
*/
public int pop() {
if (isEmpty()) {
System.out.println("栈为空！");
return -999; // 栈为空时一般约定返回一个不常用的数
} else {
return array[top--];
}
}
/**
* 删除栈
*/
public void deleteStack() {
top = -1;
}
}
动态数组的实现可以采用重复倍增技术提高性能。如果当前数组空间已满，就新建一个比原数组大一倍的新数组，然后复制元素。
注意：倍增太多可能导致内存溢出。
/**
* 动态数组实现栈
*/
public class DynArrayStack {
/**
* 栈顶
*/
private int top;
/**
* 栈的容量
*/
private int capacity;
/**
* 实现栈的数组
*/
private int[] array;
/**
* 无参构造方法
*/
public DynArrayStack() {
this.capacity = 1;
this.array = new int[this.capacity];
this.top = -1;
}
/**
* 有参构造方法
* @param capacity 数组的大小
*/
public DynArrayStack(int capacity) {
this.capacity = capacity;
this.array = new int[this.capacity];
this.top = -1;
}
/**
* 判断栈是否为空
* @return true 是空栈 false 不是空栈
*/
public boolean isEmpty() {
return (top == -1);
}
/**
* 判断栈是否已满
* @return true 是满栈 false 不是满栈
*/
public boolean isFull() {
return (top == (capacity - 1));
}
/**
* 获取栈中元素个数
* @return 栈中元素个数
*/
public int size() {
return (top + 1);
}
/**
* 入栈
* @param data 需要入栈的数据
*/
public void push(int data) {
if (isFull()) {
// 如果栈满了就倍增扩容
doubleStack();
}
top++;
array[top] = data;
}
/**
* 数组动态扩容，采用重复倍增
*/
private void doubleStack() {
// 创建新的数组，大小为原来数组的两倍
int[] newArray = new int[2 * capacity];
// 复制原数组到新数组
System.arraycopy(array, 0, newArray, 0, capacity);
// 重置数组容量
capacity = capacity * 2;
// 复制给原数组，也就是使array指向新生成内存
array = newArray;
}
/**
* 出栈
* @return 出栈数据
*/
public int pop() {
if (isEmpty()) {
System.out.println("栈为空！");
return -999; // 栈为空时一般约定返回一个不常用的数
} else {
return array[top--];
}
}
/**
* 删除栈
*/
public void deleteStack() {
top = -1;
}
}
通过在表头插入元素的方式实现push操作，删除表头元素实现pop操作。
/**
* 链表实现栈(使用泛型)
*/
public class LinkedListStack<AnyType> {
/**
* 栈顶
*/
private ListNode<AnyType> headNode;
/**
* 无参构造方法
*/
public LinkedListStack() {
headNode = null;
}
/**
* 有参构造方法
*/
public LinkedListStack(AnyType data) {
this.headNode = new ListNode<AnyType>(data);
}
/**
* 判断栈是否为空
* @return true 是空栈 false 不是空栈
*/
public boolean isEmpty() {
return (headNode == null);
}
/**
* 获取栈中元素个数
* @return 栈中元素个数
*/
public int size() {
int size = 0;
ListNode<AnyType> currentNode = headNode;
while (currentNode != null) {
size++;
currentNode = currentNode.getNext();
}
return size;
}
/**
* 入栈
* @param data 需要入栈的数据
*/
public void push(AnyType data) {
if (isEmpty()) {
headNode = new ListNode<AnyType>(data);
} else if (headNode.getData() == null){
headNode.setData(data);
} else {
ListNode<AnyType> newNode = new ListNode<AnyType>(data);
newNode.setNext(headNode);
// 更新栈顶
headNode = newNode;
}
}
/**
* 输出栈顶元素
* @return 栈顶元素
*/
public AnyType top() {
if (isEmpty()) {
return null;
} else {
return headNode.getData();
}
}
/**
* 出栈
* @return 出栈数据
*/
public AnyType pop() {
if (isEmpty()) {
System.out.println("栈为空！");
return null;
} else {
AnyType data = headNode.getData();
headNode = headNode.getNext();
return data;
}
}
/**
* 删除栈
*/
public void deleteStack() {
headNode = null;
}
}