12.4. The deque class¶
The deque (double-ended queue) is an indexed sequence container that
allows fast insertion and deletion at both its beginning and its end.
In addition,
insertion and deletion at either end of a deque never invalidates pointers
or references to the rest of the elements.
It’s primary role in the standard library is to function as
the default container underlying std::stack and std::queue.
1#include <iostream>
2#include <deque>
3#include <string>
4
5using std::cout;
6using std::deque;
7using std::string;
8
9void print (const deque<string>& container)
10{
11 cout << "\n\nItems in the Deque: \n";
12 for (const auto& value: container) {
13 cout << value << " ";
14 }
15 cout << '\n';
16
17}
18
19int main() {
20 deque<string> d;
21 cout << "Deque Empty? " << d.empty() << endl;
22 d.push_back("Zebra");
23 cout << "Deque Empty? " << d.empty() << endl;
24
25 d.push_front("Turtle");
26 d.push_front("Panda");
27 d.push_back("Catfish");
28 d.push_back("Giraffe");
29
30 cout << "Deque Size: " << d.size() << endl;
31 cout << "Item at the front: " << d.front() << endl;
32 cout << "Item at the back: " << d.back() << endl;
33
34 print (d);
35
36 d.pop_back();
37 d.pop_front();
38
39 cout << endl << "\nItem at the front: " << d.front();
40 cout << "\nItem at the back: " << d.back();
41 cout << "\nDeque Size: " << d.size();
42
43 print (d);
44
45 return 0;
46}
47
48
An interesting problem that can be easily solved using the deque data structure is the classic palindrome problem. A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. We would like to construct an algorithm to input a string of characters and check whether it is a palindrome.
One solution to this problem uses a deque to store the characters of the string. First store each character in the string into a new deque. Using the properties of the deque, we can process the characters from both ends and compare them to each other.
Since we can remove both of them directly, we can compare them and continue only if they match. If we can keep matching first and the last items, we will eventually either run out of characters or be left with a deque of size 1 depending on whether the length of the original string was even or odd. In either case, the string must be a palindrome.
1#include <deque>
2#include <iostream>
3#include <string>
4
5using std::deque;
6using std::string;
7
8bool check_palindrome(const string& value) {
9 if (value.size() < 2) return true;
10 deque<char> letters (value.begin(), value.end());
11
12 while (letters.size() > 1) {
13 char first = letters.front(); // could omit these temporaries
14 char last = letters.back();
15 if (first != last) {
16 return false;
17 }
18 letters.pop_front();
19 letters.pop_back();
20 }
21 return true;
22}
A moment of full disclosure: even though it is possible to use a deque to determine if a string is a palindrome or not, it’s far from the simplest or most efficient solution tot he the problem. Simply checking the string characters directly is better:
1#include <algorithm>
2#include <iostream>
3#include <string>
4
5bool is_palindrome(const std::string& value) {
6 return equal(value.begin(),
7 value.begin() + value.size()/2,
8 value.rbegin());
9}
The STL provides the equal template which allows comparing the values in a pair ranges.
The first begin and end define a range of values to be compared. The second begin defines the start of the second range of values. The second end does not need to be specified, because the comparison stops once the first end is reached.
Notice that in this example, the second begin is rbegin. This means the second iterator starts at the reverse beginning, which is the end of the string and each iteration moves one step closer to the begining.
While this solution does require more familiarity with the standard library, it avoids copying the string into the container, removing elements from the container, and is generally simpler.
More to Explore
STL deque class