一、適配器模式
設(shè)計模式
設(shè)計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié),是解決特定問題的一系列套路。它不是語法規(guī)定，而是一套用來提高代碼可用性，可維護性，可讀性，穩(wěn)健性以及安全性的解決方案
迭代器模式
迭代器模式（Iterator Pattern) ：提供一種方法來訪問聚合對象，而不用暴露這個對象的內(nèi)部表示，其別名為游標(Cursor)。迭代器模式是一種對象行為型模式，使得在不暴露底層實現(xiàn)細節(jié)的情況下，封裝后讓我們使用相同的方式來訪問不同的容器
適配器模式
Adapter（適配器模式）屬于結(jié)構(gòu)型模式，結(jié)構(gòu)性模式關(guān)注的是如何組合類與對象，將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口，以獲得更大的結(jié)構(gòu)，即將已有的東西轉(zhuǎn)換成我們想要的東西
二、stack
1.stack的介紹
我們和之前一樣，參照 cplusplus 網(wǎng)站進行學習：stack文檔介紹
和vector、list不同，棧是一種受特殊限制的線性表，需要保證FILO(先進后出)的特性，stack不提供迭代器，所以stack不是迭代器模式，而是一種容器適配器：
stack和queue都采用deque容器作為默認的適配器，我們stack,queue也可以使用vector，list作為適配器.
【總結(jié)】
1.stack是一種容器適配器，專門用在具有后進先出操作的上下文環(huán)境中，其刪除只能從容器的一端進行元素的插入與提取操作
2.stack是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出
3.stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作
empty：判空操作
back：獲取尾部元素操作
push_back：尾部插入元素操作
push_back：尾部插入元素操作
4.標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque
2.stack的使用
| 函數(shù)說明 | 接口說明 |
|---|---|
| stack() | 構(gòu)造空的棧 |
| empty() | 檢測stack是否為空 |
| size() | 返回stack中元素的個數(shù) |
| top() | 返回棧頂元素的引用 |
| push() | 將元素val壓入stack中 |
| pop() | 將stack中尾部的元素彈出 |
void stack_test()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
3.stack的模擬實現(xiàn)
我們在了解適配器模式之后，我們可以將適配器作為類的第二個模板參數(shù)，然后通過傳遞不同的適配容器來進行適配,我們可以使用vector、list作為stack的適配容器，但是出于隨機訪問和CPU高速緩存命中率的考慮 ，我們最終選擇vector作為stack的適配容器，我們可以將vector作為缺省參數(shù)，以后定義時我們就不需要顯示傳遞vector了
// stack.h
template<class T,class Container=vector<T>>
class stack
{
// ...
};
// test.cpp
void stack_test()
{
// 默認使用vector作為適配容器
stack<int> st1;
// 使用list作為適配容器
stack<int, list<int>> st2;
}
stack.h
#pragma once
#include <vector>
#include <list>
#include <queue>
namespace hdp
{
//template<class T, class Container = vector<T>>
template<class T, class Container = deque<T>>
class stack
{
public:
// 我們不需要顯示寫構(gòu)造和析構(gòu)函數(shù)，編譯器對于自定義類型會去調(diào)用其自身的默認構(gòu)造
// 入棧
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();
}
// 獲取元素個數(shù)
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
test.cpp
#include <iostream>
#include <queue>
#include "stack.h"
using namespace std;
// 測試棧
void stack_test()
{
hdp::stack<int, deque<int>> st;
// 入棧
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
// 獲取元素個數(shù)
cout << st.size() << endl;
while (!st.empty())
{
// 獲取棧頂元素
cout << st.top() << " ";
// 出棧
st.pop();
}
cout << endl;
}
int main()
{
stack_test();
return 0;
}
4.stack的相關(guān)OJ題目
LeetCode 155.最小棧
題目描述
設(shè)計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
實現(xiàn) MinStack 類:
- MinStack() 初始化堆棧對象。
- void push(int val) 將元素val推入堆棧。
- void pop() 刪除堆棧頂部的元素。
- int top() 獲取堆棧頂部的元素。
- int getMin() 獲取堆棧中的最小元素。
示例：
輸入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]輸出：
[null,null,null,null,-3,null,0,-2]解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路：
我們可以使用一個minST來保存最小值，當插入的元素小于minST棧頂元素的時候就將該元素插入到minST中，如果該元素大于或者等于minST棧頂元素的時候就向minST中插入一個與棧頂元素大小相同的值，此時最小值就是minST棧頂?shù)脑?，st pop的時候minST也同時進程pop
st:[8,9,9,7,2,9]
minST:[8,8,8,7,2,2]
// pop
st:[8,9,9,7,2]
minST:[8,8,8,7,2]
min = 2
我們對上面的思路可以進行優(yōu)化，因為它的空間復雜度為O(N),需要一個同等大小的棧來保存數(shù)據(jù)，優(yōu)化思路為：我們不需要每次都向minST插入元素，只有當插入的元素小于或者等于minST棧頂?shù)?元素的時候才插入，pop數(shù)據(jù)的時候只有當pop的值等于minST棧頂元素的時候才同時進行pop
st:[8,9,9,7,2,9]
minST:[8,7,2]
// pop
st:[8,9,9,7,2]
minST:[8,7,2]
min = 2
// pop
st:[8,9,9,7]
minST:[8,7]
min = 7
我們需要注意的是，當插入的元素與minST棧頂元素相等的時候也要插入，這是為了避免后續(xù)插入的元素中有等于當前minST棧頂?shù)脑兀@樣pop元素之后會導致minST棧頂元素可能就不再是最小值了
代碼實現(xiàn)：
class MinStack {
public:
// 可以為空，因為初始化類別會進行初始化
MinStack()
{}
void push(int val)
{
// minST為空或者插入的元素小于或者等于minST棧頂元素的時候插入
if(minst.empty() || val<=minst.top())
minst.push(val);
st.push(val);
}
void pop()
{
// 當pop的數(shù)據(jù)和minST棧頂元素相同的時候才pop
if(minst.top()==st.top())
minst.pop();
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return minst.top();
}
private:
stack<int> st;
stack<int> minst;
};
牛客 JZ31 棧的壓入彈出序列
題目描述
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。
1.0<=pushV.length == popV.length <=1000
2.-1000<=pushV[i]<=1000
3.pushV 的所有數(shù)字均不相同
示例
輸入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
說明：
可以通過push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
這樣的順序得到[4,5,3,2,1]這個序列，返回true
思路：
這道題我們只需要模擬出棧的順序即可，將pushV中的元素入棧，入棧的元素和popV的元素進行比較，如果相同，則說明當前元素此時出棧，所以棧頂?shù)脑鼐统鰲＃绻幌嗟萷ushV就繼續(xù)入棧，當全部入棧之后，如果pushV中入棧的元素全部被pop(pushV為空)，就說明出棧順序是正確的
代碼實現(xiàn)：
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
//入棧和出棧的元素個數(shù)必須相同
if(pushV.size() != popV.size())
return false;
stack<int> st;
size_t popi=0;
for(auto e:pushV)
{
st.push(e);
// 跟出棧序列比較，相等就出棧 因為可能多個元素持續(xù)出棧，所以是while不是if
while(!st.empty()&&st.top()==popV[i])
{
st.pop();
++popi;
}
}
return st.empty();
}
};
LeetCode 150.逆波蘭式求值
題目描述
給你一個字符串數(shù)組 tokens ，表示一個根據(jù) 逆波蘭表示法 表示的算術(shù)表達式。
請你計算該表達式。返回一個表示表達式值的整數(shù)
注意：
- 有效的算符為
'+'、'-'、'*'和'/' - 每個操作數(shù)（運算對象）都可以是一個整數(shù)或者另一個表達式
- 兩個整數(shù)之間的除法總是 向零截斷
- 表達式中不含除零運算
- 入是一個根據(jù)逆波蘭表示法表示的算術(shù)表達式
- 答案及所有中間計算結(jié)果可以用 32 位 整數(shù)表示
示例
輸入：tokens = [“2”,“1”,“+”,“3”,“*”]
輸出：9
解釋：該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：((2 + 1) * 3) = 9
思路：
對于這道題，我們首先需要明白計算機對逆波蘭表達式(后綴表達式)的計算方法：用棧來存儲數(shù)據(jù)，從左到右遍歷表達式，遇到操作數(shù)就入棧，遇到操作符就取出棧的兩個數(shù)據(jù)進行運算，注意第一次棧頂?shù)脑貫橛也僮鲾?shù)，第二次取的棧頂?shù)臄?shù)據(jù)為左操作數(shù)，然后將運算的結(jié)果入棧，然后繼續(xù)往后進行遍歷，直到將表達式遍歷完畢
代碼實現(xiàn)：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto str:tokens)
{
if(str=="+"||str=="-"||str=="*"||str=="/")
{
int right=st.top();
st.pop();
int left=st.top();
st.pop();
if(str=="+")
st.push(left+right);
if(str=="-")
st.push(left-right);
if(str=="*")
st.push(left*right);
if(str=="/")
st.push(left/right);
}
else
{
st.push(stoi(str));
}
}
return st.top();
}
};
知識拓展–中綴表達式轉(zhuǎn)后綴表達式
中綴表達式計算我們生活中所見到的表達式，但是計算機更容易計算后綴表達式，所以計算機在計算的時候需要先將中綴表達式轉(zhuǎn)為后綴表達式，再根據(jù)后綴表達式來進行求值
中綴表達式轉(zhuǎn)后綴表達式規(guī)則如下：
1.遇到操作數(shù)直接輸出
2.使用棧來存儲操作符，遇到操作符如果棧為空就直接入棧，如果棧不為空，則與棧頂?shù)牟僮鞣M行比較，如果當前操作符優(yōu)先級比棧頂?shù)膬?yōu)先級高，則入棧，如果低于或者等于，則棧頂?shù)牟僮鞣鰲?，當前操作符入?/p>
舉例說明：
中綴表達式：1+2*3/4-5
// 遇到操作數(shù)直接輸出
st:[] 后綴表達式 1
// 遇到操作符且棧為空，將操作符入棧
st:[+] 后綴表達式 1
// 操作數(shù)直接輸出，*比+的優(yōu)先級高，所以直接入棧
st:[+ *] 后綴表達式 1 2
// 操作數(shù)直接輸出，/和*的優(yōu)先級一樣高，*輸出，/入棧
st:[+ /] 后綴表達式 1 2 3 *
// -比/的優(yōu)先級低，所以/輸出，-入棧
st:[+ -] 后綴表達式 1 2 3 * 4 /
//+ 和 - 的優(yōu)先級相等，所以+輸出
st:[-] 后綴表達式 1 2 3 * 4 / +
// 操作數(shù)輸出，表達式遍歷完畢，操作符全部出棧
st:[] 后綴表達式 1 2 3 * 4 / + 5 -
LeetCode 232.用棧實現(xiàn)隊列
題目描述
設(shè)計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
實現(xiàn) MinStack 類:
-
MinStack()初始化堆棧對象。 -
void push(int val)將元素val推入堆棧。 -
void pop()刪除堆棧頂部的元素。 -
int top()獲取堆棧頂部的元素。 -
int getMin()獲取堆棧中的最小元素。
示例
輸入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]輸出：
[null,null,null,null,-3,null,0,-2]解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路：
由于棧只能在尾部插入數(shù)據(jù)和刪除數(shù)據(jù)，而隊列是在尾部插入數(shù)據(jù)，在頭部刪除數(shù)據(jù)，所以我們可以使用兩個棧，一個專門用來插入數(shù)據(jù)，一個用來專門出數(shù)據(jù)：
pushST:專門用來插入數(shù)據(jù)，當有元素入隊列時直接插入pushST中
popST:專門用來出數(shù)據(jù)，當數(shù)據(jù)出隊列時，檢查popST是否為空，如果為空，將pushST中的全部數(shù)據(jù)全部取出插入到popST中–因為棧是先進后出的，所以當我們將pushST中的數(shù)據(jù)取出插入到popST后，原本位于棧底的數(shù)據(jù)就會位于棧頂，此時popST的出棧順序就和隊列的出隊列順序相同了
代碼實現(xiàn)：
class MyQueue {
public:
MyQueue()
{}
// 檢查popST是否為空，為空就將pushST的元素全部移動到popST中
void move()
{
if(popST.empty())
{
while(!pushST.empty())
{
popST.push(pushST.top());
pushST.pop();
}
}
}
// 直接插入到pushST中
void push(int x) {
pushST.push(x);
}
int pop() {
// pop之前先檢查是否需要移動元素
move();
int x=popST.top();
popST.pop();
return x;
}
int peek() {
move();
return popST.top();
}
bool empty() {
// 兩個棧均為空則為空隊列
return pushST.empty()&&popST.empty();
}
private:
stack<int> pushST;
stack<int> popST;
};
【注意】
1.我們定義的pushST 和 popST是自定義類型，我們不寫構(gòu)造函數(shù)編譯器會調(diào)用他們自身的構(gòu)造函數(shù)，走初始化列表進行初始化，所以 MyQueue()函數(shù)里面可以不用寫任何東西，此外，如果我們連 MyQueue()都不寫，此時，編譯器會自動生成一個無參的默認構(gòu)造函數(shù)，它對于自定義類型同樣也是自定義類型的默認構(gòu)造，所以 MyQueue()不寫或者 MyQueue()函數(shù)里面不寫都是可以的
2.題目的接口中，peek,pop都需要先判斷popST是否為空，如果為空就需要將pushST中的元素移動到popST中，為了避免代碼的冗余，所以我們可以單獨寫一個函數(shù)來完成
三、queue
1.queue的介紹
queue和stack一樣，也是一種容器適配器，不提供迭代器
cplusplus網(wǎng)址：queue文檔介紹
【總結(jié)】
1.隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素
2.隊列作為容器適配器實現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊尾入隊列，從隊頭出隊列
3.底層容器可以是標準容器類模板之一，也可以是其他專門設(shè)計的容器類。該底層容器應(yīng)至少支持以下操作:
empty：檢測隊列是否為空
size：返回隊列中有效元素的個數(shù)
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列
4.標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque
2.queue的使用
| 函數(shù)聲明 | 接口說明 |
|---|---|
| queue() | 構(gòu)造空的隊列 |
| empty() | 檢測隊列是否為空，是返回true，否則返回false |
| size() | 返回隊列中有效元素的個數(shù) |
| front() | 返回隊頭元素的引用 |
| back() | 返回隊尾元素的引用 |
| push() | 在隊尾將元素val入隊列 |
| pop() | 將隊頭元素出隊列 |
void queue_test()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
3.queue的模擬實現(xiàn)
queue.h
#pragma once
#include <vector>
#include <list>
#include <queue>
namespace hdp
{
//template<class T, class Container = list<T>>
template<class T, class Container = deque<T>>
class queue
{
public:
// 入隊列
void push(const T& x)
{
_con.push_back(x);
}
// 出隊列
void pop()
{
_con.pop_front();
}
// 獲取隊頭元素
const T& top()
{
return _con.front();
}
// 判空
bool empty()
{
return _con.empty();
}
// 獲取元素個數(shù)
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
test.cpp
#include <iostream>
#include <queue>
#include "queue.h"
using namespace std;
// 測試隊列
void queue_test()
{
hdp::queue<int, deque<int>> q;
// 入隊列
q.push(1);
q.push(2);
q.push(3);
q.push(4);
// 獲取元素個數(shù)
cout << q.size() << endl;
while (!q.empty())
{
// 獲取隊頭元素
cout << q.top() << " ";
// 出隊列
q.pop();
}
cout << endl;
}
int main()
{
queue_test();
return 0;
}
4.queue的相關(guān)OJ題目
leetCode 255.用隊列實現(xiàn)棧
題目描述：
請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
實現(xiàn) MyStack 類：
-
void push(int x)將元素 x 壓入棧頂 -
int pop()移除并返回棧頂元素 -
int top()返回棧頂元素 - boolean empty()
如果棧是空的，返回true；否則，返回false
注意：
- 你只能使用隊列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty這些操作 - 你所使用的語言也許不支持隊列。 你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可
示例：
輸入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
思路
1.入數(shù)據(jù)：定義兩個隊列q1和q2，最開始入棧時隨便將數(shù)據(jù)插入哪個隊列，第二次及以后次插入數(shù)據(jù)時把數(shù)據(jù)插入到非空隊列中
2.出數(shù)據(jù)：由于隊列是先進先出而棧是后進后出，所以隊尾的數(shù)據(jù)就是棧頂?shù)臄?shù)據(jù)，而出棧時我們需要將隊尾前面的數(shù)據(jù)全部挪動到另一個空隊列中，然后刪除隊列中剩余的那個數(shù)據(jù)，這樣就完成了出棧的操作，此時這個隊列就為空了，另一個隊列不為空，下次再出棧的時候就可以把另一個不為空的隊列除隊尾的數(shù)據(jù)全部挪到這個空隊列中，然后再刪除隊尾的數(shù)據(jù)
3.將q1中的數(shù)據(jù)挪到到q2中之后，數(shù)據(jù)的前后順序是不會發(fā)生改變的，即入q1的數(shù)據(jù)為1 2 3 4 5 ，那么將數(shù)據(jù)取出插入到q2后，q2中的數(shù)據(jù)仍然為1 2 3 4 5 ，這是因為隊列入隊順序和出隊順序是一樣的
4.不進行出棧操作時，始終有一個隊列為空，入棧直接插入到非空隊列中，出棧則需要將非空隊列的除隊尾的數(shù)據(jù)全部挪動到另一個空隊列中，然后再刪除非空隊列中剩余的那個數(shù)據(jù)
代碼實現(xiàn)
class MyStack {
public:
// 不用顯式寫，編譯器會調(diào)用queue的默認構(gòu)造
MyStack() {
}
// 在非空隊列中插入數(shù)據(jù)
void push(int x) {
if(!q1.empty())
{
q1.push(x);
}
else
{
q2.push(x);
}
}
// 相當于pop非空隊列隊尾的數(shù)據(jù)
int pop() {
if(q1.empty())
{
//隊列中的數(shù)據(jù)大于1就繼續(xù)挪動
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
// 注意這里用top保存隊尾的數(shù)據(jù)之后需要將那個數(shù)據(jù)pop掉
int top=q2.front();
q2.pop();
return top;
}
else
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
int top=q1.front();
q1.pop();
return top;
}
}
// 非空隊列的隊尾數(shù)據(jù)即為棧頂數(shù)據(jù)
int top() {
if(!q1.empty())
{
return q1.back();
}
else
{
return q2.back();
}
}
// q1和q2均為空，則棧為空
bool empty() {
return q1.empty() && q2.empty();
}
private:
queue<int> q1;
queue<int> q2;
};
四、deque
1.deque的原理介紹
deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
2.deque的底層結(jié)構(gòu)
deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：
【總結(jié)】
1.deque具有多個buffer數(shù)組，每個buffer數(shù)組可以存儲n個數(shù)據(jù)，還具有一個存儲buffer數(shù)組的中控指針數(shù)組，數(shù)組的每個元素都指向一個buffer數(shù)組
2.中控指針數(shù)組的使用，首先讓數(shù)組最中間的元素指向第一個buffer,當?shù)谝粋€buffer數(shù)組存儲滿數(shù)據(jù)之后，再開辟第二個buffer數(shù)組，讓指針數(shù)組的后一個位置或前一個位置指向新開辟的數(shù)組，當一個buffer數(shù)組滿了之后，我們頭插數(shù)據(jù)的時候是在前面開辟一個數(shù)組且數(shù)據(jù)放在前一個buffer數(shù)組的最后一個位置，尾插則是放在后一個buffer數(shù)組的第一個位置
3.關(guān)于deque的擴容機制，當指針數(shù)組滿了指針，會讓中控數(shù)組的容量變?yōu)樵瓉淼亩?，然后將原來中控?shù)組里的數(shù)據(jù)拷貝到新的中控指針數(shù)組中
3.deque的迭代器設(shè)計
雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護其“整體連續(xù)”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計就比較復雜，如下圖所示：
4.deque的缺陷
與vector比較，deque的優(yōu)勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的
與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲額外字段。
我們總結(jié)為具有vector的優(yōu)點：支持隨機訪問，CPU高速緩存命中率較高，尾部插入刪除數(shù)據(jù)的效率高，同時具有l(wèi)ist的優(yōu)點：空間浪費少，頭部插入數(shù)據(jù)的效率高
但是，deque有一些致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結(jié)構(gòu)時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。此外，deque的隨機訪問的效率較低，其訪問過程為–首先通過中控數(shù)組的指針找到對應(yīng)的buffer數(shù)組，然后再找到具體的位置，我們假設(shè)每個buffer中有10個元素，假設(shè)偏移量為i,需要i/10得到位于第幾個buffer數(shù)組，然后再i%10得到buffer數(shù)組中的具體位置。并且，deque在中部插入刪除數(shù)據(jù)的效率也比較低，因為需要挪動數(shù)據(jù)，但不一定后續(xù)buffer數(shù)組中的數(shù)據(jù)全部挪動，可以控制只挪動一部分，即中間插入刪除數(shù)據(jù)的效率高于vector,但低于list
為什么選擇deque作為stack和queue的底層默認容器
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作為其底層容器，主要是因為：
1.stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2.在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數(shù)據(jù))；queue中的元素增長時，deque不僅效率高，而且內(nèi)存使用率高。結(jié)合了deque的優(yōu)點，而完美的避開了其缺陷
deque使用場景文章來源：http://www.zghlxwxcb.cn/news/detail-409719.html
deque適用于需要大量進行頭插和尾部數(shù)據(jù)的插入刪除，偶爾隨機訪問，偶爾進行中部插入刪除的場景，不太適合需要大量進行隨機訪問與中部數(shù)據(jù)插入刪除的場景，還有排序文章來源地址http://www.zghlxwxcb.cn/news/detail-409719.html
到了這里，關(guān)于【C++】容器適配器--stack&queue&deque的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++] STL_priority_queue(優(yōu)先級隊列) 的使用及底層的模擬實現(xiàn)，容器適配器，deque的原理介紹](https://imgs.yssmx.com/Uploads/2024/02/761687-1.png)
