一、stack类
1.stack的介绍
通过文档，我们可以了解到以下的内容：
- 区别于vector等容器，stack是一种容器适配器。通俗的讲，stack封装了一个其他的容器，并提供特定的成员函数来对容器进行操作并遵循栈的后进先出（Last-in First-out）原则。
- stack的底层容器至少要支持以下操作：
- empty：判空
- size：获取容器有效元素个数
- back：获取容器尾部元素
- push_back：尾插
- pop_back：尾删
- 通过这些操作，我们就可以实现栈的压入和弹出等行为
- 我们可以指定vector、list和deque作为stack的底层容器，如果没有指定，默认情况下使用deque，后面会对该容器进行介绍
2.stack的使用
在实例化与stack类类似的容器适配器时，模板参数除了必须要传入元素类型，还可以选择传入底层容器的种类
例如：
1）empty
bool empty() const;检测栈是否为空
2）size
size_type size() const;返回stack中元素的个数
3）top
value_type& top();
const value_type& top(); const返回栈顶元素的引用
4）push
void push(const value_type& val);将val压入栈中
5）pop
void pop();将栈顶元素弹出
例如：
void test_stack()
{
stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}运行结果:
二、 stack的模拟实现
前面提到，stack是一个容器适配器，其底层封装了其他的容器，这里我们以vector作为底层容器
namespace STACK
{
template<class T, class Container = vector<T>>
//一个模板参数传入数据类型，一个模板参数传入底层容器
class stack
{
public:
void push(const T& val)
{
_con.push_back(val); //压栈即在容器尾部插入数据
}
void pop()
{
_con.pop_back(); //出栈即删除容器尾部的数据
}
const T& top()
{
return _con.back(); //栈顶元素即容器尾部的元素
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con; //对容器进行封装
};
}三、queue类
1. 了解queue
通过文档，我们可以了解到以下的内容：
- 队列也是一种容器适配器，对容器进行封装，提供特定的成员函数对容器进行操作并遵循队列的先进先出（First-in First-out）原则。
- 队列的底层容器至少要支持以下操作：
- empty：判空
- size：获取容器有效元素个数
- front：获取容器头部元素
- back：获取容器尾部元素
- push_back：尾插
- pop_front：头删
通过这些操作，我们就可以实现队列的出队和入队等行为。
- 我们可以指定list和deque作为queue的底层容器，如果没有指定，默认情况下使用deque
2.使用queue
1）empty
bool empty() const;检测队列是否为空
2）size
size_type size() const;返回队列中有效元素的个数
3）front
value_type& front();
const value_type& front(); const返回队头元素的引用
4）back
value_type& back();
const value_type& (); cons5）push
void push(const value_type& val);从队尾将元素val入队列
6）pop
void pop();将队头元素出队列
例如：
void test_queue()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}运行结果:
3.queue的模拟实现
因为queue需要头删，如果底层使用vector效率太低，这里我们使用list作为queue的底层容器
namespace QUEUE
{
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val); //入队列，即从容器尾部插入数据
}
void pop()
{
_con.pop_front(); //出队列，即从容器头部删除数据
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
