C++基础语法:STL之容器(3)--序列容器中的deque

前言

       "打牢基础,万事不愁" .C++的基础语法的学习

引入

        序列容器的学习.以<C++ Prime Plus> 6th Edition(以下称"本书")内容理解

        本书中容器内容不多只有几页.最好是有数据结构方面的知识积累,如果没有在学的同时补上.

        序列容器回顾:序列容器内元素按严格线性顺序排列,至少是正向迭代器(含以上).序列容器包括deque(双端队列),forward_list(单链表),list(双向链表),queue(队列),priority_queue(优先队列),stack(栈),vector(动态数组),array(替代数组的容器)

deque(双端队列) 

        双端队列的内容在本书P698,只有两段话. ----deque,发音[dek]

       第1部分: deque模板类（在deque头文件中声明）表示双端队列（doubleended queue）,通常被简称为deque。在STL中,其实现类似于vector容器，支持随机访问。主要区别在于,从deque对象的开始位置插入和删除元素的时间是固定的,而不像vector中那样是线性时间的。所以,如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构.

        ----蓝色部分告诉程序员双端队列的使用场景,切记.

        解读及代码:

        本书P613,章节号15.2.2模板中的嵌套有链队列的示例,根据那段代码做蓝本,尝试实现deque.注意:下列代码为了练手,试图重现逻辑,不保证准确. 

         1.deque容器声明

template <class T>          
class deque                     //容器deque声明
{
private:
    enum {Q_SIZE = 10};
    class Node                  //表示结点的内部类
    {
    public:
        T t;
        Node * next;
        Node(const T& t):T(t), next(0){ }
    };
    Node * front;               // 指向前结点
    Node * rear;                // 指向末结点
    int items;                  // 队列里当前元素数量
    const int qsize;            // 队列元素最大数量
public:
    deque(int qs = Q_SIZE);     //构造函数,初始时元素个数为0的状态描述
    ~deque();
    bool isempty() const
    {
        return items == 0;
    }
    bool isfull() const
    {
        return items == qsize;
    }
    int queuecount() const
    {
        return items;
    }
    void push_front(const T& t); // 添加元素到头部
    T pop_front();               // 删除头部元素
};
 

        2.容器的算法可以有很多,根据需求定制.因为deque的特点,在头部插入和删除固定时间,所以只尝试构造函数,和push_front(t)头部插入和pop_front(t)头部删除算法

        题外话:本来想用"头结点head",但和front重复了,要么用head,要么用front,所以没有那个必要.

        构造函数:

template<class T>
deque::deque(int qs = Q_SIZE){
    front=rear=nullptr;        //或者等于0;初始化首尾指针指空
    qsize=qs;                  //设置队列最大数量
    items=0;                   //队列当前元素个数0
}

        头部插入元素:          

template<class T>
void deque<T>::push_front(const T& t){
    Node *newNode=new Node(t);            //传入数据,生成新结点
    newNode->next=front;                  //新结点挂到原前结点的前面
    front=newNode;                        //新结点成为前结点
}

        头部删除元素:         

template<class T>
T deque<T>::pop_front(){
    Node *tmp=front;        //标记前结点;
    front=front->next;      //前结点后移到下一个结点;
    T value=tmp->t;         //取出原前结点的值
    delete tmp;           //删除原前结点;
    return value;           //返回原结点的里的元素值 
}

         ----原本以为会发现点新的东西,结果没有,很平常的几行代码.

        题外话1:因为有现成的链队列做参照,所以把deque的底层也用了链表,可能他底层用的是数组也未知.

        题外话2:关于deque容器的作为序列的其他算法,如插入删除,用迭代器对象做函数形参的情况,稍微复杂一点.试想如果不用迭代器,用的是容器本身的参数,比较容易.用迭代器做形参,也是把迭代器对象中关于容器的参数提取出来,执行相同的逻辑,所以也不展开了.

         第2部分:为实现在deque两端执行插入和删除操作的时间为固定的这一目的，deque对象的设计比vector对象更为复杂。因此,尽管二者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些

        解读及代码:意思比较明确,deque拥有在双端插入和删除的优势,如果不考虑该条件,在随机访问和序列中部执行插入和删除操作的话,仍优先选择vector

小结

        deque(双端队列)的理解