“子弹弹夹”装弹和出弹的抽象原理实战：掌握栈的原理与实战
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
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
元素：13. 实战：有效括号匹配
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
}需要看到完整的栈操作过程的，可以在实现代码上打开格式化输出处理过程的注释代码。
处理过程：
格式化输出处理过程太长，不在这里贴上去了
true
true
true
false4. 总结
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
往期推荐
分类往期文章Java集合底层原理可视化TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？
LinkedHashMap集合--原理可视化
HashMap集合--基本操作流程的源码可视化
Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化
Java集合--从本质出发理解HashMap
Java集合--LinkedList源码可视化
Java集合源码--ArrayList的可视化操作过程设计模式秘籍
（已全部开源）掌握设计模式的两个秘籍
往期设计模式文章的：设计模式软件设计师软考中级--软件设计师毫无保留的备考分享
通过软考后却领取不到实体证书？
2023年下半年软考考试重磅消息Java学习路线
和相应资源Java全栈学习路线、学习资源和面试题一条龙原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]