[Vssue]栈与队列理论基础.md

[youngyangyang04]

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

[WEITAOLEE]

Mark and exercise.

[Du1in9]

C++

• 栈

先进后出的数据结构，不允许有遍历行为，不提供迭代器，SGI STL 中以 deque 为缺省情况下的底部结构。

可以指定 vector 为底层实现，初始化语句如下：stack<int, vector<int>> third;

所以 STL 栈不被归类为容器，而被归类为 container adapter（ 容器适配器）。

• 队列

先进先出的数据结构，不允许有遍历行为，不提供迭代器，SGI STL 中以 deque 为缺省情况下的底部结构。

可以指定 list 为底层实现，初始化 queue 的语句如下：queue<int, list<int>> third;

所以 STL 队列不被归类为容器，而被归类为 container adapter（ 容器适配器）。

Java

• 栈

虽然 Stack 类继承自 Vector 类，而 Vector 类使用数组。实际上，更常见的是使用数组或链表实现栈。

① 数组实现：入栈操作将元素添加到数组的末尾，出栈操作则移除数组末尾的元素。

② 链表实现：入栈操作将元素插入到链表的头部，出栈操作则移除链表头部的元素。

• 队列

队列的底层实现通常使用数组、链表或 deque。提供了 ArrayDeque 和 LinkedList 两种常见的实现类。

① 数组实现：入队操作将元素添加到数组的末尾，出队操作则移除数组的头部元素。

② 链表实现：入队操作将元素添加到链表的末尾，出队操作则移除链表的头部元素。

[li123xingye]

STL 队列不被归类为容器，而被归类为container adapter（ 容器适配器）