当前位置: 首页 > news >正文

C++ ----------- 栈和队列

C++ ----------- 栈和队列

  • 1.Stack的使用
    • 1.1习题
    • 1.2 Stack 模拟实现(容器)
  • 2.queue队列使用
    • 2.1 练习
    • 2.2队列的模拟实现(容器)
  • 3.priority_queue的使用和介绍
    • 3.1 push_heap(插入堆)
    • 3.2 make_heap(建堆)
    • 3.3 pop_heap
    • 3.2 priority_queue 的使用
    • 3.3练习
    • 3.4 priority_queue模拟实现
  • 4 适配容器
    • 4.1 什么是适配器
    • 4.2 STL标准库中stack和queue的底层结构
    • 4.3 deque的简单介绍(了解)
    • 4.5 deque的缺陷
    • 4.6为什么选择dequeue作为queue或stack的底层默认容器
    • 4.7 STL标准库中对于stack和queue的模拟实现

1.Stack的使用

函数功能说明
stack()构造
empty()判空
size()返回stack中元素个数
top()返回栈顶元素
push()压栈
pop()出栈

1.1习题

最小栈

class MinStack {
public:MinStack() {}void push(int val) {x_stack.push(val);if (min_stack.empty() || min_stack.top() >= val) {min_stack.push(val);}}void pop() {//如果_min栈顶的元素等于出栈的元素,_min顶的元素要移除if (x_stack.top() == min_stack.top()) {min_stack.pop();}x_stack.pop();}int top() { return x_stack.top(); }int getMin() { return min_stack.top(); }private:stack<int> x_stack;//保存入栈元素stack<int> min_stack;//保存最小元素
};

解题思想:建俩个栈,一个入数据,一个记录最小数据:
在这里插入图片描述

判断栈的弹出压入序

#include <stack>
class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code heresize_t pos=0;stack<int> s1;for(auto& e:pushV){//入栈s1.push(e);//出栈while(!s1.empty()&&s1.top()== popV[pos]){s1.pop();pos++;}}return s1.empty();}
};

解题思想:
在这里插入图片描述

1.2 Stack 模拟实现(容器)

template<class T, class Container>//适配容器来实现栈
class StacK
{
public:void push_back(const T& x){_con.push_back(x);//把尾当做栈顶}const T& top(){return _con.back();}void pop(){_con.pop_back();}size_t size() const{return _con.size();}bool empty(){return _con.empty();}
private:Container _con;//容器
};

在这里插入图片描述

用不同容器来实现栈,数组栈,链表栈…;

2.queue队列使用

函数功能说明
queue()构造
empty()判空
size()返回stack中元素个数
front()返回队列头元素
push()在队尾将元素入队列
pop()将对头出队列

2.1 练习

队列实现栈

class MyStack {
queue<int> in;
queue<int> out;
public:MyStack() {}void push(int x) {in.push(x);while(!out.empty()){in.push(out.front());out.pop();}swap(in,out);}  int pop() {int s=out.front();out.pop();return s;}int top() {return out.front();}bool empty() {return out.empty();}
};

解题思想:

入栈队列q1,出栈q2q1入栈,如q2的值不为空,那么先要吧q2的值给q1,在把q1的值换给q2。这样才能保持栈的后进先出

2.2队列的模拟实现(容器)

	template<class T, class Container>//适配容器来实现栈class queue{public:queue() {}void push(const T& x){_con.push_back(x);}const T& front(){return _con.front();}const T& back(){return _con.back();}void pop(){_con.pop_back();}const size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;//容器};

3.priority_queue的使用和介绍

 1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的2. 此类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。

4.底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过
随机访问迭代器访问,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素

