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ù) | 功能 | 時間復(fù)雜度 |
|---|---|---|
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ù) | 功能 | 時間復(fù)雜度 |
|---|---|---|
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) |
| 典型應(yīng)用 | 函數(shù)調(diào)用棧、表達式求值、撤銷操作 | 消息隊列、CPU 任務(wù)調(diào)度、廣度優(yōu)先搜索 |
進階：自定義底層容器與使用場景
為什么 stack 可以用 vector，而 queue 不行？
stack只需要在一端進行操作（push_back,pop_back），vector完美支持，且效率很高。queue需要在兩端進行操作（push_back,pop_front）。vector沒有pop_front()方法，如果用它會導(dǎo)致效率極低的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)鍵。它們被廣泛應(yīng)用于各種算法和系統(tǒng)設(shè)計中。
到此這篇關(guān)于C++標準庫中的Stack(堆棧)和Queue(隊列)的文章就介紹到這了,更多相關(guān)C++標準庫stack和queue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
vector直接翻譯過來為向量,在C++中為封裝動態(tài)數(shù)組的容器,且有序,需要的朋友可以參考下2016-05-05
這篇文章主要為大家介紹了C語言lidar_align雷達里程計校準功能詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
本篇文章是對C++中函數(shù)參數(shù)取默認值進行了詳細的分析介紹，需要的朋友參考下2013-05-05
C++實現(xiàn)LeetCode(115.不同的子序列)
這篇文章主要介紹了C++實現(xiàn)LeetCode(115.不同的子序列),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家介紹了C++入門之list的使用，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
這篇文章主要為大家詳細介紹了C語言驅(qū)動開發(fā)中內(nèi)核文件的讀寫的系列函數(shù)，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2023-06-06
這篇文章主要介紹了C++中的5個存儲類的作用,存儲類是管理對象的生存期、鏈接和內(nèi)存位置的類型說明符,需要的朋友可以參考下2016-05-05
C語言之整數(shù)與浮點數(shù)運算的類型轉(zhuǎn)換規(guī)則詳解
這篇文章主要介紹了C語言之整數(shù)與浮點數(shù)運算的類型轉(zhuǎn)換規(guī)則,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-03-03
C語言模擬實現(xiàn)strstr函數(shù)的示例代碼
strstr是C語言中的函數(shù)，作用是返回字符串中首次出現(xiàn)子串的地址。本文將用C語言模擬實現(xiàn)strstr函數(shù)，感興趣的小伙伴可以跟隨小編一起學習一下2022-07-07
C語言全面細致講解單雙精度float與double的使用方法
C語言中小數(shù)的數(shù)據(jù)類型為 float 或 double：float 稱為單精度浮點數(shù)，double 稱為雙精度浮點數(shù)。不像整數(shù)，小數(shù)的長度始終是固定的，float 占用4個字節(jié)，double 占用8個字節(jié)2022-05-05