【数据结构】栈

一、栈的概念

1.栈的定义

栈(Stack):只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
他是一种”先进后出“的数据结构

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表

2.栈的常见基本操作

• InitStack(&S)：初始化一个空栈S。
• StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
• Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
• Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
• GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
• DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

二、栈的顺序存储结构

1.栈的顺序存储结构

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。

若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

2.共享栈(两栈共享空间)(双端栈)

(1)共享栈概念

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

双端栈是线性表的一种,更是栈的一个特殊分类，可用借用动态数组+栈的组合实现。

(2)特点

双端栈的特点是可以从两个方向进行操作，即从左侧插入和删除元素，也可以从右侧插入和删除元素。这使得双端栈在某些场景下可以提供更灵活的操作和更高的效率。

(3)实例

使用Java的Deque实现双端栈的演示实例：

public class DequeStack {private Deque<Integer> deque;public DequeStack() {deque = new ArrayDeque<>();}public void push(int item) {deque.push(item);}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return deque.pop();}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return deque.peek();}public boolean isEmpty() {return deque.isEmpty();}public int size() {return deque.size();}
}

在这个示例中，我们使用了Java的Deque，具体是ArrayDeque实现类。ArrayDeque是基于可调整大小的数组实现的双端队列，可以在队列的两端进行插入和删除操作。我们将其作为双端栈的底层数据结构来实现。

通过双端栈，我们可以在栈顶和栈底进行元素的插入和删除操作。例如：

DequeStack stack = new DequeStack();
stack.push(1);
stack.push(2);System.out.println(stack.peek()); // 输出：2stack.push(3);
stack.push(4);System.out.println(stack.pop()); // 输出：4stack.push(5);System.out.println(stack.pop()); // 输出：5
System.out.println(stack.pop()); // 输出：3
System.out.println(stack.pop()); // 输出：2
System.out.println(stack.isEmpty()); // 输出：true

三、栈的链式存储结构

1.链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead指向栈顶元素
如下图所示。

对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

2.性能比较

链栈的进栈push和出栈pop操作都很简单，时间复杂度均为O(1)。
对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。
空间：1.顺序栈需要确定一个连续的长度，可能会存在内存浪费现象
优点：定位方便
2.链栈要求每个元素都要有指针域，会增加内存开销
对栈的长度无限制
如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

四、Stack的常用方法

方法名称	类型	说明
public Stack()	构造方法	创建Stack对象
public E Stack(E item)	普通方法	入栈
public synchronized E pop()	普通方法	出栈
public synchronized E peek()	普通方法	获取栈顶元素
public boolean empty()	普通方法	判断栈是否为空
public synchronized int search(Object o)	普通方法	基于栈顶位置(索引为1，索引自栈顶向栈底自增) 查找对象o，如果找到了返回索引值，否则返回-1

代码

public class MyStack {public int[] elem; //数组 -> 栈空间public int usedSize;//有效数据public MyStack(){this.elem = new int[5];this.usedSize = 0;}//入栈public void push(int val){//如果栈满了就进行扩容if(isFull()){this.elem = Arrays.copyOf(elem,2*this.elem.length);}this.elem[this.usedSize] = val;usedSize++;}//判断栈是否满public boolean isFull(){return usedSize==this.elem.length;}//出栈public int pop(){if(isEmpty()){throw new NullPointerException("栈为空！");}int oldVal = this.elem[usedSize-1];this.usedSize--;return oldVal;}//判断栈是否为空public boolean isEmpty(){return this.usedSize==0;}//读取栈顶元素public int peek(){if(isEmpty()){throw new NullPointerException("栈为空！");}return this.elem[usedSize-1];}
}

测试类

