目录
- 一、stack
- 1.1 stack的使用
- 1.2 stack的模拟实现
- 二、queue
- 2.1 queue的使用
- 2.2 queue的模拟实现
一、stack
1.1 stack的使用
stack是一种容器适配器,它的特点是后进先出,只能在容器的一端进行插入和删除操作。
stack的使用很简单,主要有以下几点:
- stack()——构造空的栈
- empty()——检测stack是否为空
- size()——返回stack中元素的个数
- top()——返回栈顶元素
- push()——入栈
- pop()——出栈
stack<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;
1.2 stack的模拟实现
stack作为容器适配器,它的底层可以复用其他的容器,例如vector、list、deque,默认的情况下使用的是deque,deque兼具vector和list在实现上的功能,只是有些在效率上会有所差异。
template<class T, class Container = deque<T>>//默认是dequeclass stack{public://构造stack(){}//入栈void push(const T& x){_con.push_back(x);//调用deque的push_back()}//出栈void pop(){_con.pop_back();//调用deque的pop_back()}//判空bool empty(){return _con.empty();//调用deque的empty()}//返回元素个数size_t size(){return _con.size();//调用deque的size()}//获取栈顶元素T& top(){return _con.back();//调用deque的back()}private:Container _con;};
二、queue
2.1 queue的使用
queue也是一种容器适配器,特点是先进先出,在一端插入元素,另一端删除或者获取元素。
queue的使用主要有以下几点:
- queue()——构造空的队列
- empty()——检测队列是否为空
- size()——返回队列中有效元素的个数
- front()——返回队头元素
- back()——返回队尾元素
- push()——入队列
- pop()——出队列
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
cout << q.size() << endl;
while (!q.empty())
{cout << q.front() << " ";q.pop();
}
cout << endl;
2.2 queue的模拟实现
queue的模拟实现与stack同理
template<class T, class Container = deque<T>>
class queue
{
public://构造queue(){}//判空bool empty(){return _con.empty();//调用deque的empty()}//返回元素个数size_t size(){return _con.size();//调用deque的size()}//返回队头元素T& front(){return _con.front();//调用deque的front()}//返回队尾元素T& back(){return _con.back();//调用deque的back()}//入队列void push(const T& x){_con.push_back(x);//调用deque的push_back()}//出队列void pop(){_con.pop_front();//调用deque的pop_front()}
private:Container _con;
};