数据结构&与算法&栈

谁借莪１个温暖的怀抱￠ 2024-04-03 10:37 88阅读 0赞

## （栈）&队列 ##

## 一：什么是栈？ ##

stack是一种特殊的线性数据集合，只准许在栈顶进行操作元素，在栈顶加入（push()）在栈顶删除（pop()）,采取是的**先进后出**的原则。

![8c16972ce62cd1fdd34d4881ee4803cf.png][]

## 二：栈按存储结构又分为哪两种？ ##

1.  栈底层结构为一维数组就是顺序栈，在JAVA中使用java.until.Stack类来实现的
2.  栈底层结构为链表时就是链式栈， 是用列表Linkedlist来实现的

![b153fcfd371b0e1841a783f678345d28.png][]

## 三：那么顺序栈与链栈有什么区别？ ##

*  对于顺序栈（Stack）栈来说，它是vector的子类。底层是通过一个数组来实现的，它是线程安全的，顺序栈是静态分配空间的，最大容量空间收到的限制，顺序栈遍历速度快，写操作慢与链栈。
 *  对于链栈（Stack）来说，它底层是是通过一条链表（linkedlist）来存储的数据的，是线程不安全的，链栈式动态分配空间的 ，不需要考虑空间的限制，链栈的写的速度快，读的式慢与顺序栈 的。

## 四：栈常见的应用场景有哪些？ ##

1.  **浏览器的回退和前进：**实现的网页的请进后退，实际上使用到了两个栈来实现的，当你看了1 2 3 4四个界面时，将这四个页面押入到栈1中，突然想看页面2个所以点击回退两次，将把栈顶的3 4页面给押入到栈2中，这时候就能看到页面2了，当你突然有想看4在点击两次次前进按钮，将栈2的页面在押入到栈1中这样就可以看到了。

![afb63166e9f755f3b9b04022bd5a2ee3.png][]

**2.虚拟机栈：**每一个线程又会有自己一个独立的存储空间，这个空间就是虚拟机栈，被称为是虚拟机栈，这里的虚拟机栈是由一个个栈帧组成的，栈里帧包括局部变量表，操作数栈，动态连接，方法出口信息，当你调用对应的方法时候，这个方法的栈帧就会押入到栈中，当这个方法调用结束时，也就伴随这个栈被抛出了栈，

![43c9efc3f989890cd615a80688abb028.png][]

## 五：栈常见的手撕代码有哪些？ ##

**1.检查符号是否成队出现**

实现思路：首下将所有的右括号作为键存在map集合中，左括号作为值。遍历给的括号字符串将遍历到左括号加到栈中，如果遍历到右括号的话将栈中的左括号从栈里面拿出来与集合中的对应的左括号进行比较，一样返回true否则返回false.

![de31c22afa028374d887ac146639d551.png][]

**2.实现字符串的反转**

实现思路：遍历字符串然后将字符串一次押入到栈中，后从栈中一次取出。

![f70d087ca045bf129ec945d03694ab45.png][]

[8c16972ce62cd1fdd34d4881ee4803cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d6603fef337d4d5d95425d836e98d0d6.png
[b153fcfd371b0e1841a783f678345d28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f4cf9480c32e4aa5b9adcdf0421a7e72.png
[afb63166e9f755f3b9b04022bd5a2ee3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/234382115af445db932a657af0596b69.png
[43c9efc3f989890cd615a80688abb028.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/067fc4b983c44b23a8888ca48e54064b.png
[de31c22afa028374d887ac146639d551.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/eaa3524bc8344185bb7d7381f08f9545.png
[f70d087ca045bf129ec945d03694ab45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3a0c28c9a3494d59bf503c26e7650cbd.png