文章目录
- 一、容器适配器
- 二、stack
- 2.1 push
- 2.2 pop
- 2.3 top
- 2.4 size
- 2.5 empty
- 三、queue
- 3.1 push
- 3.2 pop
- 3.3 front
- 3.4 back
- 3.5 size
- 3.6 empty
- 四、deque
- 4.1 deque的介绍
- 4.2 deque的底层结构
- 4.3 deque的优势与缺陷
- 4.4 为什么选择deque作为stack和queue的底层默认容器
- 总结
一、容器适配器
STL并没有将stack和queue划分为容器，而是将其称为容器适配器，原因是stack和queue只是对其他容器的接口进行了封装。
这也让stack和queue模拟实现起来异常简单，所以两个合在一起讲解介绍。
二、stack
细节：
- stack具有LIFO（后进先出）性质
- 默认容器使用vector，使用尾插尾删效率高（STL库中使用deque）
template<class T, class Container = vector<T>>
class stack
{
public:
private:Container _con;
};
2.1 push
压栈
void push(const T& x)
{_con.push_back(x);
}
2.2 pop
出栈
void pop()
{_con.pop_back();
}
2.3 top
获取栈顶元素
const T& top() const
{return _con.back();
}
2.4 size
获取栈的有效元素个数
size_t size() const
{return _con.size();
}
2.5 empty
判断栈是否为空
bool empty() const
{return _con.empty();
}
三、queue
细节：
- queue具有FIFO（先进先出）性质
- 默认容器使用list，使用尾插头删效率高（STL库中使用deque）
template<class T, class Container = list<T>>
class queue
{
public:
private:Container _con;
};
3.1 push
入队
void push(const T& x)
{_con.push_back(x);
}
3.2 pop
出队
void pop()
{_con.pop_front();
}
3.3 front
获取队头元素
const T& front() const
{return _con.front();
}
3.4 back
获取队尾元素
const T& back() const
{return _con.back();
}
3.5 size
获取队列的有效元素个数
size_t size() const
{return _con.size();
}
3.6 empty
判断队列是否为空
bool empty() const
{return _con.empty();
}
四、deque
4.1 deque的介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
4.2 deque的底层结构
其实，deque并不是一整块连续空间，而是一段一段连续的小空间结合在一起。deque有一个中控数组，存放一段段小空间的指针，类似动态开辟的二维数组。
一开始在中间开辟空间，随后根据需求向两边进行扩容。
所以，针对分段连续的空间结构，为了支持随机访问，设计出了比较复杂的迭代器。
这样的空间结构，也导致遍历的效率变得十分低下，因为deque的迭代器需要频繁判断是否抵达分段空间的边界
4.3 deque的优势与缺陷
优势：
- 支持随机访问
- 头尾的插入删除，时间复杂度为O(1)
缺陷：
- 中间插入删除比较麻烦
- 不适合遍历
总体来说，deque结合了vector和list的优势，却又没有vector和list的性能那么极致，在大部分场景下都不太常用，所以这里只是简单介绍，并不模拟实现底层结构。
4.4 为什么选择deque作为stack和queue的底层默认容器
原因有两点：
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长
时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
总结
这次学习了容器适配器——stack和queue，了解到用容器作为模板的美妙与神奇，极大简化构建容器的代码量。同时简单了解deque的结构和使用场景，进一步理解STL容器的设计。
