第7章栈与stack类2025/6/171栈的特点栈的创建与独特的函数栈与回文串栈与递归栈与括号匹配栈与深度搜素栈与后缀表达式

7.1栈的特点2025/6/172栈擅长在线性表的尾部，即栈顶操作，栈是受限的线性表。压栈时，最先进栈的节点在栈底，最后进栈的节点在栈顶（俗话说，垒墙的砖，后来者居上），弹栈时，从栈顶开始弹出节点，最后一个弹出的节点是栈底节点。栈是一种后进先出的数据结构，简称LIFO（LastInFirstout）

7.2栈的创建与独特函数2025/6/173std::stack是C++标准模板库（StandardTemplateLibrary,STL）中的模板类，用于实现栈这种数据结构（也称栈是STL的容器之一），即提供后进先出的数据结构。需要注意，当std使用作用域运算符（也称解析运算符））“：：”访问stack时不要误写为str::Stack，即不可以将stack的首写字母写成大写的S。称std::stack类的实例（对象）为栈，其中的节点的逻辑结构是线性结构。

2025/6/1747.2栈的创建与独特函数1创建栈使用std::stack类创建栈时，必须要指定模板类中的参数类型的具体类型，类型是可以是C++允许的数据类型，比如int、float、char和类等，即指定栈中节点里的数据的类型。例如，指定栈stack的节点中的数据的类型是std::string类型：std::stackstr::stringstack;如果不指定stack栈的存储方式，那么stack的节点的存储结构是顺序存储，即使用数组管理节点，后面叙述中说栈的节点中的数据或栈的数据都是正确的。创建栈时，例如stackWithList,可以指定stackWithList的存储方式是std:list,那么stackWithList将使用链式存储，例如：std::stackint,std::listintstackWithList;注意：如果只在尾端操作链表，就可以把链表当栈来使用，那么这样的栈是链式存储。

2025/6/1757.2栈的创建与独特函数2独特函数?std::stack没有提供迭代器，即不提供begin()和end()函数。

2025/6/1767.2栈的创建与独特函数ch7_1.cpp使用了栈的独特函数.ch7_1.cpp例子1使用栈的独特函数

7.3栈与回文串2025/6/177回文串是指和其反转（倒置）相同的字符串，例如：racecar,123321，level”，toot，civic，pop，eye，rotator，pip都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。

2025/6/1787.3栈与回文串ch7_2.cpp例子2如果一个字符串的长度是偶数，只要判断字符串的前一半和后一半是否相同即可，如果一个字符串的长度是奇数，只要忽略字符串中间的字符，然后判断字符串的前一半和后一半是否相同即可。那么利用栈的特点，首先将字符串的字符逐个进栈，然后弹出一半字符压入另一个栈，然后比较两个栈中的字符是否相同，就可以判断一个字符串是否是回文串。利用栈判断一个字符串是否为回文串

7.4栈与递归2025/6/179递归过程就是方法地址被压栈、弹栈的一个过程，所以，也可以利用栈这种数据结构，把某些递归算法改写为迭代算法。

2025/6/17107.4栈与递归ch7_3.cpp例子3ch7_3.cpp中利用栈输出Fibonacci序列的前16项（有关Fibonacci序列的知识点和递归算法参见第3章中的例3-2）。利用栈输出Fibonacci序列的前几项

7.5栈与括号匹配2025/6/1711栈的特点使得它很适合被用来检查一个字符串中的括号是否是匹配的，即左、右括号是否是成对的。算法如下：

2025/6/17127.5栈与括号匹配match.cpp例子4检查括号是否匹配算法描述如下：（1）遍历字符串的每个字符，遇到左括号时压栈。（2）遇到右括号，如果此时栈为空，字符串中就出现了括号不匹配现象。如果栈不空，弹栈。如果字符串中的括号是匹配的，按着栈的特点，当遍历字符串遇到右括号时，此刻栈顶节点中的括号一定是和它相匹配的左括号，如果不是这样，字符串中的括号就出现了不匹配现象。ch7_4.cpp

7.6栈与深度搜索2025/6/1713深度优先搜索算法，在进行遍历或者说搜索的时候，选择一个没有被搜过的节点，按照深度优先：一直往该节点的后续路径节点进行访问，直到该路径的最后一个节点，然后再从未被访问的邻节点进行深度优先搜索，重复以上过程，直至所有点都被访问或搜索到指定的某些特殊节点，算法结束。深度优先搜索（DepthFirstSear