栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
1. 栈的基本概念
1.1. 概念与属性
定义：栈（Stack）是一种“后进先出”（LIFO, Last-In First-Out）的线性数据结构，只允许在一端进行插入和删除操作，这一端称为栈顶（top），另一端称为栈底（bottom）。
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
栈结构如图：
1.2. 核心操作
核心操作主要有入栈push、出栈pop、获取栈顶元素peek，这三个功能为必要功能。
1.2.1. 入栈过程
元素加入及栈顶上移
1.2.2. 出栈过程
元素移除及栈顶下移
1.2.3. 获取栈顶元素
仅返回栈顶元素，不移除栈顶元素
常见方法如下：
push(x)：将元素 x 压入栈顶
pop()：弹出并返回栈顶元素
peek() / top()：仅返回栈顶元素，不移除
isEmpty()：判断栈是否为空
size()：返回栈大小
通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
2. 自定义栈
栈对元素的操作是后进先出（LIFO），栈的操作只需要在一端进行入栈（push）和出栈（pop），可以考虑使用链表或数组作为底层数据结构。由于栈没有规定容量大小，使用数组的话需要考虑动态扩容，链表则无需考虑扩容问题。
那就从最简单的单链表入手，编写自定义栈数据结构。
关键思路：每次 push 将新节点插入到链表头部；pop 则移除链表头节点并更新 head 节点为下一节点。
节点间关系图：top.next-->下一节点
2.1. 自定义栈类--YtyStack
栈的类需要有属性：栈顶（top），栈底（bottom），栈大小（size)；其次是栈的必要操作方法：入栈（push），出栈（pop），获取栈顶元素（peek）。
还有些常用操作，比如：栈大小（size）,判空（isEmpty），并且为栈加入了格式化输出。
自定义栈 YtyStack类的完整源代码
public class YtyStack<E> { // 栈顶 private Node<E> top; // 栈低 private Node<E> bottom; // 栈元素数量 private int size;
// 入栈操作 public void push(E e){ // 旧top 变为 新节点的下一个节点 Node<E> newNode = new Node<E>(e, top); // 更新栈顶 if(top==null) top = bottom = newNode; else top = newNode; size++; } // 出栈操作 public E pop(){ if(top == null) throw new RuntimeException("米缸没米了"); // 获取栈顶值 E e = top.item; // 栈顶下移 if(top==bottom)//触底 top = bottom = null; else { Node<E> next = top.next; top.item=null; top.next=null;// 断开指向，等待垃圾回收 top = next; }
size--; return e; } // 获取栈顶对象 public E peek(){ return top==null ? null : top.item; } public boolean isEmpty(){ return bottom==null;// top==null;size==0 都可以 } public int size(){ return size; }
private static class Node<E>{ E item; Node<E> next; Node(E item, Node<E> next){ this.item = item; this.next = next; } }
@Override public String toString() { StringBuilder sb = new StringBuilder("┎ ┒\n"); // 不要用 top，要用局部变量 Node<E> curr = top; // 按照出栈顺序遍历 while (true){ sb.append("┣ ").append(curr.item).append(" ┫"); curr=curr.next; if(curr!=null) sb.append("\n"); else return sb.append("\n┗---┛").toString(); }
}}
复制代码
2.2. 自定义栈测试
测试代码如下
// 测试自定义栈public static void main(String[] args) { YtyStack<Integer> ytyStack = new YtyStack<>(); ytyStack.push(1); ytyStack.push(2); ytyStack.push(3); ytyStack.push(4); System.out.println("栈的内容："); System.out.println(ytyStack); // 出栈 Integer item = ytyStack.pop(); System.out.println("\n出栈的值："+item); System.out.println(ytyStack); // 获取栈顶元素 Integer peek = ytyStack.peek(); System.out.println("\n仅获取栈顶的值："+peek); System.out.println(ytyStack); // 判空 System.out.println("栈是否为空："+ytyStack.isEmpty()); // 获取大小 System.out.println("栈大小："+ytyStack.size()); System.out.println("逐个取出元素："); while(!ytyStack.isEmpty()){ System.out.println("元素："+ytyStack.pop()); }}
复制代码
测试结果：做了格式化输出
栈的内容：┎ ┒┣ 4 ┫┣ 3 ┫┣ 2 ┫┣ 1 ┫┗---┛
出栈的值：4┎ ┒┣ 3 ┫┣ 2 ┫┣ 1 ┫┗---┛
仅获取栈顶的值：3┎ ┒┣ 3 ┫┣ 2 ┫┣ 1 ┫┗---┛栈是否为空：false栈大小：3逐个取出元素：元素：3元素：2元素：1
复制代码
3. 实战：有效括号匹配
3.1. 问题描述
这是力扣上的一道题目
有效的括号匹配规则："()"、"()[]{}"、"([])"；无效的括号：“)","(]"、"(])"
3.2. 代码实现
入栈左括号，出现右括号时出栈左括号进行匹配，只要三种括号有其一匹配上，则继续进行下去，直到全部都匹配即为有效括号字符串。具体代码实现如下：
public static boolean isValid(String str){ YtyStack<Character> ytyStack = new YtyStack<Character>(); for (Character ch : str.toCharArray()) { if (ch == '(' || ch == '[' || ch == '{') { ytyStack.push(ch); } else { // 首个字符是否为右符号 if (ytyStack.isEmpty()) return false; // 格式化输出处理过程 // System.out.println("\n"+ch); // System.out.println(ytyStack); Character top = ytyStack.pop(); // 括号匹配闭合 if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) { return false; // 三种括号都不匹配 } } } return ytyStack.isEmpty(); // 最后栈中不能有未匹配的括号}
复制代码
3.3. 测试
测试代码如下
public static void main(String[] args) { System.out.println(isValid("()")); // true System.out.println(isValid("()[]{}")); // true System.out.println(isValid("([{}]{[]})")); // true System.out.println(isValid("([)")); // false}
复制代码
需要看到完整的栈操作过程的，可以在实现代码上打开格式化输出处理过程的注释代码。
处理过程：
格式化输出处理过程太长，不在这里贴上去了
4. 总结
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
文章转载自：渊渟岳
原文链接：https://www.cnblogs.com/dennyLee2025/p/19008244
体验地址：http://www.jnpfsoft.com/?from=001YH
评论