亲宝软件园·资讯

展开

C++ stack与queue

m0_52012656 人气:0

容器适配器

适配器是一种设计模式(设计模式是一套反复使用的、大部分人知道的代码设计经验的总结),该模式试讲一个类的接口转化为用户希望的另一个接口,虽然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

优缺点

优点:

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

缺点:

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

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

stack模拟

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

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

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

模拟实现

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模拟实现

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

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

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

模拟实现

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;
    };

 

加载全部内容

相关教程
猜你喜欢
用户评论