C++stl中的双向队列

ゝ一世哀愁。 2022-05-18 06:15 246阅读 0赞

deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，![0_1320717883Pm54.gif][]

deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》，当然此书中使用的SGI STL与VS2008所使用的PJ STL的实现方法还是有区别的。下面给出了deque的结构图：

![0_13207172099IU6.gif][]

由于篇幅问题，deque的实现细节就不再深入了，下面给出deque的使用范例：

//双向队列 deque
    
    //by MoreWindows http://blog.csdn.net/morewindows
    
    #include <deque>
    
    #include <cstdio>
    
    #include <algorithm>
    
    using namespace std;
    
    int main()
    
    {
    
    deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0
    
    deque<int>::iterator pos;
    
    int i;
    
    
    //使用assign()赋值 assign在计算机中就是赋值的意思
    
    for (i = 0; i < 20; ++i)
    
    ideq[i] = i;
    
    
    //输出deque
    
    printf("输出deque中数据:\n");
    
    for (i = 0; i < 20; ++i)
    
    printf("%d ", ideq[i]);
    
    putchar('\n');
    
    
    //在头尾加入新数据
    
    printf("\n在头尾加入新数据...\n");
    
    ideq.push_back(100);
    
    ideq.push_front(i);
    
    
    //输出deque
    
    printf("\n输出deque中数据:\n");
    
    for (pos = ideq.begin(); pos != ideq.end(); pos++)
    
    printf("%d ", *pos);
    
    putchar('\n');
    
    
    //查找
    
    const int FINDNUMBER = 19;
    
    printf("\n查找%d\n", FINDNUMBER);
    
    pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
    
    if (pos != ideq.end())
    
    printf("find %d success\n", *pos);
    
    else
    
    printf("find failed\n");
    
    
    //在头尾删除数据
    
    printf("\n在头尾删除数据...\n");
    
    ideq.pop_back();
    
    ideq.pop_front();
    
    
    //输出deque
    
    printf("\n输出deque中数据:\n");
    
    for (pos = ideq.begin(); pos != ideq.end(); pos++)
    
    printf("%d ", *pos);
    
    putchar('\n');
    
    return 0;
    
    }

运行结果如下：

![0_1320717228QV1x.gif][]

另外要注意一点。对于deque和vector来说，尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动，从而使效率低下。

在给出一个实例：

### 双向队列 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

Problem Description

想想双向链表……双向队列的定义差不多，也就是说一个队列的队尾同时也是队首；两头都可以做出队，入队的操作。  
现在给你一系列的操作，请输出最后队列的状态；  
命令格式：  
LIN X X表示一个整数，命令代表左边进队操作；  
RIN X 表示右边进队操作；  
ROUT  
LOUT 表示出队操作；

Input

第一行包含一个整数M(M<=10000)，表示有M个操作；  
以下M行每行包含一条命令；  
命令可能不合法，对于不合法的命令，请在输出中处理；

Output

输出的第一行包含队列进行了M次操作后的状态，从左往右输出，每两个之间用空格隔开；  
以下若干行处理不合法的命令（如果存在）；  
对于不合法的命令，请输出一行X ERROR  
其中X表示是第几条命令；

Example Input

8
    LIN 5
    RIN 6
    LIN 3
    LOUT
    ROUT
    ROUT
    ROUT
    LIN 3

Example Output

3
    7 ERROR

代码如下：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n;
        deque<int>q;
    int ss[100001];
    int k = 0;
        cin>>n;
        for(int i = 1; i <= n; i++)
        {
            char a[10];
          scanf("%s",a);
    
            if(strcmp(a,"LIN") == 0)
            {
                int key;
                cin>>key;
                q.push_front(key);//在头部插入一个元素；
            }
            else if(strcmp(a,"RIN") == 0)
            {
                int key;
                cin>>key;
                q.push_back(key);//在队列尾部插入一个元素；
            }
            else if(strcmp(a,"ROUT") == 0)//队列右边出队；
            {
                if(!q.empty())
                    q.pop_back();
                else
                    ss[k++] = i;
            }
            else if(strcmp(a,"LOUT")== 0)//队列左边出队；
            {
                if(!q.empty())
                    q.pop_front();
                else
                    ss[k++] = i;
            }
            else
                ss[k++] = i;
        }
    
        deque<int>::iterator it;
    
        for(it = q.begin(); it != q.end(); it++)
        {
            if(it != q.begin())
                cout<<" ";
            cout<<*it;
        }
        cout<<endl;
    
        for(int i = 0; i < k; i++)
        {
            cout<<ss[i]<<" "<<"ERROR"<<endl;
        }
    
        return 0;
    }

转载请标明出处，原文地址：[http://blog.csdn.net/morewindows/article/details/6946811][http_blog.csdn.net_morewindows_article_details_6946811]

[0_1320717883Pm54.gif]: /images/20220518/3985fcce50724b209b81d69d635f8067.png
[0_13207172099IU6.gif]: /images/20220518/8f1b4813ea82413e921bd4209cb60f62.png
[0_1320717228QV1x.gif]: /images/20220518/fb732941217349f4a49b9b2914653fec.png
[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2204/pid/1466.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2204/pid/1466.html
[http_blog.csdn.net_morewindows_article_details_6946811]: http://blog.csdn.net/morewindows/article/details/6946811