C++標準庫中的Stack(堆棧)和Queue(隊列)詳解
1. stack（棧）
核心概念
棧是一種 LIFO 的數(shù)據(jù)結(jié)構(gòu)。
LIFO: Last-In, First-Out，即后進先出。
想象一疊盤子：你總是從最上面取走盤子，新盤子也總是放在最上面。
頭文件
cpp
#include <stack>
底層容器
默認情況下，stack 使用 deque 作為其底層容器。但你也可以顯式指定使用 vector 或 list。
cpp
stack<int> s1; // 默認使用 deque stack<int, vector<int>> s2; // 使用 vector 作為底層容器 stack<int, list<int>> s3; // 使用 list 作為底層容器
主要成員函數(shù)
| 函數(shù) | 功能 | 時間復雜度 |
|---|---|---|
push(const T& value) | 將元素壓入棧頂 | O(1) |
pop() | 彈出棧頂元素 | O(1) |
top() | 返回棧頂元素的引用 | O(1) |
empty() | 檢查棧是否為空 | O(1) |
size() | 返回棧中元素的數(shù)量 | O(1) |
注意：stack 沒有提供 begin() 和 end() 方法，因此不能使用范圍 for 循環(huán)來遍歷。遍歷棧的唯一方式是不斷彈出其元素。
基本用法示例
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
// 遍歷棧 (會銷毀棧)
cout << "Stack elements: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
// 輸出：Stack elements: 20 10
cout << endl;
return 0;
}2. queue（隊列）
核心概念
隊列是一種 FIFO 的數(shù)據(jù)結(jié)構(gòu)。
FIFO: First-In, First-Out，即先進先出。
想象排隊買票：先來的人先買到票離開，新來的人排在隊伍末尾。
頭文件
cpp
#include <queue>
底層容器
默認情況下，queue 使用 deque 作為其底層容器。你也可以指定使用 list（但不能用 vector，因為 vector 沒有 pop_front 方法）。
cpp
queue<int> q1; // 默認使用 deque queue<int, list<int>> q2; // 使用 list 作為底層容器
主要成員函數(shù)
| 函數(shù) | 功能 | 時間復雜度 |
|---|---|---|
push(const T& value) | 將元素添加到隊尾 | O(1) |
pop() | 移除隊首元素 | O(1) |
front() | 返回隊首元素的引用 | O(1) |
back() | 返回隊尾元素的引用 | O(1) |
empty() | 檢查隊列是否為空 | O(1) |
size() | 返回隊列中元素的數(shù)量 | O(1) |
注意：和 stack 一樣，queue 也沒有迭代器，不能使用范圍 for 循環(huán)遍歷。
基本用法示例
cpp
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
// 添加元素到隊尾
q.push(10);
q.push(20);
q.push(30);
// 查看隊首和隊尾元素
cout << "Front element: " << q.front() << endl; // 輸出 10
cout << "Back element: " << q.back() << endl; // 輸出 30
// 移除隊首元素
q.pop(); // 移除 10
cout << "Front after pop: " << q.front() << endl; // 輸出 20
// 遍歷隊列 (會銷毀隊列)
cout << "Queue elements: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
// 輸出：Queue elements: 20 30
cout << endl;
return 0;
}關(guān)鍵區(qū)別總結(jié)
| 特性 | stack (棧) | queue (隊列) |
|---|---|---|
| 數(shù)據(jù)原則 | LIFO (后進先出) | FIFO (先進先出) |
| 核心操作 | push(), pop(), top() | push(), pop(), front(), back() |
| 訪問元素 | 只能訪問棧頂 (top) | 可以訪問隊首 (front) 和隊尾 (back) |
| 典型應用 | 函數(shù)調(diào)用棧、表達式求值、撤銷操作 | 消息隊列、CPU 任務調(diào)度、廣度優(yōu)先搜索 |
進階：自定義底層容器與使用場景
為什么 stack 可以用 vector，而 queue 不行？
stack只需要在一端進行操作（push_back,pop_back），vector完美支持，且效率很高。queue需要在兩端進行操作（push_back,pop_front）。vector沒有pop_front()方法，如果用它會導致效率極低的O(n)操作（需要移動所有元素），所以標準庫禁止了這種用法。
如何選擇底層容器？
默認 deque：在大多數(shù)情況下是最平衡的選擇，兩端操作效率都高。
stack 用 vector：如果你確定你的棧操作非常密集，且內(nèi)存分配性能至關(guān)重要，
vector可能稍快一些，因為它使用連續(xù)內(nèi)存。list：如果你需要穩(wěn)定的迭代器（在元素插入刪除時不會失效），或者你的元素非常大，移動成本高，可以考慮
list。
cpp
// 一個使用 vector 作為底層容器的棧 stack<int, vector<int>> my_stack; // 一個使用 list 作為底層容器的隊列 queue<int, list<int>> my_queue;
總結(jié)
stack 和 queue 是 C++ 中兩個簡單而強大的容器適配器，它們通過限制對底層數(shù)據(jù)的訪問方式，強制實現(xiàn)了特定的數(shù)據(jù)管理規(guī)則。理解它們的 LIFO 和 FIFO 原則是正確使用的關(guān)鍵。它們被廣泛應用于各種算法和系統(tǒng)設計中。
到此這篇關(guān)于C++標準庫中的Stack(堆棧)和Queue(隊列)的文章就介紹到這了,更多相關(guān)C++標準庫stack和queue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)實時鐘表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
變長參數(shù)的函數(shù)，即參數(shù)個數(shù)可變、參數(shù)類型不定的函數(shù)。設計一個參數(shù)個數(shù)可變、參數(shù)類型不定的函數(shù)是可能的，最常見的例子是printf函數(shù)、scanf函數(shù)和高級語言的Format函數(shù)。最近的一個項目中就遇到這么一個相關(guān)的問題，感興趣的朋友們下面來一起看看吧。2016-10-10
C++實現(xiàn)LeetCode(146.近最少使用頁面置換緩存器)
這篇文章主要介紹了C++實現(xiàn)LeetCode(146.近最少使用頁面置換緩存器),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
C++指針數(shù)組、數(shù)組指針、數(shù)組名及二維數(shù)組技巧匯總
這篇文章主要介紹了C++指針數(shù)組、數(shù)組指針、數(shù)組名及二維數(shù)組技巧匯總,對于深入理解C++數(shù)組與指針來說非常重要,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C語言中const與指針使用方法總結(jié)的相關(guān)資料,需要的朋友可以參考下2017-10-10
今天小編就為大家分享一篇關(guān)于C++關(guān)于引用作為函數(shù)的用法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C++中浮點數(shù)、double類型如何與0值作比較詳解
浮點數(shù)在內(nèi)存中的存儲機制和整型數(shù)不同,其有舍入誤差,在計算機中用近似表示任意某個實數(shù),這篇文章主要介紹了C++中浮點數(shù)、double類型如何與0值作比較的相關(guān)資料,需要的朋友可以參考下2025-03-03
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)簡單圖書管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家詳細介紹了C++實現(xiàn)趣味掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06