在學習棧和隊列之前，我們先要了解一個東西，這個東西對我們學習本節(jié)內(nèi)容很重要。我們現(xiàn)在只是淺淺的了解一下，等stack和queue都模擬實現(xiàn)完了，我們再來仔細講
這個deque就是我們常說的容器適配器。那么，什么是容器適配器呢？
這就要牽扯出另外的知識了——設(shè)計模式（這個設(shè)計模式C++并沒有Java那么關(guān)注）
很早之前，設(shè)計模式一共有23種。到目前為止，種類在一步步的擴展
我們這里的適配器就是設(shè)計模式的一種——適配器模式；而除了我們這里的適配器以外，我們前面還學過一種設(shè)計模式——迭代器模式。這個迭代器也是一種設(shè)計模式
這里我們只要記住適配器模式和迭代器模式的作用：
迭代器模式：不暴露底層細節(jié)，封裝過后，提供統(tǒng)一的方式來訪問容器
適配器模式：用已有的東西，封裝轉(zhuǎn)換出想要的東西
我們要記住這兩個結(jié)論，下面會用到
我們只需要知道迭代器和適配器都是一種設(shè)計模式就行了，有興趣可以深入了解一下
stack文檔
接下來對stack的文檔進行簡單的總結(jié)一下：
stack是一種容器適配器，專門用在具有后進先出操作的上下文環(huán)境中，其刪除只能從容器的一端進行元素的插入與提取操作。
stack是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：
empty：判空操作
back：獲取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部刪除元素操作
我們前面數(shù)據(jù)結(jié)構(gòu)學習了棧和隊列，所以本節(jié)內(nèi)容的棧和隊列使用方面的知識就不多講了，和前面數(shù)據(jù)結(jié)構(gòu)的思路是一樣的
2、queue的使用| 函數(shù)接口 | 函數(shù)接口的作用 |
|---|---|
| stack（） | 構(gòu)建空的棧 |
| empty（） | 判斷stack是否為空 |
| size（） | 返回stack中的元素個數(shù) |
| top（） | 返回stack中的棧頂元素 |
| push（） | 向stack中壓入指定數(shù)據(jù) |
| pop（） | 彈出stack尾部的數(shù)據(jù) |
其實可以看到，有了前面的基礎(chǔ)這里就很容易理解，接口一看就知道是干什么的，有什么作用
3、stack的模擬實現(xiàn)大家是不是認為我們模擬實現(xiàn)要像以前一樣，stack是通過數(shù)組實現(xiàn)的，所以要malloc開辟，然后還要一個top數(shù)據(jù)、一個capacity、一個size…
其實這里就不用這么麻煩，我們可以更加簡單的實現(xiàn)，就是基于容器適配器的功勞
重慶分公司
重慶分公司
#includenamespace bzh
{template>//這里就是運用了適配器
//本來我們是要重新寫一個stack的，但是因為適配器的原因，我們直接通過vector轉(zhuǎn)換出來了我們想要的stack
//template>//這里使用deque也是可以的，具體為什么可以我們后面講
class stack
{public:
stack()
{}
void push(const T& x)
{_Con.push_back(x);
}
void pop()
{_Con.pop_back();
}
T& top()
{return _Con.back();
}
const T& top()const
{return _Con.back();
}
size_t size()const
{return _Con.size();
}
bool empty()const
{return _Con.empty();
}
private:
Container _Con;
};
}; 
可以看到，接口實現(xiàn)的作用是正確的，而我們模板傳參的參數(shù)就是vector類型
看得出來很簡單，那么我們就快速的也把queue搞定，進入我們的容器適配器內(nèi)容
queue文檔
進行總結(jié)一下：
隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
隊列作為容器適配器實現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。
底層容器可以是標準容器類模板之一，也可以是其他專門設(shè)計的容器類。該底層容器應至少支持以下操作:
empty：檢測隊列是否為空
size：返回隊列中有效元素的個數(shù)
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列
可以看到內(nèi)容與我們前面數(shù)據(jù)結(jié)構(gòu)的queue相差無幾。而且這里也提到了容器適配器
| 函數(shù)接口 | 函數(shù)接口的作用 |
|---|---|
| queue（） | 構(gòu)建空的隊列 |
| empty（） | 判斷隊列是否為空 |
| size（） | 返回隊列中的元素個數(shù) |
| front（） | 返回隊頭素的引用 |
| back（） | 返回隊尾素的引用 |
| push（） | 在隊尾插入指定數(shù)據(jù) |
| pop（） | 講隊頭元素出隊列 |
這些接口對于我們來說也是簡簡單單，那么我們就直接上手模擬實現(xiàn)
3、queue的模擬實現(xiàn)與stack一樣，這里使用了容器適配器
#pragma once
#include#includenamespace bzh
{//template>//這里使用deque也是可以的
template>//這里就是通過容器適配器講list轉(zhuǎn)換成我們想要的queue了
class queue
{public:
queue()
{}
void push(const T& x)
{_Con.push_back(x);
}
void pop()
{_Con.pop_front();
}
T& back()
{return _Con.back();
}
const T& back()const
{return _Con.back();
}
T& front()
{return _Con.front();
}
const T& front()const
{return _Con.front();
}
size_t size()const
{return _Con.size();
}
bool empty()const
{return _Con.empty();
}
private:
Container _Con;
};
};
那么經(jīng)過上面的棧和隊列的學習之后，我們對于容器適配器的
迭代器模式：不暴露底層細節(jié)，封裝過后，提供統(tǒng)一的方式來訪問容器
適配器模式：用已有的東西，封裝轉(zhuǎn)換出想要的東西
這兩句話有了更進一步的理解
我們現(xiàn)在就來進行一下小結(jié)：
三、容器適配器 1、什么是容器適配器呢？適配器是一種設(shè)計模式(設(shè)計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié))，該種模式是將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口
類似于上圖
雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque，比如：
那么，也就得出來了，上面為什么模擬實現(xiàn)stack和queue的時候，采用deque也可以了，這就是因為STL中，棧和隊列的底層就是deque
現(xiàn)在我們就來了解什么是deque
四、deque我們指定vector和list各有優(yōu)缺點：
vector：1、頭部中部插入刪除效率低；2、要擴容
list：1、不支持隨機訪問；2、cpu高速緩存命中率低
那么，有沒有一種完美的容器，將兩者的優(yōu)點結(jié)合，缺點抹除了呢？
答案是有的。就是deque。但是，既然你是將vector和list相結(jié)合，并且抹除了兩者的缺點，那么就導致了deque缺點少，但是優(yōu)點不明顯
deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高
注意：這里的deque和queue完全是兩個東西，deque并沒有隊列的“先進先出”的特定，不要混淆。
我們使用deque的場景是比較少的。在下面的小結(jié)我會提出上面場景使用deque合適
deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：
雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護其“整體連續(xù)”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計就比較復雜，如下圖所示：
小問題：那deque是如何借助其迭代器維護其假想連續(xù)的結(jié)構(gòu)呢？
deque是采用多個buffer數(shù)組+中控數(shù)組（指針數(shù)組）組成的
buffer數(shù)組里面存放這我們的數(shù)據(jù)，而中控數(shù)組里面存放的是指針，這些指針都指向一個buffer數(shù)組。我們第一次插入數(shù)據(jù)的時候，開辟一個buffer數(shù)組，然后中控數(shù)組的指針（第一次指向開辟數(shù)組的指針并不是在中控數(shù)組的開始位置，而是在中間位置，這是為了頭插更方便）指向該buffer數(shù)組，一直在該數(shù)組進行尾插，等到數(shù)組滿了，就進行擴容，開辟第二個buffer數(shù)組，然后由上一個指針在中控數(shù)組的下一個位置的指針指向新開辟的buffer數(shù)組，尾插以此類推
頭插數(shù)據(jù)在開辟號buffer數(shù)組之后，就通過第一次中控數(shù)組出現(xiàn)的指針前一個位置，的指針指向
deque隨機訪問下標：
我們的buffer數(shù)組大小是固定的，所以我們可以先用下標/buffer數(shù)組大小，找到我們要訪問的數(shù)據(jù)在第幾個buffer數(shù)組里面；再通過下標%buffer數(shù)組大小，算出來我們要訪問的數(shù)據(jù)，位于改buffer數(shù)組中的第幾個位置
可以看出來deque的下標隨機訪問是很麻煩的，而且還沒有vector快。這也就是我們說的，deuqe沒有了vector和list的缺點，但是它的優(yōu)點不突出
3、deque的缺陷與vector比較，deque的優(yōu)勢是：
頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的
與list比較：
其底層是連續(xù)空間，空間利用率比較高，不需要存儲額外字段
但是，deque有一個致命缺陷：
小結(jié)不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結(jié)構(gòu)時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)
所以，在一下場景有利于我們使用deque：
5、為何選擇deque作為stack和queue的底層默認容器1、中部插入刪除操作少，頭尾刪除插入操作多
2、偶爾進行下標隨機訪問
學習了上面的知識，相信我們的理解與答案相差無幾
stack是一種后進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：
- stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
- 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數(shù)據(jù))；queue中的元素增長 時，deque不僅效率高，而且內(nèi)存使用率高
結(jié)合了deque的優(yōu)點，而完美的避開了其缺陷
優(yōu)先級隊列文檔
總結(jié)：
優(yōu)先隊列是一種容器適配器，根據(jù)嚴格的弱排序標準，它的第一個元素總是它所包含的元素中大的
此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索大堆元素(優(yōu)先隊列中位于頂部的元素)。
優(yōu)先隊列被實現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先隊列的頂部。
底層容器可以是任何標準容器類模板，也可以是其他特定設(shè)計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：
empty()：檢測容器是否為空
size()：返回容器中有效元素個數(shù)
front()：返回容器中第一個元素的引用
push_back()：在容器尾部插入元素
pop_back()：刪除容器尾部元素
標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。
需要支持隨機訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時自動調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。
優(yōu)先級隊列默認使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。
注意：默認情況下priority_queue是大堆。
| 函數(shù)聲明 | 作用 |
|---|---|
| priority_queue()/priority_queue(frist,last) | 創(chuàng)建空的優(yōu)先級隊列 |
| empty（） | 判斷優(yōu)先級隊列是否為空 |
| top（） | 返回優(yōu)先級隊列大/最小的數(shù)據(jù)，也就是堆頂數(shù)據(jù) |
| push（val) | 在優(yōu)先級隊列插入val |
| pop（） | 刪除優(yōu)先級隊列大/最小的數(shù)據(jù)，也就是堆頂數(shù)據(jù) |
這些接口現(xiàn)在來看就是小兒科了
2、priority_queue的模擬實現(xiàn)#pragma once
namespace bzh
{template>class priority_queue
{public:
void adjust_up(int child)//向上調(diào)整
{ while (child >0)
{ int person = (child - 1) / 2;
if (_con[person]< _con[child])
{swap(_con[person], _con[child]);
child = person;
person = (child - 1) / 2;
}
else
{break;
}
}
}
void adjust_down(int person)//向下調(diào)整
{ int child = person * 2 + 1;
if (child + 1< _con.size() && _con[child]< _con[child + 1])
{ child++;
}
while (child< _con.size())
{ if (_con[person]< _con[child])
{swap(_con[person], _con[child]);
person = child;
child = person * 2 + 1;
}
else
{break;
}
}
}
priority_queue()//默認構(gòu)造函數(shù)
{}
templatepriority_queue(Tua first, Tua last)//這里相當于傳參的構(gòu)造函數(shù)，所以我們要寫一個無參的默認構(gòu)造函數(shù)
:_con(first, last)
{ for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{ adjust_down(i);
}
}
void push(const T& val)
{ _con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{ swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()const
{ return _con[0];
}
bool empty()const
{ return _con.empty();
}
size_t size()const
{ return _con.size();
}
private:
Contianor _con;
};
}; 
仿函數(shù)的本質(zhì)是一個類，它重載了一個運算符——（），使用時的函數(shù)名就是operator（）
舉例：
比較大小的兩個仿函數(shù)
namespace abcd
{templateclass less
{public:
bool operator()(const T& num1, const T& num2)
{ return num1< num2;
}
};
templateclass greater
{public:
bool operator()(const T& num1, const T& num2)
{ return num1 >num2;
}
};
} class Date
{public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{return (_year< d._year) ||
(_year == d._year && _month< d._month) ||
(_year == d._year && _month == d._month && _day< d._day);
}
bool operator>(const Date& d)const
{ return (_year >d._year) ||
(_year == d._year && _month >d._month) ||
(_year == d._year && _month == d._month && _day >d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{ _cout<< d._year<< "-"<< d._month<< "-"<< d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue()
{// 大堆，需要用戶在自定義類型中提供<的重載
priority_queueq1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout<< q1.top()<< endl;
// 如果要創(chuàng)建小堆，需要用戶提供>的重載
priority_queue, greater>q2;
//這里如果是指針類型，比較的時候現(xiàn)有的仿函數(shù)比較的是指針的地址
q2.push(new Date(2018, 10, 29));
q2.push(new Date(2018, 10, 28));
q2.push(new Date(2018, 10, 30));
cout<< *q2.top()<< endl;
priority_queue, less>q3;
q3.push(new Date(2018, 10, 29));
q3.push(new Date(2018, 10, 28));
q3.push(new Date(2018, 10, 30));
cout<< *q3.top()<< endl;
}
我們自己寫一個比較仿函數(shù)
class Less
{public:
bool operator()(const Date* num1, const Date* num2)
{return *num1< *num2;
}
};
class Greater
{public:
bool operator()(const Date* num1, const Date* num2)
{return *num1 >*num2;
}
};
我們前面也接觸了反向迭代器，正向迭代器++是向后面走；而反向迭代器++是往前面走
下面是反向迭代器的實現(xiàn)代碼：
#pragma once
templateclass ReverseIterator
{public:
//T,T&,T*
//const T,const T&,const T*
typedef ReverseIteratorself;
ReverseIterator(Iterator s)
:it(s)
{}
Ptr operator->()//返回數(shù)據(jù)的地址
{return &(operator*());
}
Ref operator*()//返回數(shù)據(jù)
{Iterator tmp = it;
return *(--tmp);
}
self& operator++()
{--it;
return *this;
}
self& operator--()
{++it;
return *this;
}
bool operator==(const self& s)const
{return it == s.it;
}
bool operator!=(const self& s)const
{return !operator==(s);
}
private:
Iterator it;
};
我們可以在list和vector里面引入頭文件，然后實現(xiàn)反向迭代器：
typedef ReverseIteratorreverse_iterator;
typedef ReverseIteratorconst_reverse_iterator;
reverse_iterator rbegin()
{ return reverse_iterator(end());
}
reverse_iterator rend()
{ return reverse_iterator(begin());
} 你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
