首页 > 代码库 > STL容器:deque双端队列学习

STL容器:deque双端队列学习

  所谓deque,是"double-ended queue"的缩写;
  它是一种动态数组形式,可以向两端发展,在尾部和头部插入元素非常迅速;
  在中间插入元素比较费时,因为需要移动其它元素;(No)
  双端队列容器,在序列的两端放置和删除元素是高效的;
  而vector只是在序列末尾插入才是高效的。

 技术分享

 

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
/* strdeque.cpp
    所谓deque,是"double-ended queue"的缩写;
    它是一种动态数组形式,可以向两端发展,在尾部和头部插入元素非常迅速;
    在中间插入元素比较费时,因为需要移动其它元素;(No)
    双端队列容器,在序列的两端放置和删除元素是高效的;
    而vector只是在序列末尾插入才是高效的。
*/


#include <iostream>
#include <deque>

using namespace std;

int main(void)
{
    
//push_front();
    //push_back();
    //pop_front();
    //pop_back();
    deque<int> d;
    d.push_back(
1);
    d.push_back(
2);
    d.push_back(
3);
    d.push_front(
0);
    
for (int i = 0; i < d.size(); i++)
    {
        cout << 
"d[" << i << "] = " << d[i] << endl;
    }
    d.pop_front();
    d[
1] = 23;
    
for (int i = 0; i < d.size(); i++)
    {
        cout << 
"d[" << i << "] = " << d[i] << endl;
    }

    
//迭代器遍历
    typedef deque<int>::iterator PITER;
    
for (PITER piter = d.begin(); piter != d.end(); piter++)
    {
        cout << *piter << endl;
    }

    
//大小度量
    cout << d.size() << endl;
    d.resize(
1023);
    cout << d.size() << endl;
    cout << d.max_size() << endl;

    
//返回函数
    //begin front rbegin 下同
    //end back rend
    PITER pIter = d.begin();
    cout << 
"The first element is " << *pIter << endl;
    *pIter = 
55;
    pIter = d.begin();
    cout << 
"The first element is " << *pIter << endl;
    
int &nRet = d.front();
    cout << 
"The first element is " << nRet << endl;

    
typedef deque<int>::reverse_iterator PREVITER;
    PREVITER pRevIter = d.rbegin();
    cout << 
"The last element is " << *pRevIter << endl;

    
//判断是否为空
    if (d.empty())
    {
        cout << 
"empty" << endl;
    }

    
//deque访问
    deque<char> dchar;
    dchar.push_back(
‘A‘);
    dchar.push_back(
‘B‘);
    dchar.push_back(
‘C‘);
    dchar.push_back(
‘D‘);
    
for (int i = 0; i < dchar.size(); i++)
    {
        cout << dchar.at(i) << 
" ";
    }
    cout << endl;

    
//deque重置技术
    deque<char> dchar2;
    dchar2.push_back(
‘a‘);
    dchar2.push_back(
‘b‘);
    dchar2.push_back(
‘c‘);
    dchar2.push_back(
‘d‘);
    dchar.assign(dchar2.begin(), dchar2.end());
    
for (int i = 0; i < dchar.size(); i++)
    {
        cout << dchar.at(i) << 
" ";
    }
    cout << endl;

    
//容器内容交换
    deque<int> d1(31);
    
for (int i = 0; i < d1.size(); i++)
    {
        cout << d1.at(i) << 
" ";
    }
    cout << endl;
    deque<
int> d2(310);
    d1.swap(d2);
    
for (int i = 0; i < d1.size(); i++)
    {
        cout << d1.at(i) << 
" ";
    }
    cout << endl;

    
//deque插入和删除技术
    deque<int> dInsert(556);
    
for (int i = 0; i < dInsert.size(); i++)
    {
        cout << dInsert.at(i) << 
" ";
    }
    cout << endl;
    dInsert.insert(dInsert.end(), 
50);
    
for (int i = 0; i < dInsert.size(); i++)
    {
        
//cout << dInsert.at(i) << " ";
        cout << dInsert[i] << " ";
    }
    cout << endl;

    
//erase操作
    //注意:尽量少用erase(pos)和erase(beg,end)
    /*
    deque<int> dErase(3, 7);
    dErase.erase(dErase.end());
    for (PITER p = dErase.begin(); p != dErase.end(); p++)
    {
        cout << *p << " ";
    }
    cout << endl;
    */


    
//clear操作
    deque<int> dClear(3100);
    
for (PITER p = dClear.begin(); p != dClear.end(); p++)
    {
        cout << *p << 
" ";
    }
    cout << endl;
    dClear.clear();
    
if (dClear.empty())
    {
        cout << 
"empty it!" << endl;
    }

    
//除此之外还有关系运算符
    // == > >= < <=等等 操作省略

    cin.get();
    
return 0;
}

技术分享

 

STL容器:deque双端队列学习