 5.标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。6. 需要支持随机访问迭代器,以便始终在内部保持堆结构.容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

在这里插入图片描述
提醒:push_heap,pop_heap,make_heap,都包含在algorithm里面
在这里插入图片描述

3.1 push_heap(插入堆)

//形式  
push_heap(随机迭代器1,随机迭代器2,仿函数)//调堆
//make_heap调堆
int myints[] = { 10,20,30,5,15 };
std::vector<int> v(myints, myints + 5);
v.push_back(99); std::push_heap(v.begin(), v.end());
std::cout << "max heap after push: " << v.front() << '\n';

3.2 make_heap(建堆)

int myints[] = { 10,20,30,5,15 };
std::vector<int> v(myints, myints + 5);
std::make_heap(v.begin(), v.end());
std::cout << "initial max heap   : " << v.front() << '\n';

在这里插入图片描述

3.3 pop_heap

int myints[] = { 10,20,30,5,15 };
std::vector<int> v(myints, myints + 5);std::pop_heap(v.begin(), v.end()); v.pop_back();std::cout << "max heap after pop : " << v.front() << '\n';

在这里插入图片描述

3.2 priority_queue 的使用

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

【注意】

1.默认情况下,priority_queue 是大堆
在这里插入图片描述
1.2如果要建小堆,那么要用仿函数来建 大或小堆
在这里插入图片描述

2.如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
在这里插入图片描述

using namespace std;
class Date
{
public:Date(int year=2000,int month=01,int data=01):_year(year),_month(month),_data(data){}bool operator<(const Date& x) const {return (_year < x._year)||((_year==x._year)&&(_month < x._month))||((_month == x._month)&&(_data < x._data));}bool operator==(const Date& x) const {return _year == x._year&& _month == x._month && _data == x._data;}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._data;return _cout;}
private:int _data;int _month;int _year;
};
void TestPriorityQueue()
{//自定义类型要支持<的比较priority_queue<Date> s;s.push(Date(2000, 2, 2));s.push(Date(2001, 2, 2));s.push(Date(2002, 2, 2));cout << s.top() << endl;
}

3.3练习

top_k问题

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> s;for (auto e : nums) {s.push(e);}for (int i = 0; i < k - 1; ++i) {s.pop();}return s.top();}
};

解题思路:运用priority_queue,来解决top_k问题,priority_queue底层是堆。
1:先把nums数据建堆
2:再用for循环来遍历出第k最大个数

3.4 priority_queue模拟实现

template<class T>
struct compare
{bool operator()(const T& x, const T& y){return x < y;}
};template<class T,class Container = vector<T>,class compare= compare<T>>class priority_queue//优先队列本质是个堆{public:void Adjust(size_t child)//向上调堆{compare com;size_t parent = (child-1)/2;while (child > 0){if (com(_con[child],_con[parent])){swap(_con[child],_con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Adjustdown(size_t parent)//向下调堆{size_t child = (parent * 2) + 1;compare com;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1],_con[child])){child = child + 1;}if (com(_con[child] , _con[parent])){swap(_con[child],_con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){//调堆_con.push_back(x);Adjust(_con.size() - 1);}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;};
 priority_queue底层是堆,而对于调堆如果不懂的话可以去看《数据结构》堆,再来这里看priority_queue模拟实现,这里不做解释。

4 适配容器

4.1 什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

相当于安卓,苹果,三星充电接口各有不同

在这里插入图片描述

4.2 STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

4.3 deque的简单介绍(了解)

 1:deque的原理介绍

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

在这里插入图片描述

【注意】deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

在这里插入图片描述

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个
动态的二维数组,其底层结构如下图所示:

在这里插入图片描述

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:
在这里插入图片描述
dequeue 迭代器有四个结点,cur ,first ,last,node。node指针指向中控器上的结点,firs指向buffer的第一个buffer第一个结点,而cur指向是有buffer有效结点的下一个结点,而last指向的是buffer最后一个结点

在这里插入图片描述

4.5 deque的缺陷

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

4.6为什么选择dequeue作为queue或stack的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如: list
但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。2.在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。

4.7 STL标准库中对于stack和queue的模拟实现

Stack

#include<deque>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = vector<T>>
//template<class T, class Con = list<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:
Con _c;
};
}

queue

#include<deque>
#include <list>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = list<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:
Con _c;
};
}

http://www.mrgr.cn/news/64204.html

相关文章:

  • 【flask】 flask redis的使用
  • Go语言的使用
  • 使用Cubic定制Ubuntu发行版
  • 使用Vue3DraggableResizable组件实现拖拽拉伸
  • 计算机组成原理之CPU的功能与基本结构
  • Nginx 实现动态封禁IP,详细教程来了
  • 软件设计师笔记-数据结构
  • 技术周总结10.28~11.03 周日
  • 动态规划-回文串系列——1312.让字符串变成回文串的最小插入次数
  • 祖鲁法则精要
  • 实习冲刺Day11
  • 如何利用8款工具辅助建立需求管理体系
  • CAN协议
  • 【P2-1】ESP8266 WIFI模块STA、AP、STA+AP、TCP/UDP透传工作模式介绍与AT指令介绍
  • Aicbo:解锁AI创意新纪元,一键生成视频、绘画与文字!
  • gesp的python二级题目
  • python 调用shell 脚本
  • 【机器学习】机器学习算法-线性回归算法
  • springboot河南旅游推荐系统-计算机毕业设计源码33358
  • DNS域名解析服务器--RHCE
  • Git本地分支更新推送到远程主分支上
  • 1231243545347ikih
  • 江协科技STM32学习- P33 实验-软件I2C读写MPU6050
  • 裸金属服务器和普通服务器的不同之处
  • 决策树算法
  • Java实战项目-基于 SpringBoot+Vue 的医院管理系统