【C++】stack、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;
};