您的位置:首页 > 房产 > 建筑 > C++基础知识8 stack queue

C++基础知识8 stack queue

2024/12/23 8:08:26 来源:https://blog.csdn.net/Yusei_0523/article/details/142317793  浏览:    关键词:C++基础知识8 stack queue

stack queue

  • 1.容器适配器
  • 2. stack的介绍和使用
    • 2.1 stack的介绍
    • 2.2 stack的使用
    • 2.3 stack的模拟实现
  • 3. queue的介绍和使用
    • 3.1 queue的介绍
    • 3.2 queue的使用
    • 3.3 queue的模拟实现
  • 4.priority_queue的介绍和使用
    • 4.1 priority_queue的介绍
    • 4.2 priority_queue的使用
    • 4.3 priority_queue的模拟实现

1.容器适配器

在这里插入图片描述

我在前面实现初阶数据结构中提到过栈和队列底层用数组或者链表实现都是可以的,当时我们实现时栈底层数组而队列实现时底层用了链表。而在这里我们声明一个容器模版同时实现两种底层的数据结构

2. stack的介绍和使用

2.1 stack的介绍

栈:⼀种特殊的线性表,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插⼊操作叫做进栈/压栈/⼊栈,⼊数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
在这里插入图片描述

2.2 stack的使用

在这里插入图片描述

2.3 stack的模拟实现

从栈的接口中可以看出,栈可以是一种特殊的vector,因此使用vector完全可以模拟实现stack。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
using std::vector;
namespace Yusei
{template<class T, class Container = vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

3. queue的介绍和使用

3.1 queue的介绍

概念:只允许在⼀端进⾏插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
⼊队列:进⾏插⼊操作的⼀端称为队尾
出队列:进⾏删除操作的⼀端称为队头

3.2 queue的使用

在这里插入图片描述

3.3 queue的模拟实现

因为queue的接口中存在头删和尾插,因此使用vector来封装效率太低,故可以借助list来模拟实现queue

#define _CRT_SECURE_NO_WARNINGS 1
#include<list>
using std::list;
namespace Yusei
{template<class T, class Container = list<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;};
}

4.priority_queue的介绍和使用

优先队列就是堆的别名

4.1 priority_queue的介绍

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

  2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶 部的元素)。

  3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。

  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过 随机访问迭代器访问,并支持以下操作:
    在这里插入图片描述

  5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue 类实例化指定容器类,则使用vector。

  6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数make_heap、push_heap和pop_heap来自动完成此操作。

4.2 priority_queue的使用

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

在这里插入图片描述

4.3 priority_queue的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
using std::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 Yusei
{// 默认是大堆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() && 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;};
}

PriorityQueue的实现与初阶数据结构堆的实现类似,实际上我们主要想强调的是虚函数


虚函数是一个类,它重载了operator(),也就是说在比较大小的逻辑处我们通过类对象重载后的()来代替。

实际上stl实现的stack和Queue默认容器是deque,它是list和vector的缝合体。大家可以了解一下

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com