2.栈(stack) ——————本质为："线性表"
栈是限定仅在表尾进行'插入'和'删除'的线性表。允许插入和删除的一端称为栈顶(top)，另一端则称为栈底(bottom)，不含任何元素的栈称为'空栈'。
主要基本操作：
① 初始化
② 入栈(进栈、压栈、插入)
③ 出栈(弹栈、删除)
④ 获取 —— 取栈顶数据元素。注意：不删除栈中的数据，这是和'出栈'的区别
⑤ 判空
⑥ 求长度
⑦ 正序遍历
⑧ 清空(只是把栈的top指针归回原位，并非把栈中的内容销毁，即原内容还是存在的)
表示形式：
㈠'逻辑结构':
S = (a1, a2, ... , an), a1为栈底元素，an为栈顶元素
进栈 出栈
↓ ↑
栈顶————> ┌───────────┐
├───────────┤(n)
├───────────┤
├───────────┤ .
├───────────┤ .
├───────────┤ .
├───────────┤(2)
├───────────┤(1)
栈底————> └───────────┘(0)
(-1)
特点：'后进先出(LIFO, last in first out)',因此又被称之为后进先出的线性表
㈡'物理存储结构'
(1) 顺序存储结构：顺序栈
利用一组地址连续的存储单元（由数组实现）依次存放自'栈底'到'栈顶'的数据元素，把数组中下标为0的一端作为栈底，为了指示栈中元素的位置，需要定义栈顶指针(top，为整型)来指示栈顶元素在顺序栈中的位置
顺序栈为"空"的条件：top == -1；
代码描述：
public class SequenceStack<T> {
private final int maxSize = 10; //栈的默认存储容量
private T[] stackArray; //模拟栈的数组
private int top; //栈顶指针
/**
* 顺序栈的初始化
* 注意：顺序栈的长度是固定的，因此，初始化时有两种方式：
* 1.不指定长度(即采用默认的长度)
* 2.指定长度
*/
//采用默认容量初始化
public SequenceStack() {
top = -1; //初始化栈顶指针，之所以从-1开始，是因为数组是从0开始的
stackArray = (T[])new Object[maxSize];
}
//采用指定的容量初始化
public SequenceStack(int n) {
//对传入的参数进行合法性检查
if (n <= 0) {
System.out.println("error!");
System.exit(1);
}
top = -1;
stackArray = (T[])new Object[n];
}
/**
* 入栈操作
*/
public void push(T obj) {
/*
* 由于，顺序栈是基于数组实现的，因此，插入数据时要考虑栈满的情况(但是链栈则不存在栈满的情况)
* 插入数据时，需要检查一下当前栈是否满了，需要扩容
*/
if (top == stackArray.length - 1) {
T[] p = (T[])new Object[top*2 + 2]; //容量扩展为原来的2倍
//将原来的数据复制到新的数组中
for (int i = 0; i <= top; i++) {
p[i] = stackArray[i];
}
stackArray = p;
}
//插入数据
top ++;
stackArray[top] = obj;
}
// 出栈操作, 时间复杂度：O(1)
public T pop() {
//需要检查栈是否为空
if (isEmpty()) {
System.out.println("栈为空，不可进行出栈操作!");
return null;
}
//删除元素: 应该先返回元素再将top--，但在程序中return不能先执行，否则top--执行不到了
top --;
return stackArray[top + 1];
}
// 获取
public T getHead() {
if (isEmpty()) {
System.out.println("栈为空，不可进行获取栈顶元素的操作!");
return null;
}
//注意：只是返回栈顶的元素，不删除它，因此不修改栈顶指针
return stackArray[top];
}
// 判空
public boolean isEmpty() {
return top == -1;
}
// 求长度
public int size() {
return top + 1;
}
// 正序遍历
public void nextOrder() {
System.out.print("[");
//注意：遍历栈，也就类似于将栈元素依次出栈的顺序打印出来
for (int i = top; i >= 0; i--) {
if (i == 0) {
System.out.print(stackArray[i]);
} else {
System.out.print(stackArray[i] + ", ");
}
}
System.out.println("]");
}
// 销毁栈
public void clear() {
top = -1; //将栈顶指针调整为-1即可。
}
}
★ 两栈共享空间
当两个栈的'入栈'和'出栈'在同一时段是"彼此相反"的，则可以考虑让它们共享同一个数组,一个栈的栈底在数组的0处，另一个栈的栈底在数组的末端，彼此相中间入栈
top1 ↓ top2 ↓
┌──┬──┬──┬──┬──┬──┬ ... ─┬──┬──┬──┬──┬──┬──┐
└──┴──┴──┴──┴──┴──┴ ... ─┴──┴──┴──┴──┴──┴──┘
(栈1的底)0 1 n-1 n (栈2的底)
public class SharStack<T> {
private int top1; //1号栈的栈顶指针
private int top2; //2号栈的栈顶指针
private T[] data; //共享的数组
//初始化
public init() {
...
}
/**
* 入栈：插入元素
*/
public void push(T obj, int stackNumber) {
//判断是否栈满
// 当两个栈指针“碰头”时，表示栈满了，此时两个指针相差1
if (top1 + 1 == top2) {
//或者扩容、或者返回null
System.out.println("栈已满，不能进行入栈操作");
return null;
}
//入栈操作
if (stackNumber == 1) {
//表示对栈1入栈
top1 ++;
data[top1] = obj;
}
if (stackNumber == 2) {
//表示对栈2入栈
top2 --;
data[top2] = obj;
}
}
//出栈：删除元素
public T pop(int stackNumber) {
//判断是哪个栈的出栈
//对栈1的操作
if (stackNumber == 1) {
//判断是否出现栈空
if (top1 == -1) {
System.out.println("栈1已空，不能进行出栈操作");
return null;
}
//正常出栈
top1 --;
return data[top1+1];
}
//对栈2的操作
if (stackNumber == 2) {
//判断是否出现栈空
if (top2 == data.length) {
System.out.println("栈2已空，不能进行出栈操作");
return null;
}
//正常出栈
top2 ++;
return data[top1-1];
}
}
}
(2) 链式存储结构：链栈
利用链表实现的，其中的每个数据元素(即Node结点)由两部分组成：数据域，指针域
由于，只在链栈的'头部'进行操作(进出栈)，因此，没必要像单链表那样附加头结点，并且
'头指针与栈顶指针'合二为一。
┌───────┬───────────┐
top ————> │ an │ next(n-1) │ :实质为链表的表头
(链表头指针) └───────┴───────────┘
.
.
.
┌───────┬───────────┐
│ a2 │ next(1) │
└───────┴───────────┘
┌───────┬───────────┐
栈底 ————> │ a1 │ null │ :实质为链表的表尾
└───────┴───────────┘
链栈为"空"的条件：top == null
注意：尽管从存储结构上看，链栈是链表的形式，但是在操作上依然是栈的定义。
代码描述：
// 1.链栈的结点描述
public class Node<T> {
T data;
Node<T> next;
//构造没有数据的结点
public Node(Node<T> n) {
next = n;
}
//构造有数据的结点
public Node(T obj, Node<T> n) {
data = obj;
next = n;
}
public T getData() {
return data;
}
public Node<T> getNext() {
return next;
}
}
// 2.链栈的描述
public class LinkStack<T> {
private Node<T> top; //栈顶指针,具备头指针的作用
private int length; //存储栈的长度(即数据元素的个数)
/**
* 初始化链栈：构造一个空的链栈
*/
public LinkStack() {
length = 0; //元素个数为0
top = null; //top指向空
}
//入栈, 时间复杂度：O(1)
public void push(T obj) {
//将top指针由null状态指向一个新的Node结点处
top = new Node<T>(obj, top); //该元素就是链表的尾部，因此，指针域为null
length ++; //元素个数加1
}
//出栈, 时间复杂度：O(1)
public T pop() {
//判空
if (isEmpty()) {
System.out.println("链栈为空，不能进行出栈操作!");
return null;
}
//出栈过程
T x = top.data;
top = top.next;
length --; //栈的元素长度减1
return x;
}
//获取栈顶元素
public T getHead() {
//进行判空
if (isEmpty()) {
System.out.println("链栈为空，不能进行获取栈顶元素!");
return null;
}
return top.data;
}
//判空
public boolean isEmpty() {
return top == null;
}
//求长度
public int size() {
return length;
}
//正向遍历
public void nextOrder() {
System.out.print("[");
Node<T> p = top; //注意，不能将原链表进行输出，不然在进行其他操作将引起错误
while (p != null) {
if (p.next == null) {
System.out.print(p.data);
} else {
System.out.print(p.data + ", ");
}
p = p.next;
}
System.out.println("]");
}
//销毁链栈
public void clear() {
length = 0;
top = null;
}
}
顺序栈和链栈的优缺点：
顺序栈和链栈在时间复杂度上是一样的，均为O(1)
在空间性能上：
• 顺序栈需要事先确定一个固定的长度，这样可能会造成空间的浪费。但其出入栈时的定位很方便。适用于元素数量变化可测的情况。
• 链栈则需要每个元素附件一个指针域，这在空间上增加了一定的内存开销，但它的长度灵活可变，不会造成空间上的浪费。适用于元素数量变化不可测的情况。
基于栈的一些应用：
进制转换
语法检查（如括号匹配问题）
回朔算法
递归算法
表达式求值
