登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›“子弹弹夹”装弹和出弹的抽象原理实战：掌握栈的原理与 ...

“子弹弹夹”装弹和出弹的抽象原理实战：掌握栈的原理与实战

饨篦 昨天 07:26
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
1. 栈的基本概念

1.1. 概念与属性

定义：栈（Stack）是一种“后进先出”（LIFO, Last-In First-Out）的线性数据结构，只允许在一端进行插入和删除操作，这一端称为栈顶（top），另一端称为栈底（bottom）。
栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
栈结构如图：
1.png

1.2. 核心操作

核心操作主要有入栈push、出栈pop、获取栈顶元素peek，这三个功能为必要功能。
1.2.1. 入栈过程

元素加入及栈顶上移
2.png

1.2.2. 出栈过程

元素移除及栈顶下移
3.jpeg

1.2.3. 获取栈顶元素

仅返回栈顶元素，不移除栈顶元素
4.jpeg

常见方法如下：
push(x)：将元素 x 压入栈顶
pop()：弹出并返回栈顶元素
peek() / top()：仅返回栈顶元素，不移除
isEmpty()：判断栈是否为空
size()：返回栈大小
通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
2. 自定义栈

栈对元素的操作是后进先出（LIFO），栈的操作只需要在一端进行入栈（push）和出栈（pop），可以考虑使用链表或数组作为底层数据结构。由于栈没有规定容量大小，使用数组的话需要考虑动态扩容，链表则无需考虑扩容问题。
那就从最简单的单链表入手，编写自定义栈数据结构。
关键思路：每次 push 将新节点插入到链表头部；pop 则移除链表头节点并更新head节点为下一节点。
节点间关系图：top.next-->下一节点
5.jpeg

2.1. 自定义栈类--YtyStack

栈的类需要有属性：栈顶（top），栈底（bottom），栈大小（size)；其次是栈的必要操作方法：入栈（push），出栈（pop），获取栈顶元素（peek）。
还有些常用操作，比如：栈大小（size）,判空（isEmpty），并且为栈加入了格式化输出。
自定义栈 YtyStack类的完整源代码
  1. public class YtyStack<E> {
  2.     // 栈顶
  3.     private Node<E> top;
  4.     // 栈低
  5.     private Node<E> bottom;
  6.     // 栈元素数量
  7.     private int size;
  9.     // 入栈操作
  10.     public void push(E e){
  11.         // 旧top 变为 新节点的下一个节点
  12.         Node<E> newNode = new Node<E>(e, top);
  13.         // 更新栈顶
  14.         if(top==null)
  15.             top = bottom = newNode;
  16.         else
  17.             top = newNode;
  18.         size++;
  19.     }
  20.     // 出栈操作
  21.     public E pop(){
  22.         if(top == null)
  23.             throw new RuntimeException("米缸没米了");
  24.         // 获取栈顶值
  25.         E e = top.item;
  26.         // 栈顶下移
  27.         if(top==bottom)//触底
  28.             top = bottom = null;
  29.         else {
  30.             Node<E> next = top.next;
  31.             top.item=null;
  32.             top.next=null;// 断开指向，等待垃圾回收
  33.             top = next;
  34.         }
  36.         size--;
  37.         return e;
  38.     }
  39.     // 获取栈顶对象
  40.     public E peek(){
  41.         return top==null ? null : top.item;
  42.     }
  43.     public boolean isEmpty(){
  44.         return bottom==null;// top==null;size==0 都可以
  45.     }
  46.     public int size(){
  47.         return size;
  48.     }
  51.     private static class Node<E>{
  52.         E item;
  53.         Node<E> next;
  54.         Node(E item, Node<E> next){
  55.             this.item = item;
  56.             this.next = next;
  57.         }
  58.     }
  60.     @Override
  61.     public String toString() {
  62.         StringBuilder sb = new StringBuilder("┎   ┒\n");
  63.         // 不要用 top，要用局部变量
  64.         Node<E> curr = top;
  65.         // 按照出栈顺序遍历
  66.         while (true){
  67.             sb.append("┣ ").append(curr.item).append(" ┫");
  68.             curr=curr.next;
  69.             if(curr!=null)
  70.                 sb.append("\n");
  71.             else
  72.                 return sb.append("\n┗---┛").toString();
  73.         }
  75.     }
  76. }
复制代码
2.2. 自定义栈测试

