目錄
一，棧_刷題必備
二，stack實(shí)現(xiàn)
1.什么是容器適配器
2.STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)?
了解補(bǔ)充：容器——deque?
1. deque的缺陷
2. 為什么選擇deque作為stack和queue的底層默認(rèn)容器
三，queue實(shí)現(xiàn)
1. 普通queue?
2,優(yōu)先級(jí)隊(duì)列（有難度）
<1>. 功能
<2>. 模擬實(shí)現(xiàn)
1). 利用迭代器_構(gòu)造
2).仿函數(shù)
sort函數(shù)中的仿函數(shù)使用理解
結(jié)語
一，棧_刷題必備
常見接口：?
stack()? ?? 造空的棧empty()? ? 檢測(cè) stack 是否為空size()? ? ? ? 返回 stack 中元素的個(gè)數(shù)top()? ? ? ?? 返回棧頂元素的引用push()? ? ? 將元素 val 壓入 stack 中pop()? ? ? ? 將 stack 中尾部的元素彈出
?簡單應(yīng)用，刷點(diǎn)題：
155.?最小棧
棧的壓入、彈出序列_牛客題霸_?？途W(wǎng)
150.?逆波蘭表達(dá)式求值
二，stack實(shí)現(xiàn)
思路：在C語言期間，我們可以通過鏈表，數(shù)組形式實(shí)現(xiàn)過stack，而數(shù)組形式效率更高，所以stack的實(shí)現(xiàn)可以直接復(fù)用vector接口，包裝成棧先進(jìn)后出的特性。
#pragma once
#include <iostream>
#include <vector>
#include <list>
using namespace std;
namespace my_s_qu
{
template <class T >
class stack
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
void Pop()
{
Data.pop_back();
}
T& top()
{
return Data.back();
}
const T& top() const
{
return Data.back();
}
bool empty() const
{
return Data.empty();
}
size_t size() const
{
return Data.size();
}
private:
vector<T> Data;
};
}很簡單不是嗎？ 到這里并沒有結(jié)束，我們發(fā)現(xiàn)，我們的棧只能通過vector實(shí)現(xiàn)。根據(jù)c++標(biāo)準(zhǔn)庫，我們還差個(gè)適配器的實(shí)現(xiàn)，換句話說，我們實(shí)現(xiàn)的棧不支持容器適配器。?
1.什么是容器適配器
2.STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)?
回到我們棧的實(shí)現(xiàn)，我們僅支持vector模式設(shè)計(jì)，優(yōu)化為成容器適配器支持所有容器，都能支持棧的先進(jìn)后出的特性。（在我看來這中思想更為重要）
namespace my_s_qu
{
template <class T, class container = deque<T> > // 添加容器模板
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
......
private:
container Data; // 容器換成模板
};
}其中deque又是什么？
了解補(bǔ)充：容器——deque?
?
那deque是如何借助其迭代器維護(hù)其假想連續(xù)的結(jié)構(gòu)呢？?
?
1. deque的缺陷
優(yōu)勢(shì)：?
與vector比較，deque的 優(yōu)勢(shì)是： 頭部插入和刪除效率高。? 不需要搬移元素，效率特別高，而且在 擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是必vector高的。
與list比較， 優(yōu)勢(shì)： 支持隨機(jī)訪問。其底層是連續(xù)空間， 空間利用率比較高，不需要存儲(chǔ)額外字段。
缺陷：??
不適合遍歷。因?yàn)樵诒闅v時(shí)，deque的迭代器要 頻繁的去 計(jì)算每個(gè)數(shù)據(jù)的位置，導(dǎo)致 效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list， deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是， STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。
2. 為什么選擇deque作為stack和queue的底層默認(rèn)容器
1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進(jìn)行操作。2. 在stack中元素增長時(shí)，deque比vector的效率高(擴(kuò)容時(shí)不需要搬移大量數(shù)據(jù))；queue中的元素增長時(shí)，deque不僅效率高，而且內(nèi)存使用率高。
三，queue實(shí)現(xiàn)
1. 普通queue?
?queue實(shí)現(xiàn)，我們這次以容器適配器進(jìn)行。
template <class T, class container = deque<T>>
class queue
{
public:
void push_back(const T& x)
{
Data.push_back(x);
}
void Pop()
{
Data.pop_front();
}
T& back()
{
return Data.back();
}
const T& back() const
{
return Data.back();
}
T& front()
{
return Data.front();
}
const T& front() const
{
return Data.front();
}
bool empty() const
{
return Data.empty();
}
size_t size() const
{
return Data.size();
}
private:
container Data;
};2,優(yōu)先級(jí)隊(duì)列（有難度）
簡介：
<1>. 功能
priority_queue()/priority_queue(fifirst, last)? ? ??構(gòu)造一個(gè)空的優(yōu)先級(jí)隊(duì)列empty( )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?檢測(cè)優(yōu)先級(jí)隊(duì)列是否為空，是返回true，否則返回falsetop( )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回優(yōu)先級(jí)隊(duì)列中最大(最小元素)，即堆頂元素push(x)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 在優(yōu)先級(jí)隊(duì)列中插入元素xpop()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 刪除優(yōu)先級(jí)隊(duì)列中最大(最小)元素，即堆頂元素pop_back()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 刪除容器尾部元素
<2>. 模擬實(shí)現(xiàn)
完成優(yōu)先級(jí)隊(duì)列，需要用到堆方面的知識(shí)，如果堆大家不太熟悉了，建議將堆實(shí)現(xiàn)內(nèi)容復(fù)習(xí)一遍：
詳解樹與二叉樹的概念，結(jié)構(gòu)，及實(shí)現(xiàn)（上篇）_花果山~~程序猿的博客-CSDN博客
?利用堆方面知識(shí)，完成最基礎(chǔ)的框架：
namespace my_priority_queue
{
template <class T, class container = vector<T>>
class priority_queue
{
public:
// 自定義類型，不需要給他初始化
void ajust_up(size_t child)
{
int parent;
while (child > 0)
{
parent = child / 2;
if (_pri_queue[child] > _pri_queue[parent]) // 寫大堆
{
std::swap(_pri_queue[child], _pri_queue[parent]);
child = parent;
parent = child / 2;
}
else
{
break;
}
}
}
T& top()
{
return _pri_queue[0];
}
bool empty()
{
return _pri_queue.empty();
}
void push(const T& x)
{
_pri_queue.push_back(x);
// 向上調(diào)整
ajust_up(_pri_queue.size() - 1);
}
size_t size()
{
return _pri_queue.size();
}
void ajust_down()
{
size_t parent = 0;
size_t child = 2 * parent + 1;
while (child < _pri_queue.size())
{
if (child + 1 < _pri_queue.size() && _pri_queue[child + 1] > _pri_queue[child])
{
child++;
}
if (_pri_queue[parent] < _pri_queue[child])
{
std::swap(_pri_queue[parent], _pri_queue[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_pri_queue[0], _pri_queue[size() - 1]);
// 向下調(diào)整
_pri_queue.pop_back();
ajust_down();
}
private:
container _pri_queue;
};
}這里我們會(huì)有一個(gè)疑問，那我們要構(gòu)建升序怎么辦？?仿函數(shù)會(huì)解釋
1). 利用迭代器_構(gòu)造
// 自定義類型，不需要給他初始化
priority_queue()
{}
template <class newiterator>
priority_queue(newiterator begin, newiterator end)
: _pri_queue()
{
while (begin != end)
{
push(*begin);
begin++;
}
}2).仿函數(shù)
在該場景下，我們的優(yōu)先級(jí)隊(duì)列已經(jīng)實(shí)現(xiàn)了降序的功能，那我們?nèi)绾螌?shí)現(xiàn)升序？ 什么你說再寫一段，改一下符號(hào)？？
這里仿函數(shù)就得引出了，仿函數(shù)，那么它并不是函數(shù)，那是什么？ （仿函數(shù)比如：less, greater）
?仿函數(shù)本質(zhì)是一個(gè)類，根據(jù)上圖中，compare 模板，說明這里的仿函數(shù)，就是用來靈活改變大小堆符號(hào)的。
我們直接實(shí)現(xiàn)結(jié)果：
template <class T>
struct less
{
bool operator()(const T& left, const T& right)const
{
return left < right;
}
};
template <class T>
struct greater
{
bool operator()(const T& left, const T& right)const
{
return left > right;
}
};?這個(gè)兩個(gè)類都是重載了operator(),因此我們?cè)趯?shí)例化對(duì)象后，使用：
template <class T,class compare = less<T>>
compare? ?t;
cout <<? t(1, 2) << endl;? ? ?
從外表來看，就像一個(gè)函數(shù)調(diào)用，但實(shí)際是，一個(gè)類的成員函數(shù)的調(diào)用
t.operator(1,2)?
?這樣我們就可以直接改變仿函數(shù)的類，來控制大小堆了。?
sort函數(shù)中的仿函數(shù)使用理解
函數(shù)模板中：?
?sort函數(shù)作為行參中使用：
??
sort(s.begin, s.end, greater<int> () );? ?// 函數(shù)中是要做參數(shù)的，我們加個(gè)括號(hào)就是一個(gè)匿名對(duì)象了文章來源：http://www.zghlxwxcb.cn/news/detail-636047.html
結(jié)語
? ?本小節(jié)就到這里了，感謝小伙伴的瀏覽，如果有什么建議，歡迎在評(píng)論區(qū)評(píng)論，如果給小伙伴帶來一些收獲請(qǐng)留下你的小贊，你的點(diǎn)贊和關(guān)注將會(huì)成為博主創(chuàng)作的動(dòng)力。文章來源地址http://www.zghlxwxcb.cn/news/detail-636047.html
到了這里，關(guān)于【STL】優(yōu)先級(jí)隊(duì)列&反向迭代器詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
