1. stack（棧）

核心概念

棧是一種 LIFO 的數(shù)據(jù)結(jié)構(gòu)。

• LIFO: Last-In, First-Out，即后進(jìn)先出。

• 想象一疊盤(pán)子：你總是從最上面取走盤(pán)子，新盤(pán)子也總是放在最上面。

頭文件

cpp

#include <stack>

底層容器

默認(rèn)情況下，stack 使用 deque 作為其底層容器。但你也可以顯式指定使用 vector 或 list。

cpp

stack<int> s1; // 默認(rèn)使用 deque
stack<int, vector<int>> s2; // 使用 vector 作為底層容器
stack<int, list<int>> s3; // 使用 list 作為底層容器

主要成員函數(shù)

注意：stack 沒(méi)有提供 begin() 和 end() 方法，因此不能使用范圍 for 循環(huán)來(lái)遍歷。遍歷棧的唯一方式是不斷彈出其元素。

基本用法示例

cpp

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // 壓入元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 查看棧頂元素
    cout << "Top element: " << s.top() << endl; // 輸出 30

    // 彈出棧頂元素
    s.pop(); // 彈出 30
    cout << "Top after pop: " << s.top() << endl; // 輸出 20

    // 遍歷棧 (會(huì)銷(xiāo)毀棧)
    cout << "Stack elements: ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();

    }
    // 輸出：Stack elements: 20 10
    cout << endl;

    return 0;
}

2. queue（隊(duì)列）

核心概念

隊(duì)列是一種 FIFO 的數(shù)據(jù)結(jié)構(gòu)。

• FIFO: First-In, First-Out，即先進(jìn)先出。

• 想象排隊(duì)買(mǎi)票：先來(lái)的人先買(mǎi)到票離開(kāi)，新來(lái)的人排在隊(duì)伍末尾。

頭文件

cpp

#include <queue>

底層容器

默認(rèn)情況下，queue 使用 deque 作為其底層容器。你也可以指定使用 list（但不能用 vector，因?yàn)?nbsp;vector 沒(méi)有 pop_front 方法）。

cpp

queue<int> q1; // 默認(rèn)使用 deque
queue<int, list<int>> q2; // 使用 list 作為底層容器

主要成員函數(shù)

注意：和 stack 一樣，queue 也沒(méi)有迭代器，不能使用范圍 for 循環(huán)遍歷。

基本用法示例

cpp

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // 添加元素到隊(duì)尾
    q.push(10);
    q.push(20);
    q.push(30);

    // 查看隊(duì)首和隊(duì)尾元素
    cout << "Front element: " << q.front() << endl; // 輸出 10
    cout << "Back element: " << q.back() << endl;  // 輸出 30

    // 移除隊(duì)首元素
    q.pop(); // 移除 10
    cout << "Front after pop: " << q.front() << endl; // 輸出 20

    // 遍歷隊(duì)列 (會(huì)銷(xiāo)毀隊(duì)列)
    cout << "Queue elements: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();

    }
    // 輸出：Queue elements: 20 30
    cout << endl;

    return 0;
}

關(guān)鍵區(qū)別總結(jié)

進(jìn)階：自定義底層容器與使用場(chǎng)景

為什么 stack 可以用 vector，而 queue 不行？

• stack 只需要在一端進(jìn)行操作（push_back, pop_back），vector 完美支持，且效率很高。

• queue 需要在兩端進(jìn)行操作（push_back, pop_front）。vector 沒(méi)有 pop_front() 方法，如果用它會(huì)導(dǎo)致效率極低的 O(n) 操作（需要移動(dòng)所有元素），所以標(biāo)準(zhǔn)庫(kù)禁止了這種用法。

如何選擇底層容器？

• 默認(rèn) deque：在大多數(shù)情況下是最平衡的選擇，兩端操作效率都高。

• stack 用 vector：如果你確定你的棧操作非常密集，且內(nèi)存分配性能至關(guān)重要，vector 可能稍快一些，因?yàn)樗褂眠B續(xù)內(nèi)存。

• list：如果你需要穩(wěn)定的迭代器（在元素插入刪除時(shí)不會(huì)失效），或者你的元素非常大，移動(dòng)成本高，可以考慮 list。

cpp

// 一個(gè)使用 vector 作為底層容器的棧
stack<int, vector<int>> my_stack;

// 一個(gè)使用 list 作為底層容器的隊(duì)列
queue<int, list<int>> my_queue;

總結(jié)

stack 和 queue 是 C++ 中兩個(gè)簡(jiǎn)單而強(qiáng)大的容器適配器，它們通過(guò)限制對(duì)底層數(shù)據(jù)的訪問(wèn)方式，強(qiáng)制實(shí)現(xiàn)了特定的數(shù)據(jù)管理規(guī)則。理解它們的 LIFO 和 FIFO 原則是正確使用的關(guān)鍵。它們被廣泛應(yīng)用于各種算法和系統(tǒng)設(shè)計(jì)中。

到此這篇關(guān)于C++標(biāo)準(zhǔn)庫(kù)中的Stack(堆棧)和Queue(隊(duì)列)的文章就介紹到這了,更多相關(guān)C++標(biāo)準(zhǔn)庫(kù)stack和queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論