public class TestDemo1 {public static void main(String[] args) {MyStack myStack = new MyStack();myStack.push(1);//入栈myStack.push(2);myStack.push(3);myStack.push(4);System.out.println(myStack.peek());//获取栈顶元素System.out.println(myStack.pop());//出栈System.out.println(myStack.pop());System.out.println(myStack.pop());System.out.println(myStack.pop());System.out.println(myStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false}
}

运行结果：

4
4
3
2
1
true

五、栈的使用

在集合框架中，Stack（栈）是一个普通的类，实现了List接口，具体框架图如下：

注意：

1. Stack实现了RandomAccess接口，表明Stack支持随机访问
2. Stack实现了Cloneable接口，表明Stack是可以clone的
3. Stack实现了Serializable接口，表明Stack是支持序列化的
4. Vector（向量）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
5. Vector 与 ArrayList 基本是一致的，不同的是Vector是线程安全的，会在可能出现线程安全的方法前面使用 synchronized 关键字。

六、栈的几种实现方式

1.基于简单数组的实现方式

使用简单数组作为底层数据结构来实现栈，通过将栈顶元素的索引存储在变量中，实现压栈和弹栈操作，每次压栈时将元素添加到数组末尾，每次弹栈时将栈顶元素从数组中删除。由于数组的长度是固定的，需要提前定义栈的最大容量。

public class ArrayStack {private int[] stack;private int top;public ArrayStack(int capacity) {stack = new int[capacity];top = -1;}public void push(int item) {if (top == stack.length - 1) {throw new IllegalStateException("Stack is full");}stack[++top] = item;}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack[top--];}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack[top];}public boolean isEmpty() {return top == -1;}
}

2.基于动态数组的实现方式

使用动态数组（如ArrayList）作为底层数据结构来实现栈，通过在动态数组的尾部进行插入和删除操作来实现栈的功能。当栈容量不足时，动态数组可以自动进行扩容，当栈元素减少时，动态数组可以自动进行缩容。这种实现方式提供了动态调整容量的特性。

public class DynamicArrayStack {private ArrayList<Integer> stack;public DynamicArrayStack() {stack = new ArrayList<>();}public void push(int item) {stack.add(item);}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack.remove(stack.size() - 1);}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack.get(stack.size() - 1);}public boolean isEmpty() {return stack.isEmpty();}
}

3.基于链表的实现方式

使用链表作为底层数据结构来实现栈，链表的头部或尾部作为栈顶，每次插入和删除操作都在链表的头部进行，通过修改引用来实现栈的操作。链表实现的栈可以动态增加和缩小容量，不需要提前定义栈的最大容量，但相对于数组实现，需要更多的空间开销。

public class LinkedListStack {private Node top;private class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}}public LinkedListStack() {top = null;}public void push(int item) {Node newNode = new Node(item);if (isEmpty()) {top = newNode;} else {newNode.next = top;top = newNode;}}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}int item = top.data;top = top.next;return item;}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return top.data;}public boolean isEmpty() {return top == null;}
}

基于数组的实现与基于链表的实现的区别

(1)基于数组的实现

• 各个操作都是常数时间开销
• 每隔一段时间进行的倍增操作的时间开销较大

(2) 基于链表实现的栈：

• 栈规模的增加和减小都很容易
• 各个操作都是常数时间开销
• 每个操作都需要使用额外的空间和时间开销来处理指针

4.基于队列的实现方式

使用队列作为底层数据结构来实现栈，可以使用两个队列来模拟栈的操作。当压栈时，将元素添加到非空队列中；当弹栈时，将非空队列中的元素依次弹出并放入另一个空队列中，直到剩下最后一个元素，即栈顶元素，然后弹出。这种实现方式可以保持栈顶元素总是在队列的尾部，模拟了栈的后进先出（LIFO）特性。

public class QueueBasedStack {private Queue<Integer> queue1;private Queue<Integer> queue2;private int top;public QueueBasedStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int item) {queue1.add(item);top = item;}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}while (queue1.size() > 1) {top = queue1.remove();queue2.add(top);}int item = queue1.remove();Queue<Integer> tempQueue = queue1;queue1 = queue2;queue2 = tempQueue;return item;}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return top;}public boolean isEmpty() {return queue1.isEmpty();}
}