Table of contents
Defenition
Deque is an STL used to store and load items, which supports adding items to both ends (left end and right end), getting items at both ends, and removing items from both ends, we also can look at the deque as a two-way tube, if you look from the left side you can only see the leftmost item and if you look from the right you only see the rightmost item.
In deque, the operations are done on both ends of the queue the left end which is usually referred to as "front" and the right end usually referred to as "back".
Deque Operations
There are some operations used in deque to add new items, access items in the deque, and remove items:
- Add Right: insert a new item to the right end of the deque (the back).
- Add Left: insert a new item to the left end of the deque (the front).
- Remove Right: delete the item at the right end of the deque (the item in the back).
- Remove Left: delete the item at the left end of the deque (the item in the front).
- Get Right: returns the item at the right end of the deque (the item in the back).
- Get Left: returns the item at the left end of the deque (the item in the front);
All operations supported by the deque have time complicity of O(1) so the overall complexity of the deque is O(1) the space complicity of the deque is O(n) where n is the number of items.
Example on Deque
Let's observe how the deque works when we apply the following operations in the same order they were given:
- Add Left 5
- Add Left 3
- Remove Right
- Add Right 4
- Get Left
- Get Right
- Add Left 8
- Get Left
- Add Right 4
- Remove Right
(1) In the beginning the deque is empty, after the first operation 5 will be added to the front of the deque
(now the 5 is in the front and also in the back of the deque since it is the only item)
(2) After the second operation 3 will be added to the front of the deque
(now the 3 is in the front and 5 is in the back)
(3) The third operation is a Remove Right operation so the item in the right is removed (5)
(4) The fourth operation is an Add Right 4 operation so 4 is added to the back of the deque
(now the 3 is in the front and 4 is in the back)
(5) The fifth operation is a Get Left operation and the result is 3 (item in the front)
(6) The sixth operation is a Get Right operation and the result is 4 (item in the back)
(7) The seventh operation is an Add Left 8 operation so 8 is added to the front of the deque
(now the 8 is in the front and 4 is in the back)
(8) The eighth operation is a Get Left operation and the result is 8 (item in the front)
(9) The ninth operation is an Add Right 4 operation so 4 is added to the back of the deque
(now the 8 is in the front and 4 is in the back)
(10) The tenth operation is a Remove Right operation so the item in the right is removed (4)
(now the 8 is in the front and 4 is in the back)
Queue Implementation
#include <iostream>
#include <deque>//deque header
using namespace std;
int main(){
/*
In C++:
push_front(): is used to add items to the front of the deque
push_back(): is used to add items to the back of the deque
pop_front(): is used to remove items to the front of the deque
pop_back(): is used to remove items to the back of the deque
front(): is used to return the item in the front of the deque
back(): is used to return the item in the back of the deque
*/
//Create an empty deque
deque<int> items;
//Add Left 5
items.push_front(5);
//5 is added to the front of the deque
//items = 5 <- item in the front and back
//Add Left 3
items.push_front(3);
//items = 3, 5 <- item in the back
//Remove Right
items.pop_back();
//items = 3 <- item in the front and back
//Add Right 4
items.push_back(4);
//4 is added to the back of the deque
//items = 3, 4 <- item in the back
//Get Left
cout << "Item on front is: " << items.front() << endl;
//Prints the item in the front of the deque (3)
//Get Right
cout << "Item on back is: " << items.back() << endl;
//Prints the item in the back of the deque (4)
//Add Left 8
items.push_front(8);
//items = 8, 3, 4 <- item in the back
//Get Left
cout << "Item on front is: " << items.front() << endl;
//Prints the item in the front of the deque (8)
//Add Right 4
items.push_back(4);
//4 is added to the back of the deque
//items = 8, 3, 4, 4 <- item in the back
//Remove Right
items.pop_back();
//items = 8, 3, 4 <- item in the back
}
Output:
Item on front is: 3
Item on back is: 4
Item on front is: 8