Java数据结构和算法（四）——栈

小灰灰 2022-03-16 10:48 263阅读 0赞

**目录**

*  [1、栈的基本概念][1]
 *  [2、Java模拟简单的顺序栈实现][2_Java]
 *  [3、增强功能版栈][3]
 *  [4、利用栈实现字符串逆序][4]
 *  [5、利用栈判断分隔符是否匹配　　 ][5]
 *  [6、总结][6]

--------------------

前面我们讲解了数组，数组更多的是用来进行数据的存储，纯粹用来存储数据的数据结构，我们期望的是插入、删除和查找性能都比较好。对于无序数组，插入快，但是删除和查找都很慢，为了解决这些问题，后面我们会讲解比如二叉树、哈希表的数据结构。

而本篇博客讲解的数据结构和算法更多是用作程序员的工具，它们作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比数据库类型的结构要短得多，在程序执行期间它们才被创建，通常用它们去执行某项特殊的业务，执行完成之后，它们就被销毁。这里的它们就是——栈和队列。本篇博客我们先介绍栈。

[回到顶部][Link 1]

### 1、栈的基本概念 ###

**栈**（英语：stack）又称为**堆****栈**或**堆叠，**栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。

这里以羽毛球筒为例，羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop出栈，但是第一个拿到的羽毛球是我们最后放进去的。

[回到顶部][Link 1]

### 2、Java模拟简单的顺序栈实现 ###

![1120165-20171129201940386-674535319.png][]

