一. 什么是栈?
1. 栈的特点
栈是一种组织数据的方式，栈内的元素有先进后出的特点 , 是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。我们自己去实现栈可以用数组或者双链表来完成 ;
Java集合中的Stack类在底层其实就是一个数组空间 , 当然LinledList底层是一个双链表，所以LinkedList也可以当做栈来使用。
栈的几个术语：
允许进行插入、删除操作的一端称为栈顶；栈的另一端称为栈底。
当栈中没有数据元素时，称为空栈。
栈的插入操作通常称为进栈或入栈（压栈）。
栈的删除操作通常称为退栈或出栈。
2. 栈相关的应用场景
2.1 关于栈的出栈序列
给你入栈序列，判断不可能的出栈序列，看下面给出的例题：
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
解析:
选项A： 1入栈，1出栈，2，3，4依次入栈，4，3，2 依次出栈 , 出栈序列为1，4，3，2 ，所以选项A的出栈序列是可能的。
选项B： 1，2依次入栈，2出栈，3入栈，3出栈，4入栈，4出栈，1出栈 , 出栈序列为2，3，4，1 ，所以选项C的出栈序列是可能的。
选项C： 1，2，3依次入栈，3出栈，选项中的第二个出栈序列为1 , 但此时3出栈后栈顶元素为2 , 不可能是1出栈 , 所以选项C的出栈序列是不可能的。
选项D： 1，2，3依次入栈，3出栈，4入栈，4出栈，2，1依次出栈，出栈序列为3，4，2，1 ，所以选项D的出栈序列是可能的。
一个栈的入栈序列为1，2，3，…，n ，其出栈序列是P1，P2,P3，…，Pn。若P2=3，则P3可能取值的个数是（ ）多少?
A.n-3 B.n-2 C.n-1 D.无法确定
解析:
P3的取值除了不能取到3其他的值均有可能，所以P3可能取值的个数为n-1。
2.2 前，中，后缀表达式
我们常用的数学加减乘除运算表达式都是中缀表达式，比如 1+2+3∗4，将中缀表达式按运算顺序打上不同的括号对，分别将运算符移到对应括号最右边，再将所有括号擦除，就能得到后缀表达式，同理将运算符移到到对应括号最左边就是前缀表达式。
示例如下 :
3. 栈的模拟实现
由于Java集合中的Stack类在底层是一个顺序表 , 所以这里用数组来模拟实现栈 .
MyStack.java
import java.util.Arrays; public class MyStack { public int[] elem; public int usedSize; public static final int DEFAULT_SIZE = 10; public MyStack() { this.elem = new int[DEFAULT_SIZE]; } //压栈 public int push(int val) { //判断空间容量 if(this.isFull()) { //扩容 this.elem = Arrays.copyOf(elem, this.usedSize*2); } this.elem[this.usedSize++] = val; return val; } public boolean isFull() { return this.elem.length == this.usedSize; } //出栈 public int pop() { if(this.empty()) { throw new MyEmptyStackException("当前栈为空!"); } return this.elem[--usedSize]; } //判断栈是否为空 public boolean empty() { return this.usedSize == 0; } //获取栈顶元素 public int peek() { if(this.empty()) { throw new MyEmptyStackException("当前栈为空"); } return this.elem[this.usedSize-1]; } }
MyEmptyStackException.java
public class MyEmptyStackException extends RuntimeException{ public MyEmptyStackException() { } public MyEmptyStackException(String message) { super(message); } }
TestStack.java
public class TestStack { public static void main(String[] args) { MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.push(3); myStack.push(4); myStack.push(5); System.out.println(myStack.peek()); System.out.print(myStack.pop()+" "); System.out.print(myStack.pop()+" "); System.out.print(myStack.pop()+" "); System.out.print(myStack.pop()+" "); System.out.println(myStack.pop()); System.out.println(myStack.empty()); } }
执行结果
【思考】
如果使用链表来实现栈 , 如何操作入栈和出栈更方便一些呢?
首先考虑单链表 , 假设单链表中有head和tail两个引用指向头节点和尾节点 , 那么如果是尾插入栈 , 时间复杂度为O(1) , 但此时出栈 , 需要找到尾节点的前一个节点 , 出栈的时间复杂度就为O(N)了 ; 再看头插入栈 , 时间复杂度为O(1) , 此时出栈也是从头出 , 时间复杂度为O(1) ;
所以如果采用单链表来实现栈应该采用头插法入栈 .
再考虑双链表表来实现栈 , 由于节点之间是双向的 , 所以入栈采用头插和尾插都可 , 最终入栈和出栈的时间复杂度都为O(1) , 所以采用双向链表来实现栈还是很方便的 .
4. 栈、虚拟机栈、栈帧有什么区别呢？
这里要注意概念的区分;
栈 : 是一种先进后出的数据结构。
虚拟机栈 : 是JVM的一块内存空间
栈帧 : 是在调用函数的过程当中，在Java虚拟机栈上开辟的一块内存。
二. 集合-Stack类
1. Stack的介绍
在集合框架中 , Stack的继承实现关系如下:
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的 ;
Vector类，是线程安全的动态数组，但是性能较差 , 现在已经不是很常用了 , 可以说已经过时了 .
2. 常用方法
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop( | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
代码示例:
public static void main(String[] args) { Stack<Integer> s = new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); // 获取栈中有效元素个数---> 4 System.out.println(s.peek()); // 获取栈顶元素---> 4 s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3 if(s.empty()){ System.out.println("栈空"); }else{ System.out.println(s.size()); }
执行结果:
3. 利用Stack将递归用循环实现
比如下面的代码 , 使用递归逆序打印单链表 , 可以使用Stack来模拟实现递归的过程(循环) .
// 递归方式打印单链表 public void printList1(ListNode head){ if(null != head){ printList1(head.next); System.out.print(head.val + " "); } } // 循环方式,利用栈打印单链表 public void printList2(ListNode head) { if (null == head) { return; } Stack<ListNode> s = new Stack<>(); // 将链表中的结点保存在栈中 ListNode cur = head; while (null != cur) { s.push(cur); cur = cur.next; } }
