【c++】模拟实现stack和queue

stack和queue"/>

【c++】模拟实现stack和queue

全部代码

• 栈

#pragma once
#include<deque>
using namespace std;namespace hqj
{template<class T, class Con = deque<T>>class stack{public:stack():_c(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top()const{return _c.back();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};}

• 队列

    template<class T, class Con = deque<T>>class queue{public:queue():_c(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
}

栈的模拟实现

模板参数

• 选择deque作为栈的底层容器

template<class T, class Con = deque<T>>

私有成员

• 一个容器对象_con

Con _c;

构造函数

• 因为_c是个容器对象，自身有构造函数，构造stack时会自动调用_C的构造函数，所以我们可以不写

 stack():_c(){}

push函数

• 栈的特点为栈顶入栈、栈顶出栈

• 我们之间使用容器对象_c的尾插函数便可以实现栈的入栈

 void push(const T& x){_c.push_back(x);}

pop 函数

• 栈的特点为栈顶入栈、栈顶出栈

• 我们之间使用容器对象_c的尾删函数便可以实现栈的出栈

        void pop(){_c.pop_back();}

top函数

• 栈顶恰恰是底层容器的末元素，我们直接调用底层容器_c的back函数即可

• 提供两个版本，一个是const、另一个是非const

        T& top(){return _c.back();}const T& top()const{return _c.back();}

size函数

• 底层容器中有多少数据就代表栈有多少数据，直接复用底层容器_c的size

        size_t size()const{return _c.size();}

判空函数

• 底层容器不为空栈也就不为空，还是直接复用底层容器_c的empty

        bool empty()const{return _c.empty();}

队列

构造函数

• 队列也是容器适配器的玩法，直接调用底层容器_C的构造函数

 queue():_c(){}

模板参数

• 选择deque作为队列的底层容器

template<class T, class Con = deque<T>>

私有成员

• 一个容器对象_con

Con _c;

push函数

• 队列的特点是队尾入队，队头出队

• 根据特点，我们调用底层容器的尾插函数即可

       void push(const T& x){_c.push_back(x);}

pop函数

• • 队列的特点是队尾入队，队头出队

• 根据特点，我们调用底层容器的头删函数即可

        void pop(){_c.pop_front();}

back函数

• 该接口负责返回队尾元素

• 而队尾恰恰是底层容器的末元素，直接复用底层容器的back函数

        T& back(){return _c.back();}const T& back()const{return _c.back();}

front函数

• 该接口负责返回队头元素

• 而队头恰恰是底层容器的首元素，直接复用底层容器的front函数

        T& front(){return _c.front();}const T& front()const{return _c.front();}

size函数

• 底层容器有多少数据，该队列就有多少数据，依然是复用即可

        size_t size()const{return _c.size();}

empty函数

• 底层容器不为空，队列便不为空，复用底层容器的判空函数

        bool empty()const{return _c.empty();}

总结

介绍栈和队列的模拟实现，之前有在C语言阶段实现过栈和队列，所以本文对栈和队列的结构不做解释。玩法是容器适配器玩法，底层容器选择的是双端队列，这是一种又像数组又像链表的东西。