1.栈的定义

栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。

栈的插入操作，叫做入栈（push）。存入栈的元素之间没有任何具体的关系，只有到来的时间的先后顺序。

入栈图

出栈图

入栈操作涉及的单个数据的进入，所以时间复杂度为 O(1)，同时入栈过程中只需要单个的临时存储空间，所以空间复杂度为 O(1)。

2.栈的存储原理

栈既可以用数组来实现，也可以用链表来实现

栈的数组实现如下:

数组实现的栈也叫顺序栈或静态栈

栈的链表实现如下：

3.栈的操作-数组实现

入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

出栈（弹栈）

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

public class ArrayStack {
private int[] array; // 存储栈元素的数组
   private int top; // 栈顶指针，指向栈顶元素在数组中的位置
   private int capacity; // 栈的最大容量

   // 构造函数，创建一个指定容量的栈
   public ArrayStack(int capacity) {
       this.capacity = capacity;
       this.array = new int[capacity];
       this.top = -1; // 栈为空，栈顶指针为-1
   }

   // 将给定的元素推送到栈的顶部
   public void push(int item) {
       if (isFull()) { // 如果栈已满，抛出异常
           throw new RuntimeException("Stack is full");
       }
       array[++top] = item; // 将元素放入栈顶，同时栈顶指针+1
   }

   // 从栈的顶部删除元素并返回该元素
   public int pop() {
       if (isEmpty()) { // 如果栈为空，抛出异常
           throw new RuntimeException("Stack is empty");
       }
       return array[top--]; // 返回栈顶元素，同时栈顶指针-1
   }

   // 返回栈顶元素但不删除它
   public int peek() {
       if (isEmpty()) { // 如果栈为空，抛出异常
           throw new RuntimeException("Stack is empty");
       }
       return array[top]; // 返回栈顶元素，但不修改栈顶指针
   }

   // 如果栈为空，则返回true，否则返回false
   public boolean isEmpty() {
       return top == -1; // 栈顶指针为-1表示栈为空
   }

   // 如果栈已满，则返回true，否则返回false
   public boolean isFull() {
       return top == capacity - 1; // 栈顶指针+1等于栈容量表示栈已满
   }

   // 返回栈中元素的数量
   public int size() {
       return top + 1; // 栈顶指针+1即为栈中元素的数量
   }

   // 清空栈中的所有元素
   public void clear() {
       top = -1; // 将栈顶指针重置为-1，表示栈为空
   }
}


在上面的示例中，我们定义了一个ArrayStack类，该类使用数组实现栈。该类具有以下主要方法：

push(item)：将给定的元素推送到栈的顶部。 pop()：从栈的顶部删除元素并返回该元素。 peek()：返回栈顶元素但不删除它。 isEmpty()：如果栈为空，则返回true，否则返回false。 isFull()：如果栈已满，则返回true，否则返回false。 size()：返回栈中元素的数量。 clear()：清空栈中的所有元素。

测试代码

public class ArrayStackTest {
   public static void main(String[] args) {
       // 创建一个容量为5的栈
       ArrayStack stack = new ArrayStack(5);

       // 测试栈的基本操作
       stack.push(1); // 入栈1
       stack.push(2); // 入栈2
       stack.push(3); // 入栈3
       System.out.println("栈顶元素为：" + stack.peek()); // 输出栈顶元素3
       stack.pop(); // 出栈3
       System.out.println("栈顶元素为：" + stack.peek()); // 输出栈顶元素2
       stack.push(4); // 入栈4
       stack.push(5); // 入栈5
       System.out.println("栈是否为空：" + stack.isEmpty()); // 输出false
       System.out.println("栈是否已满：" + stack.isFull()); // 输出true
       System.out.println("栈中元素个数为：" + stack.size()); // 输出4

       // 测试异常情况
       try {
           stack.push(6); // 入栈6，栈已满，抛出异常
       } catch (RuntimeException e) {
           System.out.println("异常信息：" + e.getMessage());
       }
       stack.pop(); // 出栈5
       stack.pop(); // 出栈4
       stack.pop(); // 出栈2
       stack.pop(); // 出栈1
       System.out.println("栈是否为空：" + stack.isEmpty()); // 输出true
       try {
           stack.pop(); // 出栈空栈，抛出异常
       } catch (RuntimeException e) {
           System.out.println("异常信息：" + e.getMessage());
       }
   }
}


4.栈的操作-链表实现

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

代码实现

import java.util.LinkedList;

public class LinkedStack<T> {

   private LinkedList<T> stackList; // 创建LinkedList类型的变量stackList，用于存储栈元素

   // 构造函数，创建一个空的LinkedList对象
   public LinkedStack() {
       stackList = new LinkedList<>();
   }

   // 将元素添加到栈的顶部，即链表的头部
   public void push(T item) {
       stackList.addFirst(item);
   }

   // 弹出并返回栈顶元素，同时将其从链表中删除
   public T pop() {
       if (stackList.isEmpty()) { // 如果栈为空，则抛出异常
           throw new RuntimeException("Stack is empty");
       }
       return stackList.removeFirst(); // 否则弹出并返回栈顶元素
   }

   // 返回栈顶元素，但不弹出它
   public T peek() {
       if (stackList.isEmpty()) { // 如果栈为空，则抛出异常
           throw new RuntimeException("Stack is empty");
       }
       return stackList.getFirst(); // 否则返回栈顶元素
   }

   // 判断栈是否为空
   public boolean isEmpty() {
       return stackList.isEmpty();
   }

   // 返回栈的元素数量
   public int size() {
       return stackList.size();
   }
}


该类有一个泛型类型T，用于存储栈元素。在构造函数中，我们创建了一个空的LinkedList对象来存储栈元素。

push方法将元素添加到栈的顶部，即链表的头部。

pop方法弹出并返回栈顶元素，同时将其从链表中删除。

peek方法返回栈顶元素，但不弹出它。

isEmpty方法返回栈是否为空。

size方法返回栈的元素数量。

请注意，如果尝试从空栈中弹出或查看元素，则会抛出RuntimeException。在实际应用中，可能需要使用不同的异常类型来更好地处理这种情况。

测试以上代码

public class LinkedStackTest {
   public static void main(String[] args) {
       // 创建一个字符串类型的栈
       LinkedStack<String> stack = new LinkedStack<>();

       // 测试isEmpty方法，输出true
       System.out.println("Stack is empty: " + stack.isEmpty());

       // 测试push方法，添加元素到栈顶
       stack.push("first");
       stack.push("second");
       stack.push("third");

       // 测试size方法，输出3
       System.out.println("Stack size: " + stack.size());

       // 测试peek方法，输出"third"
       System.out.println("Top element: " + stack.peek());

       // 测试pop方法，弹出并输出"third"
       System.out.println("Popped element: " + stack.pop());

       // 再次测试peek方法，输出"second"
       System.out.println("Top element: " + stack.peek());

       // 测试pop方法，弹出并输出"second"
       System.out.println("Popped element: " + stack.pop());

       // 测试size方法，输出1
       System.out.println("Stack size: " + stack.size());

       // 测试isEmpty方法，输出false
       System.out.println("Stack is empty: " + stack.isEmpty());
   }
}


5.栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出，以回到原来的程序中。 递归的调用：可以用来在函数调用的时候存储断点， 储存下一个指令的地址外，也将参数、区域变量等数据存入栈中。 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。 二叉树的遍历。 图形的深度优先(depth一first)搜索法。