stack的实现
🗨️stack的容器适配器应该选什么比较好呢?
首先, stack的特点是 头部入, 尾部出 ⇒ 尾插 和 尾删操作比较频繁
我们前面学过的容器有 vector 和 list,
vector 和 list的尾插 和 尾删的时间复杂度是 O(1), 还是适合做容器适配器的.
stack的基本结构
template<class T, class Continer = vector<T>> // 默认容器适配器是vector class stack { private: Continer _con; // 维护这个容器对象就可以了 };
用这个容器对象来进行模拟实现stack
按照我们之前的想法, 容器适配器要么是 vector, 要么是 list.
这两者都是 自定义类型 ⇒ 自定义类型会调用它的默认构造 ⇒ 我们都不用写构造函数的
- push
void push(const T& val) { _con.push_back(val); }
- pop
void pop() { _con.pop_back(); }
- size
const T& top() const { return _con.back(); }
- empty
bool empty() const { return _con.size() == 0; }
- top
const T& top() const { return _con.back(); }
stack测试用例
void test_stack() { muyu::stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); cout << "size->" << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; st.push(2); st.push(3); st.push(4); st.pop(); st.pop(); cout << "size->" << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; }
queue的实现
🗨️queue的容器适配器能不能用 vector? 能不能使用list?
首先, queue的特点是 队尾入, 对头出 ⇒ 尾插, 头删操作比较频繁
其次, 我们来考量vector 和 list的尾插 和 头删效率如何?
vector的尾插是O(1), 头删是O(n )且 没有pop_front函数
list的尾插是O(1), 头删也是O(1) 且 有pop_front函数
⇒ 所以, 我们queue的容器适配器, list 比 vector更适合
queue的基本结构
template<class T, class Continer = list<T>> // 默认容器适配器是list class queue { private: Continer _con; // 维护容器对象 };
- push
void push(const T& val = T()) { _con.push_back(val); }
- pop
void pop() { _con.pop_front(); }
- front
const T& front() const { return _con.front(); }
- back
const T& back() const { return _con.back(); }
- empty
bool empty() const { return _con.size() == 0; }
- size
size_t size() const { return _con.size(); }
queue测试用例
void test_queue() { muyu::queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout << "front->" << q.front() << endl; cout << "back->" << q.back() << endl; cout << "size->" << q.size() << endl; cout << endl; q.pop(); q.pop(); cout << "front->" << q.front() << endl; cout << "back->" << q.back() << endl; cout << "size->" << q.size() << endl; cout << endl; while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; }
源码中， stack 和 queue的默认容器适配器给的是 deque.
我们来看一下deque的接口函数
我们惊奇的发现: deque不仅可以支持随机访问 [], 还支持 头插, 头删, 尾插, 尾删. 这不妥妥地是 vector 和 list 的结合体嘛.
🗨️那deque这么厉害, 我们之前为啥没有听过呢?
由于这个容器不值得我们去深度学习, 我这里就偷点懒, 盗用航哥的图了!
