? 對于棧和隊列我們是不陌生的，在數(shù)據(jù)結構階段已經(jīng)學習過，記得當時我們還是用c語言將它一步一步造出來，因為壓棧與出棧正好滿足數(shù)組的尾插與頭刪，數(shù)組的代價是及小的。對于隊列是頭出隊列，尾插。所以就棧的實現(xiàn)就用的數(shù)組，隊列實現(xiàn)就用鏈表。在c++中呢，vector和list就完美解決。priority_queue叫優(yōu)先級隊列，實質就是大小堆，堆的實現(xiàn)就是數(shù)組。
成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)站建設、成都網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務蘭考,10余年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:13518219792在很多時候stack，queue，priority_queue他們都叫做適配器，這里簡單的提一下，它們就好比是農夫山泉，不生產水，是大自然的搬運工。也就意味著它“不生產代碼,只是代碼的搬運工”。下面我們通過底層代碼的實現(xiàn)，就能看出這一特性。
目錄
前言
一、stack-棧
1.1?stack的使用
1.2stack的模擬實現(xiàn)
二、queue-隊列
2.1queue的使用
2.2queue的模擬實現(xiàn)
2.3容器適配器
三、deque
3.2deque的原理介紹
3.3deque--插入
3.4deque的接口
四、priority_queue-優(yōu)先級隊列
4.1priority_queue的使用
4.2模擬實現(xiàn)
?編輯
五、仿函數(shù)/函數(shù)對象
5.1仿函數(shù)的實現(xiàn)
5.2仿函數(shù)的使用
5.2仿函數(shù)的用法（進階版）
stack是一種容器適配器，專門用在具有后進先出操作的上下文環(huán)境中，其刪除只能從容器的一端進行元素的插入與提取操作。
下面這些接口的使用我相信大家已經(jīng)是游刃有余了，這里就不用過多演示，若不熟悉查文檔即可。
| 函數(shù)說明 | 接口說明 |
| stack() | 構造空的棧 |
| empty() | 檢測stack是否為空 |
| size() | 返回stack中元素的個數(shù) |
| top() | 返回棧頂元素的引用 |
| push() | 將元素val壓入stack中 |
| pop() | 將stack中尾部的元素彈出 |
重慶分公司
重慶分公司
void test_stack()
{
stacks;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout<< s.top()<< " ";
s.pop();
}
} 對stack的實現(xiàn)，現(xiàn)在只關注它的實現(xiàn)全是調用。關于deque，Container下面我們就會進行探究。
#pragma once
#include#includenamespace qhx
{
template>class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
隊列也是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
隊列的接口其實與棧的接口基本一樣，而且使用方法也是一樣。
| 函數(shù)聲明 | 接口說明 |
| queue() | 構造空的隊列 |
| empty() | 檢測隊列是否為空，是返回true，否則返回false |
| size() | 返回隊列中有效元素的個數(shù) |
| front() | 返回隊頭元素的引用 |
| back() | 返回隊尾元素的引用 |
| push() | 在隊尾將元素val入隊列 |
| pop() | 將隊頭元素出隊列 |
void test_queue()
{
queueq;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout<< q.front()<< " ";
q.pop();
}
cout<< endl;
} #pragma once
#include#includenamespace qhx
{
template>class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
queue的模擬實現(xiàn)也是非常簡單的，都是復用其他人代碼。棧和隊列的實現(xiàn)中，我們發(fā)現(xiàn)都有class Container = deque
在queue和stack中都有這樣一段話。
Queue：
queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
翻譯：隊列是一種容器適配器，專門設計用于在 FIFO 上下文（先進先出）中運行，其中元素插入容器的一端并從另一端提取。
Stacks：
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
翻譯：
隊列是一種容器適配器，專門設計用于在 FIFO 上下文（先進先出）中運行，其中元素插入容器的一端并從另一端提取。
class Container = deque
適配器是一種設計模式(設計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設計經(jīng)驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。
設計模式的使用將提高軟件系統(tǒng)的開發(fā)效率和軟件質量，節(jié)省開發(fā)成本。有助于初學者深入理解面向對象思想，設計模式使設計方案更加靈活，方便后期維護修改。
在stack，queue中 deque
在容器適配器為什么會選擇deque，那么就必須得從vector，list的優(yōu)缺點說起
3.1vector，list的優(yōu)缺點
vector：
stack可以隨機訪問，但是頭部中部插入刪除效率低，并且還需要擴容
list：
雖然queue在任何地方插入刪除效率高，但是不支持隨機訪問，CPU高速緩存命中率低
對于deque就完美兼容vector，list的優(yōu)點。所以對于接口選擇就是deque。
3.2deque的原理介紹deque文檔
deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結構，雙開口的含義是：可以在頭尾兩端進行插入和 刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
這個是deque一段的buffer數(shù)組，所以deque并不是真正連續(xù)的空間，它是由一段一段這樣的buffer數(shù)組鏈接而成，一段一段的buffer數(shù)組被放在中控，這個中控就是一個指針數(shù)組，實際上deque類似于一個動態(tài)的二維數(shù)組， 如圖：
這里的緩沖區(qū)就是buffer數(shù)組，用于存放數(shù)據(jù)。map就是中控器，就是存放指針。當map空間不夠后，會再開辟一個中控-map。
插入操作--頭插
插入操作--尾插?
查找：即相當于二維數(shù)組一樣，先找map中的地址（第一層），然后在找buffer（第二層）
缺點：
那么我們發(fā)現(xiàn)它下標訪問有一定的消耗，沒有vector快。當我們中間插入時候，它的中間插入的時候需要挪動數(shù)據(jù)，與list相比也是有消耗的。
deque不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到 某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結構時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作 為stack和queue的底層數(shù)據(jù)結構。
我們通過發(fā)現(xiàn)deque其實是沒有想象中那樣完美的，它與vector和list相比是不夠極致的。vector是呂布，list是諸葛亮，那么deque就是魏延。所以更多的時候我們更需要極致。
deque的底層實現(xiàn)是比較復雜的，不僅僅是上訴簡單兩句的問題。
根據(jù)上圖，對于deque的維護是通過兩個迭代器，start和finsh。因為daque是作為stack和queue的底層默認容器，一般來說deque是不需要進行中間插入的，那么start和finsh就很好的處理頭插和尾插。它通過frist和last指向頭尾，頭插通過start的frist，如果滿了node鏈接map新開辟buffer的指針位置。尾插通過finish的last控制。如果top()和back(),即通過start的cur和finish的cur控制。、
3.4deque的接口deque文檔的接口
通過stack，queue的接口與deque的接口對比，發(fā)現(xiàn)直接調用deque是非常適合充當stack，queue的默認容器。stack，queue就是直接調用deque的接口。
四、priority_queue-優(yōu)先級隊列優(yōu)先隊列是一種容器適配器，而它實質就是堆。是否還記得堆是完全二叉樹中用數(shù)組實現(xiàn)的，因為數(shù)組正好滿足堆下標隨機存取的需求，標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。相對deque，vector更加極致。priority_queue是默認大根堆。
priority_queue的使用來說也是比較簡單的，接口也比較少。
| 函數(shù)聲明 | 接口說明 |
| priority_queue()/priority_queue(?rst, last) | 構造一個空的優(yōu)先級隊列 |
| empty( ) | 檢測優(yōu)先級隊列是否為空，是返回true，否則返回 false |
| top( ) | 返回優(yōu)先級隊列中大(最小元素)，即堆頂元素 |
| push(x) | 在優(yōu)先級隊列中插入元素x |
| pop() | 刪除優(yōu)先級隊列中大(最小)元素，即堆頂元素 |
對于priority_queue的頭文件，我們通過手冊發(fā)現(xiàn)，priority_queue與queue都是一個頭文件。
接口演示：
//默認大根堆
void test()
{
priority_queuep;
p.push(7);
p.push(1);
p.push(9);
p.push(2);
p.push(3);
p.push(4);
while (!p.empty())
{
cout<< p.top()<< " ";
p.pop();
}
} 結果：9 7 4 3 2 1
小根堆 --greater
void test()
{
priority_queue, greater>p;
p.push(7);
p.push(1);
p.push(9);
p.push(2);
p.push(3);
p.push(4);
while (!p.empty())
{
cout<< p.top()<< " ";
p.pop();
}
} 4.2模擬實現(xiàn)結果：1 2 3?4 7 9
#pragma once
namespace qhx
{
template>class priority_queue
{
public:
templatepriority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
//建堆-推薦向下調整建堆，時間復雜度更小
for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; --i)//
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child >0)
{
if (_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);
adjust_up(_con.size() - 1);
}
void adjust_down(size_t parent)
{
size_t michild = parent * 2 + 1;
while (michild< _con.size())
{
if (michild< _con.size() && _con[michild]>_con[michild + 1])
{
michild++;
}
if ( _con[michild]>]< _con[parent])
{
swap(_con[michild], _con[parent]);
parent = michild;
michild = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con(_con.size(-1)));
_con.pop_back();
adjust_down(0);
}
const T&top()const
{
return _con[0];
}
const empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
}; 如果對向上/向下調整忘記了的，就可以看下面圖片回憶。
向上調整?
向下調整
仿函數(shù)(functor)，就是使一個類的使用看上去像一個函數(shù)。其實現(xiàn)就是類中實現(xiàn)一個operator()，這個類就有了類似函數(shù)的行為，就是一個仿函數(shù)類了。
這里是實現(xiàn)的比較大小的仿函數(shù)
#includeusing namespace std;
//仿函數(shù)/函數(shù)對象
namespace qhx
{
templateclass less
{
public:
bool operator()(const T& x, const T& y)
{
return x< y;
}
};
templateclass greater
{
public:
bool operator()(const T& x, const T& y)
{
return x>y;
}
};
};
int main()
{
qhx::lesslessFunc;
if (lessFunc(3, 2))
cout<< "yes"<< endl;
else
cout<< "no"<< endl;
return 0;
} 冒泡排序
templatevoid BubbleSort(T* a, int n)
{
for (int i = 0; i< n; i++)
{
int flag = 0;
for (int j = 1; j< n - i; j++)
{
if (a[j - 1] >a[j])
swap(&a[j - 1], &a[j]);
flag = 1;
}
if (flag == 0)
break;
}
} 在C語言時期，冒泡函數(shù)進行比較的時候，是需要進入冒泡函數(shù)內部改變">","<"?；蛘呤峭ㄟ^函數(shù)指針的方式，在多增加一個函數(shù)參數(shù)。
方法一：
if (a[j - 1] >a[j])????????//改變其大與小
對于封裝的好的函數(shù)來說，這樣對使用者是非常不友好的，那么就可以通過接口的方式，增加函數(shù)指針。
方法二：
void BubbleSort(T* a, int n，bool（*pcom）(int,int))
方法二的話，這個方法是比較搓的，使用的函數(shù)時需要傳太多變量，閱讀性也不夠強。那么c++中函數(shù)模板就起到了重要的作用了。我們可以增加一個模板參數(shù)，再增加給函數(shù)的參數(shù)，通過類型的對象去比較，可以想函數(shù)一樣去是使用。
template// 冒泡排序
void BubbleSort(T* a, int n,compaer com)
{
for (int i = 0; i< n; i++)
{
int flag = 0;
for (int j = 1; j< n - i; j++)
{
//if (a[j - 1] >a[j])
if (com(a[j - 1] , a[j]))
swap(a[j - 1], a[j]);
flag = 1;
}
if (flag == 0)
break;
}
}
void test_less()
{
qhx::lesslessFunc;
if (lessFunc(3, 2))
cout<< "yes"<< endl;
else
cout<< "no"<< endl;
}
void test_BubbleSort()
{
qhx::lesslessFunc;
int arr[] = { 1, 2, 4, 9, 8, 3, 6, 7 };
//BubbleSort(arr, sizeof(arr) / sizeof(arr[0]),lessFunc);
BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);
for (auto e : arr)
{
cout<< e<< " ";
}
}
int main()
{
test_BubbleSort();
return 0;
} 運行結果：9 8 7 6 4 3 2 1
這里的less是根據(jù)優(yōu)先級隊列來定義的，這里是降序，greater就是升序。
注意：這里模板參數(shù)是類，函數(shù)調用類模板增加的代碼內存時不多的。例如上述只增加1個字節(jié)。
5.2仿函數(shù)的用法（進階版）這里是比較Daet--自定義類型的大小。我們有Date類型比較大小的方式后，但是對于Date*的比較是沒有的，故此，我們創(chuàng)建一個struct（類-默認公共類），然后通過函數(shù)模板的調用，實現(xiàn)了比較非自定義變量指針的大小。
#include#include#includeusing namespace std;
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;
};
struct PDateLess
{
bool operator()(const Date* d1, const Date* d2)
{
return *d1< *d2;
}
};
struct PDateGreater
{
bool operator()(const Date* d1, const Date* d2)
{
return *d1 >*d2;
}
};
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;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout<< q2.top()<< endl;
// 大堆
priority_queue, PDateLess>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;
// 小堆
priority_queue, PDateGreater>q4;
q4.push(new Date(2018, 10, 29));
q4.push(new Date(2018, 10, 28));
q4.push(new Date(2018, 10, 30));
cout<< *q4.top()<< endl;
}
int main()
{
TestPriorityQueue();
return 0;
} 你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
