C++?超詳細講解stack與queue的使用
stack
介紹和使用
stack是一種容器適配器，專門用在具有后進先出操作的上下文環(huán)境中，其刪除只能從容器的一端進行元素的插入與提取操作。
stack是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：
- empty：判空操作
- back：獲取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部刪除元素操作
標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。
模擬實現(xiàn)
從棧的接口可以看出，棧實際是一種特殊的vector，直接使用vector即可模擬實現(xiàn)stack
#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>
using namespace std;
namespace s {
//stack是一個Container適配(封裝轉換)出來的
template<class T,class Container = std::deque<T>>
class stack {
public:
stack() {
}
void pop()
{
_con.pop_back();
}
void push(const T& x)
{
_con.push_back(x);
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_stack1()
{
s::stack<int,vector<int>> st;
//s::stack<int, list<int>> st;
//s::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top();
st.pop();
}
cout << endl;
}
}
stack的使用例題
最小棧
題目描述：設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。push(x) —— 將元素 x 推入棧中。pop() —— 刪除棧頂?shù)脑?。top() —— 獲取棧頂元素。getMin() —— 檢索棧中的最小元素。
解題思路：定義兩個成員變量（棧），當插入數(shù)據(jù)時，_st正常插入，如果要插入的數(shù)據(jù)比_st的棧頂元素小時，就把該數(shù)據(jù)也插入_minst。出數(shù)據(jù)時，取出_st棧頂元素，如果該數(shù)據(jù)和_minst棧頂數(shù)據(jù)相等，就把_minst的棧頂元素也取出，這樣_minst的棧頂元素就始終是棧中存在元素的最小值。
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty() || val<=_minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top()==_minst.top())
{
_minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
stack<int> _st;
stack<int> _minst;
};
棧的彈出壓入序列
題目描述：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。
解題思路：定義一個棧，把pushV中的數(shù)據(jù)依次放入棧中。如果遇到放入的pushV中的數(shù)據(jù)和popV中數(shù)據(jù)相等，那么把st棧頂元素取出。最后st如果為空，則符合要求。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size()==0)
return true;
stack<int> st;
int pushi=0,popi=0;
while(pushi<pushV.size()){
st.push(pushV[pushi]);
//如果pushV[pushi]和popV[popi]匹配上了
while(!st.empty() && st.top()==popV[popi]){
st.pop();
++popi;
}
++pushi;
}
if(st.empty())
return true;
return false;
}
};
逆波蘭表達式求值
題目描述：根據(jù) 逆波蘭表示法，求表達式的值。有效的算符包括 +、-、*、/ 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。說明：整數(shù)除法只保留整數(shù)部分。給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。
解題思路：遍歷，如果是字符串中是數(shù)字，將字符數(shù)字轉化為數(shù)字后放入棧中，如果遇到運算符，取出兩個棧頂元素，先取出的棧頂元素作為運算符右邊的數(shù)字，后取出的作為運算符左邊的數(shù)字，按照字符串中的運算符做運算，得到的數(shù)字再放入棧中，再遍歷數(shù)組放入數(shù)字，以此類推。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
int left=0,right=0;
for(const auto& str:tokens)
{
if(str=="+" ||str=="-"||str=="*"||str=="/")
{
right=st.top();
st.pop();
left=st.top();
st.pop();
switch(str[0])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
}
}
else
{
st.push(stoi(str));
}
}
return st.top();
}
};
queue
和棧一樣，隊列是一種容器適配器。該底層容器至少支持以下操作：
empty：檢測隊列是否為空
size：返回隊列中有效元素的個數(shù)
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列
標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。vector類的頭刪效率太低，不能頭刪，所以不適配。
模擬實現(xiàn)
因為queue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實現(xiàn)queue
#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>
using namespace std;
namespace q {
template<class T,class Container=std::deque<T>>
class queue {
public:
queue() {
}
void pop()
{
_con.pop_front();
}
void push(const T& x)
{
_con.push_back(x);
}
const T& back()
{
return _con.back();
}
const T& front()
{
return _con.front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_queue1()
{
//q::queue<int,list<int>> q1;
//q::queue<int, vector<int>> q1;//vector頭刪效率低，不適配，報錯
q::queue<int> q1;
q1.push(1);
q1.push(2);
q1.push(3);
q1.push(4);
while (!q1.empty())
{
cout << q1.front();
q1.pop();
}
cout << endl;
}
}
容器適配器
適配器是一種設計模式(設計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設計經(jīng)驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。
雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque
deque簡介
deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結構，即可以在頭尾兩端進行插入刪除操作，且時間復雜度為O(1)。
deque不是真正完全連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成，類似于一個動態(tài)的二維數(shù)組。
deque底層是一段假想的連續(xù)空間，實際上是分段連續(xù)的，它借助迭代器來維護其假想連續(xù)的結構，因此deque的迭代器設計也比較復雜。
vector的缺點是當空間不夠時要擴容，會存在一定的空間浪費，頭插或中間插入需要挪動數(shù)據(jù)，效率低。優(yōu)點是可以隨機訪問，cpu高速緩存命中率很高。list的缺點是無法隨機訪問，cpu高速緩存命中率低(地址不連續(xù))。優(yōu)點是可按需申請釋放空間，任意位置的插入刪除數(shù)據(jù)時間復雜度為O(1)，效率高。而deque折中了vector和list，從使用的角度，避開了它們的缺點，可以支持隨機訪問，頭尾插入效率也較高，擴容時不需要挪動大量數(shù)據(jù)，效率較vector高。但deque不夠極致，隨機訪問效率不如vector，任意位置插入刪除不如list，且中間插入刪除數(shù)據(jù)也很麻煩，效率不高，需要挪動整體數(shù)據(jù)，或是挪動目標buff數(shù)組，并記錄每個buff數(shù)組的大小。在遍歷時，deque的迭代器需要頻繁檢測是否移動到某段小空間的邊界，效率低下。所以deque比較適合頭插尾插多的情況，比如作為stack和queue的底層數(shù)據(jù)結構。stack和queue不需要遍歷（所以沒有迭代器），只需要在固定的兩端進行操作。stack中元素增長時，如果需要擴容，deque的效率比vector高；queue同理，且內(nèi)存使用率高。
priority_queue優(yōu)先級隊列
優(yōu)先隊列是一種容器適配器，根據(jù)嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。
類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素（優(yōu)先隊列中位于頂部的元素）。
優(yōu)先隊列被實現(xiàn)為容器適配器，即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的尾部彈出，其成為優(yōu)先隊列的頂部。
底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：
- empty()：檢測容器是否為空
- size()：返回容器中有效元素個數(shù)
- front()：返回容器中第一個元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：刪除容器尾部元素
標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。
需要支持隨機訪問迭代器，以便始終在內(nèi)部保持堆結構。容器適配器通過在需要時自動調用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。
priority_queue的使用
優(yōu)先級隊列默認使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了對算法將vector中元素構造成堆的結構，因此priority_queue就是堆。注意：默認情況下priority_queue是大堆。
在OJ中的使用：
數(shù)組中的第k個最大元素
題目描述：給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回數(shù)組中第 k 個最大的元素。
請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(),nums.end());
//默認大堆，取出前k-1個元素后的第k個堆頂元素就是第k大的元素
while(--k)
{
pq.pop();
}
return pq.top();
}
};
priority_queue的模擬實現(xiàn)
#pragma once
#include <vector>
#include <list>
#include <iostream>
using namespace std;
namespace priority
{
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
//模板參數(shù)--類型
//函數(shù)參數(shù)--對象
//less 大堆
template<class T,class Container=::vector<T>,class Compare=Less<typename Container::value_type>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
//插入數(shù)據(jù)
while (first != last)
{
_con.push_back(*first);
++first;
}
//建堆
for (int i = (_con.size() - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(i);
}
}
void AdjustDown(size_t parent)
{
Compare com;
int child = parent * 2+1;
while (child <_con.size())
{
if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
{
child++;
}
//_con[parent] < _con[child]
if (com(_con[parent] , _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(size_t child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top() const
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_priority_queue()
{
list<int> lt = { 1,2,3,4,5, };
priority_queue<int, vector<int>, Greater<int>> pq(lt.begin(), lt.end());
pq.push(10);
pq.push(20);
pq.push(30);
pq.push(40);
pq.push(50);
pq.push(60);
cout << pq.top() << endl;
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
}
通過仿函數(shù)控制比較方式
如果在priority_queue中放自定義類型的數(shù)據(jù)，我們需要在自定義類型中重載>或<。如以下情形，類型T是Date*，如果不重載<或>，比較的就是地址大小。
//仿函數(shù)的變異玩法--通過仿函數(shù)控制比較方式
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);
}
friend ostream& operator<<(ostream& _cout, const Date& d);
friend class PDateLess;
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day << endl;
return _cout;
}
class PDateLess
{
public:
bool operator()(const Date* p1, const Date* p2)
{
return *p1 < *p2;
}
};
int main()
{
priority_queue<Date*, vector<Date*>, PDateLess> pq;
pq.push(new Date(2023, 11, 24));
pq.push(new Date(2021, 10, 24));
pq.push(new Date(2023, 11, 14));
pq.push(new Date(2022, 1, 24));
cout << (*pq.top()) << endl;
pq.pop();
return 0;
}
到此這篇關于C++ stack和queue的文章就介紹到這了,更多相關C++ stack內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
QT原生控件沒有實現(xiàn)如儀表盤或者溫度計的控件,只好自己實現(xiàn),所以本文為大家介紹了如何利用qt實現(xiàn)自定義溫度/濕度控件,感興趣的小伙伴可以了解下2023-11-11
在本篇文章里小編給大家分享了一篇關于c++中創(chuàng)建.in文件的方法步驟的內(nèi)容以及相關知識點，需要的朋友們學習下。2019-07-07
VC++實現(xiàn)文件與應用程序關聯(lián)的方法(注冊表修改)
這篇文章主要介紹了VC++實現(xiàn)文件與應用程序關聯(lián)的方法,涉及VC++針對注冊表的相關操作技巧,需要的朋友可以參考下2016-08-08
這篇文章主要介紹了C語言的變量，變量是C語言語法和語義中一個很重要的知識點，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
AVL樹是高度平衡的而二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,下面這篇文章主要給大家介紹了關于C++實現(xiàn)AVL樹的相關資料,需要的朋友可以參考下2022-01-01
這篇文章主要為大家詳細介紹了C++實現(xiàn)高校人員信息管理系統(tǒng)項，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C++入門實現(xiàn)十步萬度游戲,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-10-10
本文主要介紹了Qt實現(xiàn)卡牌對對碰游戲,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-10-10
深入解析C++中的拷貝、移動與返回值優(yōu)化問題(為什么可以返回臨時對象)
本文給大家介紹為什么可以返回臨時對象?深入解析C++中的拷貝、移動與返回值優(yōu)化問題,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2025-09-09
本文介紹了在VS2019上配置MPI,包括下載和安裝MPI、創(chuàng)建項目、配置屬性、導入頭文件和庫文件、添加依賴項等步驟,具有一定的參考價值,感興趣的可以了解一下2024-12-12