一、棧的概念
棧是?種只允許在?端進?數據插?和刪除操作的線性表。
- 進?數據插?或刪除的?端稱為棧頂，另?端稱為棧底。不含元素的棧稱為空棧。
- 進棧就是往棧中放?元素，出棧就是將元素彈出棧頂。
?
二、棧的模擬實現
1.?創建
- 本質還是線性表，因此可以創建?個?夠?的數組，充當棧結構
- 再定義?個變量 n ，?來記錄棧中元素的個數，同時還可以標記棧頂的位置。
const int N = 1e6 + 10;int n;int stk[N];2.?進棧
時間復雜度：
顯然是 O(1) 。?
這?依舊舍棄下標為 0 的位置，有效元素從 1 開始記錄。
進棧操作，那就把元素放在棧頂位置即可。
// 進棧
void push(int x){stk[++n] = x;}3.?出棧
時間復雜度：
顯然是 O(1) 。?
不?真的刪除元素，只?將元素個數減 1 ，就相當于刪除棧頂元素。
// 出棧
void pop(){n--;}4. 棧頂元素
時間復雜度：
顯然是 O(1) 。?
查詢棧頂元素。
這?要注意，因為棧特殊的規定，不?持遍歷整個棧中的元素。因此，需要查找棧中元素的時候，只能查找到棧頂元素。
// 棧頂元素
int top(){return stk[n];}5. 判空
時間復雜度：
顯然是 O(1) 。?
判斷棧是否為空
// 判空
bool empty(){return n == 0;}6. 有效元素的個數
時間復雜度：
顯然是 O(1) 。
// 棧中元素個數
int size(){return n;}7. 所有測試代碼
#include <iostream>using namespace std;const int N = 1e5 + 10;// 創建棧
int stk[N], n;// 進棧 - 本質就是順序表里面的尾插
void push(int x)
{stk[++n] = x;
}// 出棧 - 順序表的尾刪操作
void pop()
{n--;
}// 查詢棧頂元素
int top()
{return stk[n];
}// 判斷是否為空
bool empty()
{return n == 0;
}// 查詢有效元素的個數
int size()
{return n;
}int main()
{for(int i = 1; i <= 10; i++){push(i);}// 當棧不為空的時候while(size()) // while(!empty()) {cout << top() << endl;pop();}return 0;
}二、stack
有了之前 vector 和 list 的鋪墊，棧的使?應該會?較得?應?。
1. 如何創建？
2. 關???有什么函數？
3. 函數的功能以及時間復雜度
1.?創建
- stack<T> st;
- T 可以是任意類型的數據。
2.?size / empty
時間復雜度：?O(1)??
- size ：返回棧?實際元素的個數；
- empty ：返回棧是否為空。
3.?push/pop
時間復雜度：?O(1)??
- push ：進棧；
- pop ：出棧。
4.?top
時間復雜度：?O(1)???
top ：返回棧頂元素，但是不會刪除棧頂元素。
5. 所有測試代碼
#include <iostream>
#include <stack>using namespace std;int main()
{stack<int> st;// 先講 1~10 進棧for(int i = 1; i <= 10; i++){st.push(i);}while(st.size()) // !st.empty(){cout << st.top() << endl;st.pop();}return 0;
}
)
)
