C++標準庫不只是包含了順序容器，還包含一些為滿足特殊需求而設計的容器，它們提供簡單的接口。

這些容器可被歸類為容器適配器(container adapter)，它們是改造別的標準順序容器，使之滿足特殊需求的新容器。

適配器:也稱配置器,把一種接口轉為另一種接口。

有三種標準的 容器適配器: stack(棧)、queue(隊列)和priority queue(優先級隊列)。 priority queue就是“根據排序準則，自動將元素排序”的隊列，其所謂“下一個””元素總是擁有最高優先級。

stack棧

stack 棧是一種只在一端(棧頂)進行數據插入(入棧)和刪除(出棧)的數據結構,它滿足后進先出(LIFO)的特性。

使用push(入棧)將數據放入stack,使用pop(出棧)將元素從容器中移除。 POP PUSH棧頂TOP棧底

?

使用stack,必須包含頭文件:

#include <stack>

在頭文件中,class stack定義如下:

namespace std{template <typename T,typename Container = deque<T>>class stack;
}

第一個參數T代表類型,第二個參數用來定義stack內部存放數據的容器,默認為deque。之所以選擇deque而非vector,是因為deque移除數據時可能會釋放內存,并在插入數據需要擴容時不需要復制所有的數據。

例如，以下定義了一個元素類型為整數的 stack:

std::stack<int>?st;

stack 只是很單純地把各項操作轉化為內部容器對應的函數調用。你可以使用任何支持 back()、push_back()和pop_back()成員函數的標準容器支持 stack。例如你可以使用 vector或list 來存放數據:

stack<int,vector<int>> st;//整型棧,使用vector存放數據

注意:forword_list和array不可以作為其容器

定義及初始化

#include <iostream>
#include <stack>
#include <vector>
#include <list>
using namespace std;int main()
{stack <char> s1;//創建一個默認的棧,最常用stack <char, deque<char> > s2;//顯示創建用deque保存數據的棧,和s1等價stack <int, vector<int> > s3;//創建用vector保存數據的棧stack <int, list<int> > s4;//創建用list保存數據的棧return 0;
}

先創建一個空的棧,然后往里面存放數據。

常用操作

stack棧的操作比較簡單,不支持迭代器和運算符,只有幾個簡單的成員函數。 empty成員函數

empty成員函數

判斷棧是否為空。

//判空
bool IsEmpty(PLStack ps)
{return ps->next == NULL;
}

pop成員函數

出棧函數,刪除棧頂元素。

//獲取棧頂元素的值,并且刪除
bool Pop(PLStack ps, int* rtval)
{assert(ps != NULL);if (ps == NULL)return false;if (IsEmpty(ps))return false;*rtval = ps->next->date;LSNode* p = ps->next;ps->next = ps->next->next;free(p);return true;
}

push成員函數

入棧函數,往棧頂添加數據。

//往棧中入數據(入棧操作)
bool Push(PLStack ps, int val)
{assert(ps != NULL);if (ps == NULL)return false;LSNode* p = (LSNode*)malloc(sizeof(LSNode));assert(p != NULL);p->date = val;p->next = ps->next;ps->next = p;return false;
}

size成員函數

返回棧的數據個數。

//獲取棧中有效數據的個數
int GetLength(PLStack ps)
{assert(ps != NULL);if (ps == NULL)return 0;int count = 0;for (LSNode* p = ps->next; p != NULL; p = p->next){count++;}return count;
}

top成員函數

返回棧頂元素的引用。

//獲取棧頂元素的值,但不刪除
bool  GetTop(PLStack ps, int* rtval)
{assert(ps != NULL);if (ps == NULL)return false;if (IsEmpty(ps))return false;*rtval = ps->next->date;return true;
}

棧的實現方式?

鏈表實現：鏈表實現棧則更加靈活，它不需要預先分配固定大小的內存空間，適用于棧的大小動態變化且難以預估的場景。在鏈表實現中，每個節點包含數據和指向下一個節點的指針。棧頂對應鏈表的頭節點，入棧和出棧操作都在鏈表頭部進行，時間復雜度同樣為 O (1)。

.h文件

#pragma once//鏈式棧
typedef struct LSNode
{int date;struct LSNode* next;
}LSNode, * PLStack;//初始化
void InitStack(PLStack ps);//往棧中入數據(入棧操作)
bool Push(PLStack ps, int val);//獲取棧頂元素的值,但不刪除
bool  GetTop(PLStack ps, int* rtval);//獲取棧頂元素的值,并且刪除
bool Pop(PLStack ps, int* rtval);//判空
bool IsEmpty(PLStack ps);//獲取棧中有效數據的個數
int GetLength(PLStack ps);//清空所有的數據
void Clear(PLStack ps);//銷毀
void Destroy(PLStack ps);

.cpp文件

