C++中stack类和queue类
感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步
数据结构习题_LaNzikinh篮子的博客-CSDN博客
初阶数据结构_LaNzikinh篮子的博客-CSDN博客
收入专栏：C++_LaNzikinh篮子的博客-CSDN博客
其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客
个人主页：LaNzikinh-CSDN博客
文章目录
- 前言
- 一.容器适配器
- 二.栈的实现stack
- 三.队列的实现queue
- 四.优先级队列priority_queue（）
- 五.deque（双向队列）
- 总结
前言
前面我们讲解了C++中List，Vector,和string类的使用和底层逻辑，今天我们来利用前3个类，来搭建栈和队列，在讲解前，我们先来引入一个容器适配器的概念
一.容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的，代码设 计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL标准库中stack和queue的底层结构中stack和queue默认使用deque。
二.栈的实现stack
接口函数
1.push()将元素val压入stack中
2.top()返回栈顶元素的引用
3.pop()将stack中尾部的元素弹出
4.size()返回stack中元素的个数
5.empty()检测stack是否为空
实现
我们之前说过，栈他是一种适配器，stack只是对其他容器的接口进行了包装，所以我们从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。
#include<vector>
namespace yyz
{
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
接口函数
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
实现
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器 类，则使用标准容器deque。
#include <list>
namespace yyz
{
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（）
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
这里我们的实现是用堆去实现的，堆的本质是数组，所以优先级队列作为适配器，只需要通过对vector进行通用的封装即可
#include<vector>
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
namespace yyz
{
// 默认是大堆
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void AdjustDown(int parent)
{
// 先假设左孩子小
size_t child = parent * 2 + 1;
Compare com;
while (child < _con.size()) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}五.deque（双向队列）
我们前面说了，栈和队列在STL标准库中stack和queue的底层结构中stack和queue默认使用deque。所以我们这次来看看deque到底是什么
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
在标准库里实现的stack和queue
namespace yyz
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front() const
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}namespace yyz
{
// Containerתstack
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
//return _con.func();
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}总结
这次讲解了C++中栈和队列的使用，下次对模板在做一点补充