【java基础】【算法】栈和队列

青旅半醒 2024-03-27 16:33 47阅读 0赞

## 栈 ##

栈（stack ），一种遵循先进后出（FILO—First-In/Last-Out）原则的线性存储结构。

### Java实现 ###

api: [Stack (Java Platform SE 8 ) (matools.com)][Stack _Java Platform SE 8 _ _matools.com]  
栈（Stack） 这个类继承自 Vector ，底层用数组实现，是 JDK1.0 时代的产物，官方已经不推荐使用了。  
![截图自官方api][api]

图片截取自官方

因为 Vector 在方法上添加了 synchronized ，以达到线程安全的目的，不过 JVM 级别的 synchronized 特别消耗资源，已不被 Java 官方推荐使用。

所以继承自它的 Stack 更不可能被推荐使用。并且 Stack 代码很少，底层有兴趣转 Vector 源码解读吧，包括它的扩容，构造等。

**Stack 的方法：**  
![在这里插入图片描述][d38aec38cff44b7e8904db9c8c5c1363.png]

在Java中，我们用Deque可以实现Stack的功能：

*  把元素压栈：push(E)/addFirst(E)；
 *  把栈顶的元素“弹出”：pop()/removeFirst()；  
    \*取栈顶元素但不弹出：peek()/peekFirst()。

> 为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。

当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。

## 队列 ##

队列（queue），一种遵循先进先出（FIFO—first in first out）原则的线性存储结构。

### Java实现 ###

队列（Queue） 的话，JDK1.6 开始声明了 Deque（double ended queue ）双向队列接口 ，双向队列同时具备栈和队列的功能。

## 相关题目 ##

## 参考资料 ##

*  https://blog.csdn.net/m0\_46144826/article/details/105405172

[Stack _Java Platform SE 8 _ _matools.com]: https://www.matools.com/file/manual/jdk_api_1.8_google/java/util/Stack.html
[api]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e6db5da0cea54b4998770ba2063d1cf9.png
[d38aec38cff44b7e8904db9c8c5c1363.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/87342d52702c4acc8cbb619c46f66922.png