谈谈 “栈” 到底是个啥玩意，真的有那么难吗？
栈的总结
栈是一种运算受限的线性表，只允许在固定的一端进行插入（入栈）和删除（出栈）操作，遵循“后进先出”的原则（FILO）。它由一个存储容器（如数组或链表）和一个表示栈顶的指针组成。
主要特点：
入栈：将新元素添加到容器末尾（尾部），并将指针向后移动一位。
出栈：从容器末尾移除元素，并向前移动指针。
应用：广泛应用于函数调用记录、括号匹配、递归调用等场景。
常见实现方式：
数组形式实现：
- 使用固定大小数组存储元素。
- 优点：清空时间复杂度为O(1)。
- 缺点：内存浪费较大。
- 方法包括push（入栈）、pop（出栈）、display（打印）等。
链表形式实现：- 每个节点包含数据和指向下一个节点的引用。
- 优点：按需申请内存空间。
- 缺点：效率较低。
- 方法包括push、pop及迭代器接口等。
总结而言，选择哪种实现取决于具体需求与应用场景。
1、到底什么是栈？
官方理解：
stack（也称为堆栈）是一种受限的数据结构。其本质是一个受到运算限制的线性表。仅允许在数据表的一端进行添加与删除操作。这种只能在指定一端执行数据增删操作的方式使其具有独特的特性。
将新元素加入到当前顶端位置之上即完成进栈操作；而取出并丢弃顶端位置上的数据则被视为出栈操作。
相对于这个结构底端的位置则被称为底端。
通俗来说：
栈本质上是一种受限的线性数据结构，在其一端允许进行插入与删除操作。这种只能在固定位置执行的数据操作模式决定了其核心特征。
栈中的元素按照“先进后出”的原则组织，在实际应用中展现出独特的优势。
从存储实现的角度来看，栈可分为两种主要类型：一种基于顺序存储设备的顺序栈以及另一种基于链式存储结构的链栈。
它的数据结构和操作流程如下图所示：
2、栈的数组形式实现
（1）定义数组结构
首先初始化一个用于存储栈元素的空数组；接着确定一个表示栈顶元素位置的最大索引变量top；最后计算并确定一个用于计算栈容量的最大空间变量maxSize。
public class ArrayStact<E> {
private Object[] value = null; // 栈存储容器
private int top = -1; // 栈顶（的指针）
private int maxSize = 0; // 栈容量
// 构造函数（初始化默认容量）
public ArrayStact() {
this.maxSize = 10;
}
// 有参构造函数
public ArrayStact(int initSize) throws Exception {
if (initSize <= 0) {
throw new Exception("栈容量必须大于 0");
} else {
value = new Object[initSize];
maxSize = initSize;
top = -1;
}
}
}
AI助手（2）入栈
先来通过下面动图看看入栈的数组形式实现是怎么样的：
每当发生数据插入操作时,我们可以通过向数组中追加一个元素,并使栈顶位置（top）的下标递增1来实现栈结构的有效维护
// 入栈
public boolean push(E e) throws Exception {
if (maxSize - 1 == top) {
throw new Exception("入栈失败，栈容量已满");
} else {
value[++top] = e;
return true;
}
}
AI助手（3）出栈
再来通过下面动图看看出栈的数组形式实现是怎么样的：
具体来说，出栈操作仅需从数组末尾移除该栈顶元素，并将其索引指向相邻的前一个元素位置。
// 出栈
public E pop() throws Exception {
if (top <= -1) {
throw new Exception("移除失败，栈中已无数据");
} else {
return (E) value[top--];
}
}
AI助手（4）栈中的元素查询
我们还可以查询栈顶的元素
// 元素查询
public E peep() throws Exception {
if (top <= -1) {
throw new Exception("移除失败，栈中已无数据");
} else {
return (E) value[top];
}
}
AI助手（5）打印栈中的元素
// 打印栈元素
public void display() throws Exception {
if (getSize() == 0) {
throw new Exception("空栈!");
}
for (int i=getSize()-1;i>=0;i--) {
System.out.print(value[i].toString() + " ");
}
System.out.println("");
}
AI助手（6）测试
// 代码测试
public static void main(String[] args) throws Exception {
ArrayStact stack = new ArrayStact(10);
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.display();
System.out.println("栈顶元素为："+stack.peep());
System.out.println("栈元素个数为："+stack.getSize());
stack.pop();
stack.display();
System.out.println("出栈后栈顶元素为："+stack.peep());
System.out.println("出栈后栈元素个数为："+stack.getSize());
stack.push("e");
stack.display();
System.out.println("入栈栈顶元素为："+stack.peep());
System.out.println("入栈栈元素个数为："+stack.getSize());
}
AI助手
3、栈的链表形式实现
先来通过下面动图看看链表形式实现是怎么样的：
（1）定义链表结构
API设计如下图：
首先我们先来定义一个链表节点：
public class Stack<T> implements Iterable<T>{
//记录首结点
private Node top;
//栈中元素的个数
private int N;
private class Node{
public T item;
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
public Stack() {
this.top = new Node(null,null);
this.N=0;
}
//判断当前栈中元素个数是否为0
public boolean isEmpty(){
return N==0;
}
//获取栈中元素的个数
public int size(){
return N;
}
//把t元素压入栈
public void push(T t){
}
//弹出栈顶元素
public T pop(){
return null;
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
private class SIterator implements Iterator{
private Node n;
public SIterator(){
this.n=top;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}
AI助手（2）入栈
当入栈时，我们将数据存放在链表的头部位置；出栈操作则从链表头部开始；具体而言，在出栈后需将当前头节点作为新的栈顶指针所指向的对象；为了直观展示这一过程的变化轨迹，则可以通过动态图示的方式能够清晰展示这一过程。
实现代码如下：
//把t元素压入栈
public void push(T t){
//找到首结点指向的第一个结点
Node oldFirst = top.next;
//创建新结点
Node newNode = new Node(t, null);
//让首结点指向新结点
top.next = newNode;
//让新结点指向原来的第一个结点
newNode.next=oldFirst;
//元素个数+1；
N++;
}
AI助手（3）出栈
动图呈现如下：
实现代码如下：
//弹出栈顶元素
public T pop(){
//找到首结点指向的第一个结点
Node oldFirst = top.next;
if (oldFirst==null){
return null;
}
//让首结点指向原来第一个结点的下一个结点
top.next=oldFirst.next;
//元素个数-1；
N--;
return oldFirst.item;
}
AI助手（4）测试
public class StackTest {
public static void main(String[] args) {
//创建栈对象
Stack<String> stack = new Stack<>();
//测试压栈
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
for (String item : stack) {
System.out.println(item);
}
System.out.println("------------------------------");
//测试弹栈
String result = stack.pop();
System.out.println("弹出的元素是："+result);
System.out.println("剩余的元素个数："+stack.size());
}
}
AI助手
4、栈的数组和链表形式实现区别
数组：
- 优点：清空栈时间复杂度为 O(1)
- 缺点：内存空间浪费比较大
链表：
优点：根据需求动态分配存储区域
缺点：每次都生成节点并预留所需内存
该段为HUA… 的一篇博客文章（原文）。该文详细讨论了……（具体内容），并探讨了……（相关主题）。
需要改写的内容