STL—stack与queue

Stack

stack的使用

stack的模拟实现

queue

queue的使用

queue的模拟实现

priority_queue

priority_queue的用法

priority_queue的模拟实现

容器适配器

种类

Stack

http://www.cplusplus.com/reference/stack/stack/?kw=stack

stack是栈，后入先出

stack的使用

stack	构造栈
empty	是否为空
size	元素个数
top	返回栈顶元素的引用
push	将元素val压入stack中
pop	将stack中尾部的元素弹出

stack的模拟实现

template<class T>
class stack
{ 
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::vector<T> _c;
};

queue

cplusplus.com/reference/queue/queue/

queue 队列后入先出

queue的使用

queue	构造队列
empty	是否为空
size	元素个数
front	返回队列头元素的引用
back	返回队列尾元素的引用
push	将元素val压入队尾
pop	将stack中头部的元素弹出

queue的模拟实现

template<class T>
class queue
{ 
public:
queue() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_front();}
T& back() {return _c.back();}
const T& back()const {return _c.back();}
T& front() {return _c.front();}
const T& front()const {return _c.front();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::list<T> _c;
};

priority_queue

cplusplus.com/reference/queue/priority_queue/

这个是优先队列，会自排序，内部是按照堆排序来的，可以设定是正排序或者逆排序

priority_queue的用法

priority_queue（）	构造空的优先级队列
empty	判空
top	返回堆顶元素
push	插入元素x
pop	删除堆顶元素

greater<T> 排列反序的重载

priority_queue的模拟实现

#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace m
{template<class T>struct less{bool operator()(const T& A,const T& B){return A < B;}};template<class T>struct greater{bool operator()(const T& A, const T& B){return A > B;}};template <class T, class Container = vector<T>, class Compare = less<T> >class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){this->push(*first);first++;}}bool empty() const{return c.empty();}size_t size() const{return c.size();}T top() const{return c.front();}void push(const T& x){c.push_back(x);this->AdjustUP(c.size() - 1);}void pop(){if (empty())return;swap(c.front(),c.back());c.pop_back();AdjustDown(0);}private:void AdjustUP(int child){int parent = (child - 1) / 2;while (child){if (comp(c[parent], c[child])){swap(c[parent], c[child]);child = parent;parent = (child - 1) / 2;}else{return;}}}void AdjustDown(int parent){int child = 2 * parent;while (child < size()){if (child < size() - 1 && comp(c[child], c[child + 1])){child++;}if (comp(c[parent], c[child])){swap(c[parent], c[child]);parent = child;child = 2 * parent;}elsereturn;}}void swap(T& left, T& right){T c = left;left = right;right = c;}Container c;Compare comp;};};

容器适配器

容器适配器是一种机制，能使某种容器的行为看起来像另一种容器。它接受一种已有的容器类型，并使其操作起来像另一种类型的容器。

在C++标准库中，容器适配器是一种特殊的数据结构，它并不直接存储数据，而是通过对底层容器的接口进行包装和转换，来实现特定的数据访问和操作方式。

种类

C++标准库定义了三个主要的容器适配器，分别是stack（栈）、queue（队列）和priority_queue（优先队列）

一般情况下 stack是基于deque实现的

queue是基于deque实现的

priority_queue是基于vector实现的

deque

deque是一种双开口的“连续”的空间数据结构，可以在头尾插入和删除，时间复杂度为O（1），对比vector头插效率高，对比list空间利用率高

deque是一种复杂的数据结构

缺点是

        与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
        与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
        但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

但是