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