**测试：**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.test;</code> &nbsp; <code>import</code>&nbsp;<code>com.ys.datastructure.MyStack;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>MyStackTest { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>static</code>&nbsp;<code>void</code>&nbsp;<code>main(String[] args) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>MyStack stack =&nbsp;</code><code>new</code>&nbsp;<code>MyStack(</code><code>3</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>2</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>3</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(stack.peek());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(!stack.isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(stack.pop());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

**结果：**

![1120165-20171129075526706-1505059456.png][]

这个栈是用数组实现的，内部定义了一个数组，一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈，push()方法是向栈中压入元素，指向栈顶的变量top加一，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据。pop()方法返回top变量指向的元素，然后将top变量减一，便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。

**产生的问题：**

**　　①、上面栈的实现初始化容量之后，后面是不能进行扩容的（虽然栈不是用来存储大量数据的），如果说后期数据量超过初始容量之后怎么办？（自动扩容）**

**　　②、我们是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据类型，那么同一个栈能不能存储不同类型的数据呢？（声明为Object）**

**　　③、栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初始化容量呢？（改为由链表实现）**

[回到顶部][Link 1]

### **3、增强功能版栈** ###

**　　对于上面出现的问题，第一个能自动扩容，第二个能存储各种不同类型的数据，解决办法如下：（第三个在讲链表的时候在介绍）**

**　　这个模拟的栈在JDK源码中，大家可以参考 Stack 类的实现。**

**　　![1120165-20171129170538081-90095577.png][]**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.datastructure;</code> &nbsp; <code>import</code>&nbsp;<code>java.util.Arrays;</code> <code>import</code>&nbsp;<code>java.util.EmptyStackException;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>ArrayStack { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//存储元素的数组,声明为Object类型能存储任意类型的数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>Object[] elementData;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//指向栈顶的指针</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>top;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//栈的总容量</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>size;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//默认构造一个容量为10的栈</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>ArrayStack(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.elementData =&nbsp;</code><code>new</code>&nbsp;<code>Object[</code><code>10</code><code>];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.top = -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.size =&nbsp;</code><code>10</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>ArrayStack(</code><code>int</code>&nbsp;<code>initialCapacity){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(initialCapacity &lt;&nbsp;</code><code>0</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>throw</code>&nbsp;<code>new</code>&nbsp;<code>IllegalArgumentException(</code><code>"栈初始容量不能小于0: "</code><code>+initialCapacity);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.elementData =&nbsp;</code><code>new</code>&nbsp;<code>Object[initialCapacity];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.top = -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.size = initialCapacity;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//压入元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>Object push(Object item){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//是否需要扩容</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>isGrow(top+</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>elementData[++top] = item;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>item;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//弹出栈顶元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>Object pop(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Object obj = peek();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>remove(top);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>obj;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//获取栈顶元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>Object peek(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(top == -</code><code>1</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>throw</code>&nbsp;<code>new</code>&nbsp;<code>EmptyStackException();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>elementData[top];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//判断栈是否为空</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isEmpty(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>(top == -</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//删除栈顶元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>remove(</code><code>int</code>&nbsp;<code>top){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//栈顶元素置为null</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>elementData[top] =&nbsp;</code><code>null</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.top--;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/**</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @param minCapacity</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isGrow(</code><code>int</code>&nbsp;<code>minCapacity){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>oldCapacity = size;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(minCapacity &gt;= oldCapacity){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//定义扩大之后栈的总容量</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>newCapacity =&nbsp;</code><code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>((oldCapacity&lt;&lt;</code><code>1</code><code>) - Integer.MAX_VALUE &gt;</code><code>0</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>newCapacity = Integer.MAX_VALUE;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>newCapacity = (oldCapacity&lt;&lt;</code><code>1</code><code>);</code><code>//左移一位，相当于*2</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>this</code><code>.size = newCapacity;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code><code>[] newArray =&nbsp;</code><code>new</code>&nbsp;<code>int</code><code>[size];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>elementData = Arrays.copyOf(elementData, size);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>true</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>false</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;<code>&nbsp; &nbsp;</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

测试：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 </td> 
 <td> <code>//测试自定义栈类 ArrayStack</code> <code>//创建容量为3的栈，然后添加4个元素，3个int，1个String.</code> <code>@Test</code> <code>public</code>&nbsp;<code>void</code>&nbsp;<code>testArrayStack(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ArrayStack stack =&nbsp;</code><code>new</code>&nbsp;<code>ArrayStack(</code><code>3</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//System.out.println(stack.peek());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>2</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>3</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(</code><code>"abc"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(stack.peek());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.pop();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.pop();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.pop();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(stack.peek());</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

结果：

![1120165-20171129170921394-914998816.png][]

[回到顶部][Link 1]

### 4、利用栈实现字符串逆序 ###

我们知道栈是后进先出，我们可以将一个字符串分隔为单个的字符，然后将字符一个一个push()进栈，在一个一个pop()出栈就是逆序显示了。如下：

将 字符串“how are you” 反转！！！

ps：这里我们是用上面自定的栈来实现的，大家可以将ArrayStack替换为JDK自带的栈类Stack试试

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 </td> 
 <td> <code>//进行字符串反转</code> <code>@Test</code> <code>public</code>&nbsp;<code>void</code>&nbsp;<code>testStringReversal(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ArrayStack stack =&nbsp;</code><code>new</code>&nbsp;<code>ArrayStack();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>String str =&nbsp;</code><code>"how are you"</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>char</code><code>[] cha = str.toCharArray();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code><code>(</code><code>char</code>&nbsp;<code>c : cha){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>stack.push(c);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(!stack.isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(stack.pop());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

结果：

![1120165-20171129170737222-708202885.png][]

[回到顶部][Link 1]

### 5、利用栈判断分隔符是否匹配　　  ###

写过xml标签或者html标签的，我们都知道<必须和最近的>进行匹配，\[ 也必须和最近的 \] 进行匹配。

比如：<abc\[123\]abc>这是符号相匹配的，如果是 <abc\[123>abc\] 那就是不匹配的。

对于 12<a\[b\{c\}\]>，我们分析在栈中的数据：遇到匹配正确的就消除

![1120165-20171129171842362-772229136.png][]

最后栈中的内容为空则匹配成功，否则匹配失败！！！

[回到顶部][Link 1]

### 6、总结 ###

根据栈后进先出的特性，我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具，具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop()，使得程序不容易出错。

对于栈的实现，我们稍微分析就知道，数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作，我们不要画蛇添足。

[1]: https://www.cnblogs.com/ysocean/p/7911910.html#_label0
[2_Java]: https://www.cnblogs.com/ysocean/p/7911910.html#_label1
[3]: https://www.cnblogs.com/ysocean/p/7911910.html#_label2
[4]: https://www.cnblogs.com/ysocean/p/7911910.html#_label3
[5]: https://www.cnblogs.com/ysocean/p/7911910.html#_label4
[6]: https://www.cnblogs.com/ysocean/p/7911910.html#_label5
[Link 1]: https://www.cnblogs.com/ysocean/p/7911910.html#_labelTop
[1120165-20171129201940386-674535319.png]: /images/20220316/315ffb1d5d234aee878f38e66c7ceb86.png
[1120165-20171129075526706-1505059456.png]: /images/20220316/0f26bf0f96f24887b96bd2b88595c242.png
[1120165-20171129170538081-90095577.png]: /images/20220316/87aabae60e0f4e93ad7f2e25e027825b.png
[1120165-20171129170921394-914998816.png]: /images/20220316/db80fa698d8b456590d4fe9747e2f9ac.png
[1120165-20171129170737222-708202885.png]: /images/20220316/ee1fb7b962874cbd810a5f46c322ecbf.png
[1120165-20171129171842362-772229136.png]: /images/20220316/7df954e1139c48d59e4e5b3f3e81d76f.png