“子弹弹夹”装弹和出弹的抽象原理实战：掌握栈的原理与实战
<blockquote><p>栈的数据结构就像是<strong>子弹弹夹</strong>一样，<strong>后装入</strong>的子弹<strong>先发出</strong>。</p>
<p>从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握<strong>栈数据结构</strong>，并通过自定义栈解决实际问题。</p>
</blockquote>
<h2 id="1-栈的基本概念">1. 栈的基本概念</h2>
<h3 id="11-概念与属性">1.1. 概念与属性</h3>
<p><strong>定义</strong>：栈（Stack）是一种“<strong>后进先出</strong>”（<code>LIFO</code>, Last-In First-Out）的线性数据结构，只允许在一端进行插入和删除操作，这一端称为<strong>栈顶</strong>（top），另一端称为<strong>栈底</strong>（bottom）。</p>
<p>栈的数据结构就像是<strong>子弹弹夹</strong>一样，<strong>后装入</strong>的子弹<strong>先发出</strong>。</p>
<p>栈结构如图：</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250728082802371-769478750.jpg" alt="image" loading="lazy"></p>
<h3 id="12-核心操作">1.2. 核心操作</h3>
<p><strong>核心操作</strong>主要有入栈<code>push</code>、出栈<code>pop</code>、获取栈顶元素<code>peek</code>，这三个功能为必要功能。</p>
<h4 id="121-入栈过程">1.2.1. 入栈过程</h4>
<p>元素加入及栈顶上移</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250728082809426-974687095.jpg" alt="image" loading="lazy"></p>
<h4 id="122-出栈过程">1.2.2. 出栈过程</h4>
<p>元素移除及栈顶下移</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250728082816784-285394844.jpg" alt="image" loading="lazy"></p>
<h4 id="123-获取栈顶元素">1.2.3. 获取栈顶元素</h4>
<p>仅返回栈顶元素，不移除栈顶元素</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250728082824146-168276640.jpg" alt="image" loading="lazy"></p>
<p><strong>常见方法如下</strong>：</p>
<p><code>push(x)</code>：将元素 x 压入栈顶</p>
<p><code>pop()</code>：弹出并返回栈顶元素</p>
<p><code>peek()</code> / <code>top()</code>：仅返回栈顶元素，不移除</p>
<p><code>isEmpty()</code>：判断栈是否为空</p>
<p><code>size()</code>：返回栈大小</p>
<blockquote>
<p>通过自定义栈来彻底掌握<strong>栈数据结构</strong>，并通过自定义栈解决实际问题。</p>
</blockquote>
<h2 id="2-自定义栈">2. 自定义栈</h2>
<p>栈对元素的操作是后进先出（LIFO），栈的操作只需要在一端进行入栈（push）和出栈（pop），可以考虑使用<strong>链表</strong>或<strong>数组</strong>作为底层数据结构。由于栈没有规定容量大小，使用数组的话需要考虑动态扩容，链表则无需考虑扩容问题。</p>
<p>那就从最简单的<strong>单链表</strong>入手，编写自定义栈数据结构。</p>
<p><strong>关键思路</strong>：每次 <code>push</code> 将新节点插入到链表头部；<code>pop</code> 则移除链表头节点并更新head节点为下一节点。</p>
<p>节点间关系图：top.next-->下一节点</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250728082832159-1082874120.jpg" alt="image" loading="lazy"></p>
<h3 id="21-自定义栈类--ytystack">2.1. 自定义栈类--YtyStack</h3>
<p>栈的类需要有属性：<strong>栈顶（top）</strong>，<strong>栈底（bottom）</strong>，<strong>栈大小（size)</strong>；其次是栈的必要操作方法：<strong>入栈（push）</strong>，<strong>出栈（pop）</strong>，<strong>获取栈顶元素（peek）</strong>。</p>
<p>还有些常用操作，比如：<strong>栈大小（size）</strong>,<strong>判空（isEmpty）</strong>，并且为栈加入了格式化输出。</p>
<p>自定义栈 <code>YtyStack</code>类的完整源代码</p>
<pre><code class="language-java">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();
}
}
}
</code></pre>
<h3 id="22-自定义栈测试">2.2. 自定义栈测试</h3>
<p>测试代码如下</p>
<pre><code class="language-java">// 测试自定义栈
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());
}
}
</code></pre>
<p><strong>测试结果</strong>：做了格式化输出</p>
<pre><code>栈的内容：
┎ ┒
┣ 4 ┫
┣ 3 ┫
┣ 2 ┫
┣ 1 ┫
┗---┛
出栈的值：4
┎ ┒
┣ 3 ┫
┣ 2 ┫
┣ 1 ┫
┗---┛
仅获取栈顶的值：3
┎ ┒
┣ 3 ┫
┣ 2 ┫
┣ 1 ┫
┗---┛
栈是否为空：false
栈大小：3
逐个取出元素：
元素：3
元素：2
元素：1
</code></pre>
<h2 id="3-实战有效括号匹配">3. 实战：有效括号匹配</h2>
<h3 id="31-问题描述">3.1. 问题描述</h3>
<p>这是力扣上的一道题目</p>
<p>有效的括号匹配规则："()"、"()[]{}"、"([])"；无效的括号：“)","(]"、"(])"</p>
<h3 id="32-代码实现">3.2. 代码实现</h3>
<p>入栈左括号，出现右括号时出栈左括号进行匹配，只要三种括号有其一匹配上，则继续进行下去，直到全部都匹配即为有效括号字符串。具体代码实现如下：</p>
<pre><code class="language-java">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(); // 最后栈中不能有未匹配的括号
}
</code></pre>
<h3 id="33-测试">3.3. 测试</h3>
<p>测试代码如下</p>
<pre><code class="language-java">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
}
</code></pre>
<p>需要看到完整的栈操作过程的，可以在实现代码上打开格式化输出处理过程的注释代码。</p>
<p><strong>处理过程</strong>：</p>
<p>格式化输出处理过程太长，不在这里贴上去了</p>
<pre><code>true
true
true
false
</code></pre>
<h2 id="4-总结">4. 总结</h2>
<p>栈的数据结构就像是<strong>子弹弹夹</strong>一样，<strong>后装入</strong>的子弹<strong>先发出</strong>。</p>
<p>从概念到实战逐步掌握数据结构：通过自定义栈来彻底掌握<strong>栈数据结构</strong>，并通过自定义栈解决实际问题。</p>
<h2 id="往期推荐">往期推荐</h2>
<table>
<thead>
<tr>
<th>分类</th>
<th>往期文章</th>
</tr>
</thead>
<tbody>
<tr>
<td>Java集合底层原理可视化</td>
<td>TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？<br>LinkedHashMap集合--原理可视化<br>HashMap集合--基本操作流程的源码可视化<br>Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化<br>Java集合--从本质出发理解HashMap<br>Java集合--LinkedList源码可视化<br>Java集合源码--ArrayList的可视化操作过程</td>
</tr>
<tr>
<td>设计模式秘籍<br>（已全部开源）</td>
<td>掌握设计模式的两个秘籍<br>往期设计模式文章的：设计模式</td>
</tr>
<tr>
<td>软件设计师</td>
<td>软考中级--软件设计师毫无保留的备考分享<br>通过软考后却领取不到实体证书？<br>2023年下半年软考考试重磅消息</td>
</tr>
<tr>
<td>Java学习路线<br>和相应资源</td>
<td>Java全栈学习路线、学习资源和面试题一条龙</td>
</tr>
</tbody>
</table>
<p>原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓</p><br><br>
来源：https://www.cnblogs.com/dennyLee2025/p/19008244
頁:
[1]