[数据结构与算法]stack与queue模拟实现

stack与queue的模拟实现

容器适配器

适配器是一种设计模式（设计模式是一套反复使用的、大部分人知道的代码设计经验的总结），该模式试讲一个类的接口转化为用户希望的另一个接口，虽然stack与queue中也可以存放元素，但在STL中并没有将其划分为容器，而是成为容器适配器，这是因为stack与队列只是堆其他容器进行了包装，STL中的stack和queue是使用双端队列进行封装的。

双端队列

概念

它是一种双开口的连续空间数据结构（与队列没有关系），双开口的含义是可以再两端进行插入删除操作，且时间复杂度为O(1)，与vector比较，头插效率比较高，不需要移动数据，与list比较，空间利用率高。

结构

?

deque并不是真正的连续空间，而是使用一小段连续的小空间拼接而成，实际上deque类似于一个动态的二维数组，其底层结构如下图所示：

?

中控数组map：?map数组是一个指针数组，指向多个buff数组用来储存数据，当buff数组头或尾满了，就新开辟一个buff数组，其指针存在map的相对应位置，当map数组满了，会对map数组扩容(指针数组的扩容并不会效率低)

deque迭代器

deque所谓的连续空间是一个假象，是他底层复杂的迭代器实现

STL源码：

typedef T** map_pointer;
T* cur;
T* first;
T* last;
map_pointer node

cur:是当前的node指向的buff数组当前指向的地址

first：是当前node指向的buff数组，第一个元素的地址。

last:是当前node指向的buff数组，最后一个元素的地址。

node：是指向当前map数组对应的指针，由于他指向的也是一个指针·，所以为二级指针。

优缺点

优点：

双端队列，说明他很合适头插头删，尾插尾删，他去做stack和queue的容器适配器很合适。

缺点：

双端队列中间插入删除非常麻烦，效率不高。

deque是一种折中的方案设计，随机访问效率不如vector，任意插入删除不及list

stack模拟

1. stack是一种容器适配器，专门在具有后进先出的上下文环境中，其删除只能是在一端进行操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出 。

3. stack的底层原理可以是任何标椎的容器类模板或者一些特定的容器类，这些容器类应该支持以下操作：

empty:判空操作。

back:尾部元素获取。

push_back：尾部插入元素操作

·· pop_back:尾部删除元素操作。

模拟实现

template<class T, class Con = deque<T>>
 ? ?class stack
 ?  {
 ? ?public:
 ? ? ? ?stack();
 ? ? ? ?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;
 ?  };
?

queue模拟实现

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

模拟实现

template<class T, class Con = deque<T>>
 ? ?class queue
 ?  {
 ? ? ? ?public:
 ? ? ? ? ? ?queue();
 ? ? ? ? ? ?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;
 ?  };