各位好友，本期开战 Stack（栈区）~~ Queue（队列）
------->Stack（栈区）
对于 栈区， 可使用 Vector （容器）~~ List （链表）进行模拟实现 ！--->如下 ：>
//栈区__模拟实现 "Stack.h"
//注意：>deque 适配器
#include <iostream>
#include <deque>
#include <vector>
#include <list>
using std :: cout;
using std :: endl;
using std :: vector;
using std :: list;
using std :: deque;
namespace UC
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& Top()
{
return _con.back();
}
bool empty()
{
_con.emppty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}------>测试__Stack ：>
//测试栈区
//
#include "Stack.h"
void test_stack()
{
UC ::stack<int, vector<int>> T1;
T1.push(21);
T1.push(22);
T1.push(23);
T1.push(32);
T1.push(38);
while(!T1.empty())
{
cout << T1.Top() << " ";
T1.pop();
}
cout << endl;
UC ::stack<int, list<int>> T2;
T2.push(110);
T2.push(111);
T2.push(112);
T2.push(123);
T2.push(138);
while(!T2.empty())
{
cout << T2.Top() << " ";
T2.pop();
}
cout << endl;
}
int main()
{
test_stack();
return 0;
}为了方便好友们， 有更好的观感体验， 现附上 彩色代码图样 ：>
------>"Stack.h"
------>"Stack.cpp"
------->Queue（队列）
注意 ：>队列 模拟， vector（容器）不支持 头插 与头删 。 因此， 可以使用 List 进行 实现 ！
queue 接口有 头删 ， 然而 ，用 vector 进行分装 效率太低， 故 可借助 List 进行模拟实现 !
//队列__模拟实现 "Queue.h"
//注意：>deque 适配器
#include <iostream>
#include <list>
#include <deque>
#include <vector>
using std :: cout;
using std :: endl;
using std :: deque;
using std :: list
using std :: vector;
namespace UC
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
//使用 vector 进行创建变量
//此种头删不支持
//_con.pop_front();
//强制让 vector 支持 头删
//注意：效率很低
_con.earse(_con.begin());
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}------->测试__Queue ：>
//测试 队列
//注意：>deque 适配器
#include "Queue.h"
void test_queue()
{
UC :: queue<int, list<int>> Q1;
Q1.push(21);
Q1.push(22);
Q1.push(23);
Q1.push(32);
Q1.push(38);
while(!Q1.empty())
{
cout << Q1.Top() << " ";
Q1.pop();
}
cout << endl;
//强制使用 vector(容器)进行 创建变量
//此种方法效率 极其低 ！
UC :: queue<int, vector<int>> Q2;
Q2.push(110);
Q2.push(111);
Q2.push(112);
Q2.push(123);
Q2.push(138);
while(!Q2.empty())
{
cout << Q2.Top() << " ";
Q2.pop();
}
cout << endl;
}
int main()
{
test_queue();
return 0;
}为了方便好友们， 有更好的观感体验， 现附上 彩色代码图样 ：>
------>"Queue.h"
------->"Test__queue.cpp" ----->NO.1 :>
-------->"Test__queue.cpp" ------>NO.2 :>
各位好友，上述 实现过程 涉及到一个新知识点 ：>deque （适配器 ）
下面讲述 什么是 适配器 ？适配器 有哪些优缺点 ？
----->如下 ：>
--------->何为 适配器 ？
适配器 又称 ：>容器适配器 ！根据 STL 标准库中 Stack 与queue 的底层结构 ，并没有将二者 划分到 容器行列 ！而是将它们称为 容器的适配器 ；
而 Stack 与 queue 只是对容器的接口进行了 包装， STL 中 Stack 与queue 默认使用的容器 为
deque （双端队列）
--------->原因 ：>
（1）与 Vector 相比， deque 优势 ：>头部插入 和删除元素， 不需要搬移， 效率非常高 。
在 Vector 扩容过程中， 需进行 搬运大量元素 。 因此， deque 更加高效 ；
（2）与 List 相比， deque 底层结构是连续的空间， 空间利用率较高 ；（以上两点为 优势 ）
（3）deque 劣势 ：>不适合遍历访问 。在实际中， 多用线性结构， 如， Vector 与 List ；
在遍历过程中， deque 迭代器 需要频繁访问并且去检测 是否移向某一小段空间边界， 导致其效率低下 ！
--------->小总结 ：>
Stack （栈区）可以使用的底层结构 :> Vector 与List ；Queue（队列） 只能使用 List 作为底层结构 !
A. Satck 与queue 不需要进行遍历（因为 stack 与queue 没有迭代器）只需要固定在某一端即可 ;
B. Stack（栈区）中元素的增长， Deque 比较于 Vector 效率更高， 并不会进行大量数据的搬运 ;
Queue （队列）是连续空间，Deque 比较于 List 空间利用率更高 ！
--------->deque 介绍 ：>
---->deque（双端队列） 双开口 ~~ 连续的数据结构 。双开口含义 ：>头尾两端 可进行插入 与删除 ！
同 Vector 相比， 头插效率很高， 与 List 相比较 ， 空间利用率很高 ！如下 ：>
注意 ：>deque 并不是真正的 连续空间，而是由一段段 连续的小空间拼接而成
------------------------------->实际上， deque 类似于 一个动态二维数组 ！
下面展示 deque（双端队列）排序 ----->效率对比 :>
---------->deque ~~ Vector ：>
------->NO.1 ：>
// deque（双端队列）
//排序比较 --->deque__拷贝 ~~ vector
#include <iostream>
#include <vector>
#include <deque>
#include <time.h>
#include <stdlib.h>
#include <algorithm>
using std :: cout;
using std :: endl;
using std :: deque;
using std :: vector;
int main()
{
srand(time(0));
vector<int> v1;
vector<int> v2;
const int N = 1000000;
v1.reserve(N);
v2.reserve(N);
deque<int> dq;
for(int i = 0; i < N; i++)
{
auto e = rand();
v2.push_back(e);
dq.push_back(e);
}
int begin1 = clock();
//先拷贝到 vector
for(auto e : dq)
{
v1.push_back(e);
}
sort(v1.begin(), v1.end());
//再拷贝回去
size_t i = 0;
for(auto& e : dq)
{
e = v1[i++];
}
int end1 = clock();
int begin2 = clock();
sort(v2.begin(), v2.end());
int end2 = clock();
cout << "deque copy to vector sort :> " << end1 - begin1 << endl;
cout << "vector sort :> " << end2 - begin2 << endl;
}为了方便好友们， 有更好的观感体验， 现附上 彩色 代码图样 ：>
------->NO.1 ：>
---------->可见 ：>Vector 排序__更胜一筹 ！
---------->deque__拷贝 ~~ deque ：>
------->NO.2 :>
// deque（双端队列）
//排序比较 --->deque__拷贝 ~~ deque
#include <iostream>
#include <vector>
#include <deque>
#include <time.h>
#include <stdlib.h>
#include <algorithm>
using std :: cout;
using std :: endl;
using std :: deque;
using std :: vector;
int main()
{
srand(time(0));
vector<int> v;
const int N = 1000000;
v.reserve(N);
deque<int> dq1;
deque<int> dq2;
for(int i = 0; i < N; i++)
{
auto e = rand();
dq1.push_back(e);
dq2.push_back(e);
}
int begin1 = clock();
//先拷贝到 vector
for(auto e : dq1)
{
v.push_back(e);
}
sort(v.begin(), v.end());
//再拷贝回去
size_t i = 0;
for(auto& e : dq1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
sort(dq2.begin(), dq2.end());
int end2 = clock();
cout << "deque copy to vector sort :> " << end1 - begin1 << endl;
cout << "deque sort :> " << end2 - begin2 << endl;
}为了方便好友们， 有更好的观感体验， 现附上 彩色 代码图样 ：>
------->NO.2 ：>
---------->可见 ：>deque 排序__更加慢 ！
各位好友， 本期内容 已完结 ！
下一期， 继续推进 ------>优先级队列 ！ "敬请期待 ！😊😊