目錄

前言

數(shù)據(jù)結(jié)構(gòu)

deque

vector和list的優(yōu)缺點

push

pop

top

size

empty

完整代碼

---

前言

stack類就是數(shù)據(jù)結(jié)構(gòu)中的棧

C數(shù)據(jù)結(jié)構(gòu)：棧-CSDN博客

stack類所擁有的函數(shù)相比與string、vector和list類都少很多，這是因為棧這個數(shù)據(jù)結(jié)構(gòu)是后進先出的，它必須被有所限制，所以所能用的函數(shù)只需要那幾個足矣

棧可以用順序表來實現(xiàn)，也可以用鏈表來實現(xiàn)，我們只需要控制它先進先出的特性即可，用什么容器實現(xiàn)取決于個人

因為我們前面實現(xiàn)了vector和list類，所以再實現(xiàn)stack類就容易很多了，只需要復(fù)用vector和list容器內(nèi)的函數(shù)即可

數(shù)據(jù)結(jié)構(gòu)

template<class T, class Container = std::deque<T>>
class stack
{
public:private:Container _con;
};

這里的模板有兩個，T是棧的類型，Container表示的是所需要使用哪個容器來實現(xiàn)這個棧

我們需要用這個Container里面的成員函數(shù)來復(fù)用從而輕松的實現(xiàn)這個棧

這里的Container默認是deque

deque

deque（雙端隊列）也是STL中的一個容器，它是vector和list的結(jié)合

vector和list的優(yōu)缺點

vector優(yōu)點：

1. 隨機訪問效率高

2. 在內(nèi)存中連續(xù)存儲，緩存命中率高

vector缺點：

1. 插入和刪除效率低

2. 空間分配不靈活（利用率低）

list優(yōu)點：

1. 插入和刪除效率高

2. 空間利用率高

list缺點：

1. 訪問數(shù)據(jù)速度慢

2. 緩存利用率低（空間不連續(xù)，緩存命中率低）

為什么說deque是vector和list的結(jié)合？

下面是deque的數(shù)據(jù)結(jié)構(gòu)圖片

deque有n個buffer緩沖區(qū)（個數(shù)取決于數(shù)據(jù)個數(shù)）

這個緩沖區(qū)比list的空間大，像是一個小型數(shù)組，這個數(shù)組由中控器控制

而中控器可以通過一個數(shù)組來存儲一個個的指針，這些指針又指向一個個緩沖區(qū)，所以它能夠控制每一個緩沖區(qū)

iterator迭代器的cur、first和last來控制緩沖區(qū)的數(shù)據(jù)，node則表示是哪一個緩沖區(qū)

deque總結(jié)：

1. deque的頭尾插入效率高

2. 下標的隨機訪問效率也還可以

3. 中間插入刪除的效率很低（O(N)）

push

void push(const T& x)
{_con.push_back(x);
}

棧的push就是插入到最后的位置，所以只需要復(fù)用容器中的push_back函數(shù)即可

deque、vector和list都有這些函數(shù)，所以這三個容器都可以用來實現(xiàn)stack類

pop

void pop()
{_con.pop_back();
}

棧的pop就是尾刪，所以只需要復(fù)用pop_back函數(shù)即可?

top

const T& top() const
{return _con.back();
}

棧的top就是取尾部數(shù)據(jù)，返回back函數(shù)即可?

size

size_t size() const
{return _con.size();
}

棧的size就是取得棧的數(shù)據(jù)個數(shù)，返回容器的size函數(shù)即可?

empty

bool empty() const
{return _con.empty();
}

棧的empty就是判斷棧是否為空，返回empty函數(shù)即可

只要上述的函數(shù)名哪個類中有，并且功能相同，就可以使用那個類來完成stack的實現(xiàn)

完整代碼

#pragma once#include<iostream>
#include<deque>namespace lyw
{template<class T, class Container = std::deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

---

完