目錄

棧

棧（stack）的聲明：

push()： 將元素推入棧頂

pop()： 彈出棧頂元素

top()： 訪問棧頂元素，但不彈出

empty()： 檢查棧是否為空?

size()： 返回棧中元素的數(shù)量?

emplace()： 在棧頂構(gòu)造一個元素?

== 和 !=： 用于比較兩個棧是否相等或不相等

隊列

隊列（queue）的聲明：

push()： 將元素推入隊列尾部

pop()： 從隊列頭部彈出元素

front()： 訪問隊列頭部元素

back()： 訪問隊列尾部元素

empty()： 檢查隊列是否為空

總結(jié)

---

棧

棧（stack）的聲明：

#include <stack>// 聲明一個整數(shù)類型的棧
std::stack<int> myStack;// 在棧中壓入元素
myStack.push(10);
myStack.push(20);// 彈出棧頂元素
myStack.pop();// 訪問棧頂元素
int topElement = myStack.top();

push()： 將元素推入棧頂

#include <stack>std::stack<int> myStack;myStack.push(10);
myStack.push(20);

pop()： 彈出棧頂元素

myStack.pop();

top()： 訪問棧頂元素，但不彈出

int topElement = myStack.top();

empty()： 檢查棧是否為空?

if (myStack.empty()) {// 棧為空
}

size()： 返回棧中元素的數(shù)量?

size_t stackSize = myStack.size();

emplace()： 在棧頂構(gòu)造一個元素?

myStack.emplace(30);

== 和 !=： 用于比較兩個棧是否相等或不相等

std::stack<int> stackA;
std::stack<int> stackB;// ...if (stackA == stackB) {// 棧A和棧B相等
}if (stackA != stackB) {// 棧A和棧B不相等
}

妙用?

逆波蘭表達式計算： 使用棧來計算逆波蘭表達式。運算符遇到時，彈出棧頂?shù)牟僮鲾?shù)進行計算，并將結(jié)果重新壓入棧。

// 逆波蘭表達式：3 4 + 5 *
std::stack<int> st;
st.push(3);
st.push(4);
st.push(st.top() + 5);  // 3 + 4
st.pop();
int result = st.top() * 5;  // (3 + 4) * 5

括號匹配檢查： 使用棧來檢查表達式中的括號是否匹配。遍歷表達式，遇到左括號壓入棧，遇到右括號時檢查棧頂是否是對應(yīng)的左括號。

std::stack<char> st;
std::string expression = "((a + b) * (c - d))";
for (char c : expression) {if (c == '(') {st.push(c);} else if (c == ')') {if (st.empty() || st.top() != '(') {// 括號不匹配break;}st.pop();}
}
bool isBalanced = st.empty();

函數(shù)調(diào)用堆棧： 編程語言中的函數(shù)調(diào)用使用堆棧來保存局部變量和返回地址。當函數(shù)調(diào)用時，創(chuàng)建一個新的棧幀，函數(shù)執(zhí)行完畢后，將棧幀彈出。

void func1() {int x = 10;// ...
}void func2() {int y = 20;// ...
}int main() {func1();func2();return 0;
}

隊列

隊列（queue）的聲明：

#include <queue>// 聲明一個整數(shù)類型的隊列
std::queue<int> myQueue;// 在隊列尾部插入元素
myQueue.push(30);
myQueue.push(40);// 從隊列頭部彈出元素
myQueue.pop();// 訪問隊列頭部元素
int frontElement = myQueue.front();

push()： 將元素推入隊列尾部

#include <queue>std::queue<int> myQueue;myQueue.push(10);
myQueue.push(20);

pop()： 從隊列頭部彈出元素

myQueue.pop();

front()： 訪問隊列頭部元素

int frontElement = myQueue.front();

back()： 訪問隊列尾部元素

int backElement = myQueue.back();

empty()： 檢查隊列是否為空

if (myQueue.empty()) {// 隊列為空
}

隊列妙用?

廣度優(yōu)先搜索（BFS）： 在圖或樹的遍歷中，使用隊列來實現(xiàn)廣度優(yōu)先搜索，確保按照層次遍歷節(jié)點。

void BFS(Node* root) {std::queue<Node*> q;q.push(root);while (!q.empty()) {Node* current = q.front();// 處理當前節(jié)點// ...// 將當前節(jié)點的鄰居節(jié)點入隊for (Node* neighbor : current->neighbors) {q.push(neighbor);}// 出隊q.pop();}
}

任務(wù)調(diào)度： 在操作系統(tǒng)或并發(fā)編程中，使用隊列來管理任務(wù)隊列，確保按照先進先出的原則執(zhí)行任務(wù)。

#include <queue>
#include <thread>
#include <iostream>std::queue<std::function<void()>> taskQueue;
std::mutex taskQueueMutex;void workerThread() {while (true) {std::function<void()> task;{std::lock_guard<std::mutex> lock(taskQueueMutex);if (!taskQueue.empty()) {task = taskQueue.front();taskQueue.pop();}}if (task) {task();} else {// Sleep or yield to avoid busy-waitingstd::this_thread::yield();}}
}

緩存管理： 使用隊列來管理緩存中的數(shù)據(jù)，確保最先進入緩存的數(shù)據(jù)最先被替換。?

#include <queue>
#include <iostream>std::queue<int> cache;void addToCache(int data) {cache.push(data);// 如果緩存大小超過限制，移除隊首元素if (cache.size() > MAX_CACHE_SIZE) {cache.pop();}
}

打印任務(wù)隊列： 模擬打印任務(wù)的隊列，確保先提交的打印任務(wù)先得到執(zhí)行。

?

#include <queue>
#include <iostream>std::queue<std::string> printQueue;void submitPrintJob(const std::string& document) {printQueue.push(document);
}void printNextJob() {if (!printQueue.empty()) {std::string document = printQueue.front();std::cout << "Printing: " << document << std::endl;printQueue.pop();}
}

總結(jié)

????????棧（Stack）和隊列（Queue）是兩種基本的數(shù)據(jù)結(jié)構(gòu)，分別以后進先出（Last-In-First-Out，LIFO）和先進先出（First-In-First-Out，FIFO）的原則組織數(shù)據(jù)。在面試中，它們常被用于解決各種問題。