圖解C++的STL之stack和queue,輕松理解數(shù)據(jù)結(jié)構(gòu)
前言
今天咱們學(xué)習(xí)stack和queue，咱們還是依照官網(wǎng)來學(xué)習(xí)：
stack - C++ Reference (cplusplus.com)
queue - C++ Reference (cplusplus.com)
主體
在數(shù)據(jù)結(jié)構(gòu)初階中，我們模擬實現(xiàn)了stack和queue，只能說我們知道棧和隊列，但是棧和隊列的底層是如何實現(xiàn)的我們就不得而知了，面對這個現(xiàn)象我們從新學(xué)習(xí)棧和隊列，深度解剖。學(xué)習(xí)這個版塊，咱們按照下面的圖解進行學(xué)習(xí)：
stack的介紹和使用
stack的介紹
stack - C++ Reference (cplusplus.com)
stack是一種容器適配器，其本質(zhì)是數(shù)據(jù)結(jié)構(gòu)中的棧。它是一種只能在一端進行插入和刪除操作的線性表。stack是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒有為stack指定特定的底層容器，默認(rèn)情況下使用deque。棧和隊列都叫做適配器/配接器，不是直接實現(xiàn)的，而是封裝其他容器，包裝轉(zhuǎn)換實現(xiàn)出來的stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下： empty：判空操作。back：獲取尾部元素的操作，這是因為棧的top操作相當(dāng)于拿取尾部元素。push_back：尾部插入元素操作。pop_back：尾部刪除元素操作。
stack的使用
| 函數(shù)說明 | 接口說明 |
|---|---|
| stack() | 構(gòu)造空的棧 |
| empty() | 檢測stack是否為空 |
| size() | 返回stack中元素的個數(shù) |
| top() | 返回棧頂元素的引用 |
| push() | 將元素val壓入stack中 |
| pop() | 將stack中尾部的元素彈出 |
代碼訓(xùn)練：
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void test_stack()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.empty() << endl; // 檢測stack是否為空
cout << st.size() << endl; // 返回stack中元素的個數(shù)
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
int main()
{
test_stack();
return 0;
}代碼訓(xùn)練：tack的案例，首先先創(chuàng)建一個stack容器，<int>這里表示我這個容器存放的是int類型的數(shù)據(jù)。然后通過push()將數(shù)據(jù)壓入棧中，stack并不支持迭代器訪問，我們通過接口empty()判斷棧是否為空，通過top()訪問棧頂元素，pop()將數(shù)據(jù)出棧。
stack的應(yīng)用
1.最小棧
問題分析：設(shè)計兩個棧，一個負(fù)責(zé)保存棧的元素，一個負(fù)責(zé)保存棧的最小值。只要有元素比最小值棧的頂部元素還有小，那么，就將這個值壓入最小值棧中，這樣就能保證，最小值棧的頂部元素永遠是當(dāng)前壓入的所有元素中最小的。
代碼：
class MinStack {
public:
MinStack()
{
}
void push(int val)
{
st.push(val);
if(minst.empty() || val <= minst.top())
{
minst.push(val);
}
}
void 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; // 輔助棧
};2.棧的壓入、彈出序列
問題分析：借助一個輔助棧，首先，創(chuàng)建兩個變量i和j，分別指向pushV數(shù)組的元素和popV數(shù)組的元素，然后將pushV的數(shù)據(jù)壓入棧中，直到遇到頂部元素恰好等于出棧序列的元素，那么就將棧頂元素出棧，并且j++。最后，如果棧的元素不為空，那么說明當(dāng)前出棧序列不符合。
代碼：
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
stack<int> st;
int i = 0, j = 0; // i 指向push數(shù)組的元素 ， j 指向pop數(shù)組元素
for(; i < pushV.size();i++)
{
st.push(pushV[i]);
while(!st.empty() && st.top() == popV[j])
{
st.pop();
j++;
}
}
return st.empty();
}
};3.逆波蘭表達式求值
問題分析：同樣借助一個輔助棧來完成，遍歷數(shù)組tokens，遇到數(shù)值就壓入棧中，遇到符號，就彈出兩個元素，并且根據(jù)符號進行求值。最后，棧頂元素就是最終的表達式結(jié)果。
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int> st;
for(int i = 0;i<tokens.size();++i)
{
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
{
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
if(tokens[i] == "+") st.push(num2 + num1);
else if(tokens[i] == "-") st.push(num2 - num1);
else if(tokens[i] == "*") st.push(num2 * num1);
else if(tokens[i] == "/") st.push(num2 / num1);
}
else
{
st.push(stoi(tokens[i])); // stoi 把字符串轉(zhuǎn)為數(shù)字
}
}
int result = st.top();
st.pop();
return result;
}
};4.用棧實現(xiàn)隊列
問題分析：設(shè)計兩個棧，一個棧用來入數(shù)據(jù)，一個棧用來出數(shù)據(jù)。入隊列操作，可以直接將數(shù)據(jù)插入到stIn中，出隊列的時候，如果stOut為空，就將stIn的數(shù)據(jù)放到stOut中，我們直到棧的特性是后進先出，隊列的特性是先進先出，那么將元素放到一個棧中，再出棧到另一個棧中，相當(dāng)于元素原本的順序不變，恰好符合隊列的要求。
代碼：
class MyQueue {
public:
stack<int> stIn; // 用來入數(shù)據(jù)
stack<int> stOut; // 用來出數(shù)據(jù)
MyQueue()
{
}
void push(int x)
{
stIn.push(x);
}
int pop()
{
if(stOut.empty())
{
while(!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
// 獲取頭部元素
int peek()
{
int res = this->pop();
stOut.push(res);
return res;
}
bool empty()
{
return stIn.empty() && stOut.empty();
}
};queue的介紹和使用
queue的介紹
queue - C++ Reference (cplusplus.com)
queue是一種容器適配器，專門用于在先進先出上下文中操作，在容器的一端插入元素，另一端刪除元素。
queue的底層也是用作容器來進行封裝，底層容器必須支持以下操作：
empty：檢測隊列是否為空。size：返回隊列的有效元素個數(shù)front：返回隊頭元素的引用back：返回隊尾元素的引用push_back：在隊列尾部入隊列pop_front：在隊列頭部出隊列標(biāo)準(zhǔn)容器中的deque、list滿足了這些要求，默認(rèn)情況下，使用deque作為底層容器類。
queue的使用
| 函數(shù)說明 | 接口說明 |
|---|---|
| empty | 檢測queue是否為空 |
| size | 返回queue的元素個數(shù) |
| front | 返回隊頭元素的引用 |
| back | 返回隊尾元素的引用 |
| push | 在隊尾將元素入隊列 |
| pop | 將隊頭元素出隊列 |
代碼訓(xùn)練：
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void test_queue()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
cout << q.empty() << endl;
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
int main()
{
test_queue();
return 0;
}運行結(jié)果：
queue的應(yīng)用
用隊列實現(xiàn)棧
問題分析：使用兩個隊列，重點在于出棧操作，出棧操作，將隊列1的元素，放到隊列2，隊列1的元素只剩下1個，然后這個作為出棧的元素，之后q1 = q2，然后將q2的元素進行出隊。
class MyStack {
public:
queue<int> q1;
queue<int> q2;
MyStack() {
}
void push(int x) {
q1.push(x);
}
int pop() {
int size = q1.size();
size--;
while(size--)
{
q2.push(q1.front());
q1.pop();
}
int result = q1.front();
q1.pop();
q1 = q2;
while(!q2.empty())
{
q2.pop();
}
return result;
}
int top() {
return q1.back();
}
bool empty() {
return q1.empty();
}
};priority_queue的介紹和使用
priority_queue的介紹
priority_queue::priority_queue - C++ Reference (cplusplus.com)
優(yōu)先級隊列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個元素是所有元素中最大的。優(yōu)先級隊列的底層是用堆進行實現(xiàn)的，大根堆的堆頂是最大的。標(biāo)準(zhǔn)容器vector和queue都滿足以上要求，如果沒有特定要求，默認(rèn)使用vector作為底層容器類。需要支持隨機訪問迭代器，保證內(nèi)部始終保持堆結(jié)構(gòu)。容器適配器在需要的時候調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。優(yōu)先級隊列的底層容器可以使任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計的容器類。容器應(yīng)該可以通過隨機訪問迭代器訪問，并支持以下操作： empty()：檢測容器是否為空。size()：返回容器有效元素個數(shù)。front()：返回容器第一個元素的引用push_back()：在容器尾部插入元素pop_back()：刪除容器尾部元素 ??容器適配器 ??什么是適配器
適配器是一種設(shè)計模式，假設(shè)已經(jīng)有一個設(shè)計系統(tǒng)，你需要把新的廠商類整合進去，但是，新的廠商類的接口和原來的接口不一致，但是，又不可以修改原有的代碼，這個時候，就可以設(shè)計一個適配器作為中間人，實現(xiàn)所期望的接口，與新的廠商類進行對接。
STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)
stack和queue是對標(biāo)準(zhǔn)庫的其他容器的接口進行了包裝，STL的stack和queue默認(rèn)使用deque。
deque的介紹和使用
deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
到此這篇關(guān)于圖解C++的STL之stack和queue,輕松理解數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)STL之stack和queue詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了QSS樣式表實現(xiàn)界面換膚功能，對QSS樣式表進行簡單介紹，本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-10-10
下面小編就為大家?guī)硪黄樞蚓€性表的代碼實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-04-04
pair是一種模板類型，其中包含兩個數(shù)據(jù)值，兩個數(shù)據(jù)的類型可以不同,本篇詳細(xì)的介紹了Pair的使用方法和實例，有興趣的同學(xué)可以了解一下。2016-12-12
這篇文章主要介紹了C++設(shè)計模式之模板方法模式,本文講解了什么是模板方法模式、模板方法模式的UML類圖、模板方法模式的使用場合等內(nèi)容,需要的朋友可以參考下2014-10-10
所謂函數(shù)模板實際上是建立一個通用函數(shù)，其涵涵素類型額形參類型不具體指定，用一個虛擬的類型來代表，這個通用函數(shù)就稱為函數(shù)模板2013-10-10
這篇文章主要為大家詳細(xì)介紹了一些C++中日期類的常見題目，文中的示例代碼講解詳細(xì)，對我們掌握C++有一定的幫助，感興趣的小伙伴可以了解一下2023-06-06
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)組實現(xiàn)打磚塊游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
系統(tǒng)之間通信方式很多如：系統(tǒng)之間調(diào)用（http/rpc等）,異步間接調(diào)用如發(fā)送消息、公共存儲等,算法工程為C/C++工程,本文將介紹如何在C/C++中如何發(fā)送與接收Kakfa消息（包含：Kafka的SASL認(rèn)證方式）,并提供了詳細(xì)的源碼和講解,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了使用opencv拉伸圖像擴大分辨率示例,需要的朋友可以參考下2014-04-04