#include "Istak.h"
#include <iostream>
#include <cassert>
using namespace std;//初始化
void InitStack(PLStack ps)
{assert(ps != NULL);if (ps == NULL)return;ps->next = NULL;
}//往棧中入數據(入棧操作)
bool Push(PLStack ps, int val)
{assert(ps != NULL);if (ps == NULL)return false;LSNode* p = (LSNode*)malloc(sizeof(LSNode));assert(p != NULL);p->date = val;p->next = ps->next;ps->next = p;return false;
}//獲取棧頂元素的值,但不刪除
bool  GetTop(PLStack ps, int* rtval)
{assert(ps != NULL);if (ps == NULL)return false;if (IsEmpty(ps))return false;*rtval = ps->next->date;return true;
}//獲取棧頂元素的值,并且刪除
bool Pop(PLStack ps, int* rtval)
{assert(ps != NULL);if (ps == NULL)return false;if (IsEmpty(ps))return false;*rtval = ps->next->date;LSNode* p = ps->next;ps->next = ps->next->next;free(p);return true;
}//判空
bool IsEmpty(PLStack ps)
{return ps->next == NULL;
}//獲取棧中有效數據的個數
int GetLength(PLStack ps)
{assert(ps != NULL);if (ps == NULL)return 0;int count = 0;for (LSNode* p = ps->next; p != NULL; p = p->next){count++;}return count;
}//清空所有的數據
void Clear(PLStack ps)
{Destroy(ps);
}//銷毀
void Destroy(PLStack ps)
{LSNode* p;while (ps->next != NULL){p = ps->next;ps->next = p->next;free(p);}
}

棧的應用場景?

1.表達式求值

在數學表達式求值中，棧發揮著關鍵作用。例如，對于后綴表達式（逆波蘭表達式），我們可以利用棧來高效地計算結果。后綴表達式將運算符放在操作數之后，避免了括號帶來的優先級判斷復雜性。計算時，從左到右掃描后綴表達式，遇到操作數就將其入棧，遇到運算符則從棧中彈出相應數量的操作數進行運算，并將結果入棧。最終，棧頂元素即為表達式的計算結果。以表達式 “3 4 + 2 *” 為例，計算過程如下：?

掃描到 3，入棧，棧：[3]?

掃描到 4，入棧，棧：[3, 4]?

掃描到 +，彈出 4 和 3，計算 3 + 4 = 7，將 7 入棧，棧：[7]?

掃描到 2，入棧，棧：[7, 2]?

掃描到 *，彈出 2 和 7，計算 7 * 2 = 14，將 14 入棧，棧：[14]??

最終結果為 14

2.括號匹配

在編譯器和文本編輯器中，常常需要檢查代碼中的括號是否正確匹配，如圓括號、方括號和花括號。利用棧可以輕松解決這個問題。當遇到左括號時，將其入棧；遇到右括號時，從棧中彈出對應的左括號進行匹配。如果在匹配過程中棧為空或者匹配失敗，說明括號不匹配。例如，對于字符串 “{[()]}”，處理過程如下：?

遇到 {，入棧，棧：[{]?

遇到 [，入棧，棧：[{, []?

遇到 (，入棧，棧：[{, [, (]?

遇到 )，彈出 (進行匹配，棧：[{, []?

遇到 ]，彈出 [進行匹配，棧：[{]?

遇到 }，彈出 {進行匹配，棧：[]?

匹配成功

3.函數調用棧

在程序執行過程中，函數調用是通過棧來管理的。當一個函數被調用時，它的相關信息，如參數、局部變量和返回地址等，會被壓入棧中。當函數執行完畢返回時，這些信息會從棧中彈出，程序繼續執行調用函數的下一條指令。例如，在一個包含多個函數嵌套調用的程序中，棧記錄了函數調用的順序和狀態，確保函數能夠正確返回和繼續執行。假設函數 A 調用函數 B，函數 B 又調用函數 C，棧的狀態變化如下：?

調用 A，A 的相關信息入棧，棧：[A]?

A 中調用 B，B 的相關信息入棧，棧：[A, B]?

B 中調用 C，C 的相關信息入棧，棧：[A, B, C]?

C 執行完畢返回，C 的信息出棧，棧：[A, B]?

B 執行完畢返回，B 的信息出棧，棧：[A]?

A 執行完畢返回，A 的信息出棧，棧：[]

4.深度優先搜索（DFS）

在圖論和搜索算法中，深度優先搜索常常用棧來實現。在遍歷圖的過程中，從起始節點開始，將其入棧。然后，每次從棧中彈出一個節點，訪問該節點，并將其未訪問過的鄰接節點入棧，直到棧為空。這樣的方式使得搜索沿著一條路徑盡可能深地探索下去，直到無法繼續，然后回溯到上一個節點繼續探索其他路徑。

5.瀏覽器歷史記錄

我們日常使用的瀏覽器，其歷史記錄功能也運用了棧的思想。當我們依次訪問網頁 A、B、C 時，這些網頁依次被壓入棧中。當我們點擊 “后退” 按鈕時，就相當于執行出棧操作，從棧頂彈出當前頁面，回到上一個頁面。例如，訪問順序為 A -> B -> C，棧的狀態為 [C, B, A]，點擊 “后退”，C 出棧，回到 B 頁面，棧變為 [B, A]

總結?

棧作為一種簡單而強大的數據結構，以其獨特的后進先出特性，在眾多領域展現出高效的應用價值。無論是復雜的算法實現，還是日常使用的軟件功能，棧都默默發揮著重要作用。通過對棧的概念、操作、實現方式以及應用場景的深入學習，我們不僅掌握了一種基礎的數據結構，更能在編程實踐中靈活運用它來解決各種實際問題。在未來的編程之旅中，希望你能充分利用棧的優勢，優化代碼，提升程序的性能和效率。讓我們繼續探索數據結構的奇妙世界，解鎖更多編程的奧秘！