Stack--Queue 棧和隊列

一、Stack--棧

1.1 什么是棧？

堆棧是一種容器適配器，專門設計用于在 LIFO 上下文（后進先出）中運行，其中元素僅從容器的一端插入和提取。?

?第一個模版參數T：元素的類型；第二個模版參數Container：底層容器：分配器的類型。

1.2 棧內部成員函數

stack():創建空的棧

empty()：檢測棧是否為空

如果棧為空，返回true，否則返回false。

int main()
{int sum = 0;stack<int> mystack;for (int i = 1; i <= 10; i++){mystack.push(i);}while (!mystack.empty()){sum += mystack.top();mystack.pop();}cout << sum << endl;return 0;
}

size():返回stack中的元素個數

stack<int> mystack;
for (int i = 1; i <= 10; i++)
{mystack.push(i);
}
cout << mystack.size() << endl;

top():返回棧頂元素的引用

stack<int> mystack;
for (int i = 1; i <= 10; i++)
{mystack.push(i);
}
cout << mystack.top() << endl;

?push():將元素val壓入stack中

stack<int> mystack;
for (int i = 1; i <= 10; i++)
{mystack.push(i);
}
while (!mystack.empty())
{cout << mystack.top() << " ";mystack.pop();
}

?stack是一個先進后出或后進先出的模式容器，相當于倒序輸出數據。

pop():將stack尾部的元素彈出

for (int i = 1; i <= 10; i++)
{mystack.push(i);
}
while (!mystack.empty())
{cout << mystack.top() << " ";mystack.pop();
}

1.3 棧中題的解析

逆波蘭表達式求值：

泥波蘭表達式又稱后綴表達式：

如：我們平時寫a+b，這是中綴表達式，寫成后綴表達式就是：ab+

(a+b)*c-(a+b)/e的后綴表達式為：

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

class Solution 
{
public:int evalRPN(vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); i++){string& str = tokens[i];// str為數字if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(atoi(str.c_str()));}else{// str為操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':// 題目說明了不存在除數為0的情況s.push(left / right);break;}}}return s.top();}
};

二、Queue -- 隊列

2.1 什么是隊列？

1、隊列是一種容器適配器，專門設計用于在 FIFO 上下文（先進先出）中運行，其中 elements入到容器的一端并從另一端提取。

2、隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。

2.2 隊列的使用?

隊列的使用函數接口與棧的類似：

queue():構造空的隊列

queue<int> q1;

empty(): 檢測隊列是否為空，是返回true，否則返回false?

queue<int> myqueue1;
for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}
cout << myqueue1.empty() << endl;
queue<int> myqueue2;
cout << myqueue2.empty() << endl;

size():?返回隊列中有效元素的個數

queue<int> myqueue1;
for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}
cout << myqueue1.size() << endl;

front():返回隊頭元素的引用 ?

queue<int> myqueue1;
for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}
cout << myqueue1.front() << endl;

back():?返回隊尾元素的引用?

queue<int> myqueue1;
for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}
cout << myqueue1.back() << endl;

push():?在隊尾將元素val入隊列

for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}

?pop():將隊頭元素出隊列

queue<int> myqueue1;
for (int i = 1; i <= 10; i++)
{myqueue1.push(i);
}
while (!myqueue1.empty())
{cout << myqueue1.front() << " ";myqueue1.pop();
}

?三、?priority_queue的介紹和使用

3.1 什么是優先級隊列(priority_queue)?

1. 優先隊列是一種容器適配器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。

2. 此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優先隊列中位于頂部的元素)。

3. 優先隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類,queue提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。?

4. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

在算法中，沒有純粹的使用queue來解題，大多需要使用優先級隊列的特性。

3.2 priority_queue的使用

優先級隊列默認使用vector作為其底層存儲數據的容器，在vector上又使用了堆算法將vector中元素構造成堆的結構，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用 priority_queue。

注意：默認情況下priority_queue是大堆。

?priority_queue():?構造一個空的優先級隊列

?(1) priority_queue 在內部將 comparing 函數和容器對象保存為 data，它們分別是 comp 和 ctnr 的副本。

(2) 位于其頂部，在 first 和 last 之間插入元素（在容器轉換為堆之前）

注意：范圍是左閉右開：[first,last)

empty():?檢測優先級隊列是否為空，是返回true，否則返回false ?

std::priority_queue<int> mypq;for (int i = 1; i <= 10; i++) mypq.push(i);while (!mypq.empty())
{cout << mypq.top() << " ";mypq.pop();
}

top():?返回優先級隊列中最大(最小元素)，即堆頂元素 ?

因為在使用priority_queue時，是大根堆還是小根堆是我們自己來決定的

vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
for (auto& e : v)
{q1.push(e);
}
cout << q1.top() << endl;

在priority_queue,還有第三個參數，可以使得大堆與小堆的修改：

#include? <functional>? // greater算法的頭文件

// 如果要創建小堆，將第三個模板參數換成greater比較方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;

push():?在優先級隊列中插入元素x

vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
for (auto& e : v)
{q1.push(e);
}

但push()的數據必須具有常量的性質。?

?pop():?刪除優先級隊列中最大(最小)元素，即堆頂元素

vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
for (auto& e : v)
{q1.push(e);
}
while (!q1.empty())
{cout << q1.top() << " ";q1.pop();
}

3.3 最具有代表性的一道題

數組中第K個大的元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 將數組中的元素先放入優先級隊列中priority_queue<int> p(nums.begin(), nums.end());// 將優先級隊列中前k-1個元素刪除掉for (int i = 0; i < k - 1; ++i){p.pop();}return p.top();}
};

?四、適配器

4.1 什么是適配器？

我們之前就提到無論是stack、queue還是我們現在學習的priority_queue，它的構造函數中class Container=deque<T>?

??它是什么呢？

適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。

4.2?STL標準庫中stack和queue的底層結構?

我之前說stack與queue是容器，這是一個錯誤的說法：

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque。

4.2.1 duque的原理介紹

deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與 list比較，空間利用率比較高。?

deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組。

雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜：?它是如何借助迭代器來維護自己開辟的空間呢？

這里它通過指針，以結構體的形式來鏈式鏈接每個節點。

4.2.2 deque的缺陷?

與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。

4.3?為什么選擇deque作為stack和queue的底層默認容器?

stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如 list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為： 1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。 2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。結合了deque的優點，而完美的避開了其缺陷。

那么到這里我們就學完了棧與隊列最簡單的認識，繼續努力加油吧！！！?