Yashb | Deque

Deque

  • by Warawreh
  • Last updated: 2022-02-06 10:31:46
  • Estimated time to read: 10 minutes


Deque

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:
  1. Add Left 5
  2. Add Left 3
  3. Remove Right
  4. Add Right 4
  5. Get Left
  6. Get Right
  7. Add Left 8
  8. Get Left
  9. Add Right 4
  10. Remove Right
      Deque
      Deque
      (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)

      Deque
      Deque
      (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)

      Deque
      Deque
      (3) The third operation is a Remove Right operation so the item in the right is removed (5)

      Deque
      Deque
      (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)

      Deque
      (5) The fifth operation is a Get Left operation and the result is 3 (item in the front)

      Deque
      (6) The sixth operation is a Get Right operation and the result is 4 (item in the back)

      Deque
      Deque
      (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)

      Deque
      (8) The eighth operation is a Get Left operation and the result is 8 (item in the front)

      Deque
      Deque
      (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)

      Deque
      Deque
      (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



      Table of contents