测试代码如下
  1. // 测试自定义栈
  2. public static void main(String[] args) {
  3.         YtyStack<Integer> ytyStack = new YtyStack<>();
  4.         ytyStack.push(1);
  5.         ytyStack.push(2);
  6.         ytyStack.push(3);
  7.         ytyStack.push(4);
  8.         System.out.println("栈的内容：");
  9.         System.out.println(ytyStack);
  10.         // 出栈
  11.         Integer item = ytyStack.pop();
  12.         System.out.println("\n出栈的值："+item);
  13.         System.out.println(ytyStack);
  14.         // 获取栈顶元素
  15.         Integer peek = ytyStack.peek();
  16.         System.out.println("\n仅获取栈顶的值："+peek);
  17.         System.out.println(ytyStack);
  18.         // 判空
  19.         System.out.println("栈是否为空："+ytyStack.isEmpty());
  20.         // 获取大小
  21.         System.out.println("栈大小："+ytyStack.size());
  22.         System.out.println("逐个取出元素：");
  23.         while(!ytyStack.isEmpty()){
  24.                 System.out.println("元素："+ytyStack.pop());
  25.         }
  26. }
复制代码
测试结果：做了格式化输出
  1. 栈的内容：
  2. ┎   ┒
  3. ┣ 4 ┫
  4. ┣ 3 ┫
  5. ┣ 2 ┫
  6. ┣ 1 ┫
  7. ┗---┛
  9. 出栈的值：4
  10. ┎   ┒
  11. ┣ 3 ┫
  12. ┣ 2 ┫
  13. ┣ 1 ┫
  14. ┗---┛
  16. 仅获取栈顶的值：3
  17. ┎   ┒
  18. ┣ 3 ┫
  19. ┣ 2 ┫
  20. ┣ 1 ┫
  21. ┗---┛
  22. 栈是否为空：false
  23. 栈大小：3
  24. 逐个取出元素：
  25. 元素：3
  26. 元素：2
  27. 元素：1
复制代码
3. 实战：有效括号匹配

3.1. 问题描述

这是力扣上的一道题目
有效的括号匹配规则："()"、"()[]{}"、"([])"；无效的括号：“)","(]"、"(])"
3.2. 代码实现

入栈左括号，出现右括号时出栈左括号进行匹配，只要三种括号有其一匹配上，则继续进行下去，直到全部都匹配即为有效括号字符串。具体代码实现如下：
  1. public static boolean isValid(String str){
  2.         YtyStack<Character> ytyStack = new YtyStack<Character>();
  3.         for (Character ch : str.toCharArray()) {
  4.                 if (ch == '(' || ch == '[' || ch == '{') {
  5.                         ytyStack.push(ch);
  6.                 } else {
  7.                         // 首个字符是否为右符号
  8.                         if (ytyStack.isEmpty())
  9.                                 return false;
  10.                         // 格式化输出处理过程
  11.                         // System.out.println("\n"+ch);
  12.                         // System.out.println(ytyStack);
  13.                         Character top = ytyStack.pop();
  14.                         // 括号匹配闭合
  15.                         if ((ch == ')' && top != '(') ||
  16.                                 (ch == ']' && top != '[') ||
  17.                                 (ch == '}' && top != '{')) {
  18.                                 return false; // 三种括号都不匹配
  19.                         }
  20.                 }
  21.         }
  22.         return ytyStack.isEmpty(); // 最后栈中不能有未匹配的括号
  23. }
复制代码
3.3. 测试

测试代码如下
  1. public static void main(String[] args) {
  2.         System.out.println(isValid("()")); // true
  3.         System.out.println(isValid("()[]{}")); // true
  4.         System.out.println(isValid("([{}]{[]})")); // true
  5.         System.out.println(isValid("([)")); // false
  6. }
复制代码
需要看到完整的栈操作过程的，可以在实现代码上打开格式化输出处理过程的注释代码。
处理过程：
格式化输出处理过程太长，不在这里贴上去了
  1. true
  2. true
  3. true
  4. false
复制代码
4. 总结

栈的数据结构就像是子弹弹夹一样，后装入的子弹先发出。
从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握栈数据结构，并通过自定义栈解决实际问题。
往期推荐

分类往期文章Java集合底层原理可视化TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？
LinkedHashMap集合--原理可视化
HashMap集合--基本操作流程的源码可视化
Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化
Java集合--从本质出发理解HashMap
Java集合--LinkedList源码可视化
Java集合源码--ArrayList的可视化操作过程设计模式秘籍
（已全部开源）掌握设计模式的两个秘籍
往期设计模式文章的：设计模式软件设计师软考中级--软件设计师毫无保留的备考分享
通过软考后却领取不到实体证书？
2023年下半年软考考试重磅消息Java学习路线
和相应资源Java全栈学习路线、学习资源和面试题一条龙原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
饨篦
昨天 07:26

0

粉丝关注

17

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