stack和queue

stack

stack是作为容器适配器被实现的, 容器适配器是对特定类封装作为其底层的容器, 并提供一组特定的成员函数来访问其元素, 将特定类作为其底层的, 元素特定容器的尾部(即栈顶)被压入和弹出

stack的使用

stack()					// 构造空的栈
empty()					// 检测stack是否为空
size()					// 返回stack中元素的个数
top()					// 返回栈顶元素的引用
push()					// 将元素val压入栈中
pop()					// 删除栈顶的元素

queue

队列是一种容器适配器, 从容器一端插入元素, 另一端提取元素. 元素从队尾入队列, 从队头出队列

queue的使用

queue()					// 构造空的队列
empty()					// 检测队列是否为空, 是返回true, 否则返回false
size()					// 返回队列中有效元素的个数
front()					// 返回队头元素的引用
back()					// 返回队尾元素的引用
push()					// 在队尾将元素val入队列
pop()					// 将队头元素出队列

priority_queue优先队列

  • 优先队列是一种容器适配器, 根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器, 在vector上有使用了堆算法将vector中元素构造成堆的结构, 因此priority_queue就是堆, 所有需要用到堆的位置, 都可以考虑priority_queue. 默认情况下priority_queue是大堆

priority_queue()/priority_queue(firs, last)		// 构造一个空的优先级队列
empty()					// 检测优先级队列是否为空, 是返回true, 否则返回false
top()					// 返回优先级队列中最大(最小)元素, 即堆顶元素
push(x)					// 在优先级队列插入元素x
pop()					// 删除优先级队列中最大(最小)元素, 即堆顶元素

适配器

适配器是一种设计模式, 该种模式是将一个类的接口转换成客户希望的另一个接口

为什么将stack, queue和priority_queue称为容器适配器

STL并没有将stack, queue, priority_queue划分在容器的行列, 而是将其称为容器适配器. 这是因为每个容器在底层都有自己的实现方式, 而stack, queue, priority_queue只是在底层将其他容器进行了封装

为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构, 因此只要具有push_back()和pop_back()操作的线性结构, 都可以作为stack的底层容器, 比如vector的list

queue是先进先出的特殊线性结构, 只要具有push_back()和pop_front()操作的线性结构都可以作为queue的底层容器, 比如list

但主要是因为:

  • stack和queue不需要遍历(因此stack和queue没有迭代器), 只需要在固定的一端或两端进行操作
  • 当stack中元素增长时, deque比vector的效率高, queue中的元素增长时, deque不仅效率高, 而且内存使用率高

 


我们的征途是星辰大海!