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;
}
else
return;
}
}
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的底层数据结构。
但是
因为stack queue不需要遍历，使用deque几乎是结合了它的优点