stack

使用stack时需要头文件#include<stack>

stack的介绍

stack是一种容器适配器，用于具有后进先出(LIFO)的环境中。只能从容器的一端（栈顶），执行删除、插入和提取操作。

stack是作为容器适配器实现的，容器适配器是对特定容器类封装，作为其底层的容器。vector、deque、list均符合特定的底层容器需求，如果没有指定特定的底层容器，默认使用deque

stack的使用

函数	接口说明
stack()	构造空的栈
empty()	判断栈是否为空
size()	返回栈中的元素个数
top()	返回栈顶元素的引用
push()	将val压栈
pop()	出栈顶元素

test:


void test_stack()
{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;
}

注意：从栈的接口可以看出，栈实际是一种特殊的vector，使用vector完全可以模拟实现stack

stack的实现

stack接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//容器可以使用vector,deque容器在本博客最后一个知识点介绍//template<class T, class Container = vector<T>>//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class stack{public:stack(){}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

queue

使用queue时需要头文件#include<queue>

queue的介绍

queue是一种容器适配器，用于具有先进先出(FIFO)的环境中。从容器的一端插入元素，另一端提取元素。

queue作为容器适配器实现，容器适配器是对特定容器类封装，作为其底层的容器。deque、list符合特定的底层容器需求，如果没有为queue实列化指定特定的底层容器，默认使用deque

queue的使用

函数	接口说明
queue()	构造空的队列
empty()	判断队列是否为空
size()	返回队列中的元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将val入列
pop()	在队头元素出队列

test:

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << "size:" << q.size() << endl;cout << "front:" << q.front() << endl;q.pop();cout << "back:" << q.back() << endl;while (!q.empty()){cout << "front:" << q.front() << " ";q.pop();}cout << endl;
}

queue的实现

因为queue的接口有头插和尾插，使用vector封装效率底，所以可以借助list模拟实现。这里我们依旧使用的默认容器deque

queue接口的实现是对deque容器接口的封装。

#include <deque>namespace kpl
{//template<class T, class Container = list<T>>template<class T, class Container = deque<T>>class queue{public:queue(){}bool empty(){return _con.empty();}size_t size(){return _con.size();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}private:Container _con;};
}