Yashb | Queue

Queue

  • by Warawreh
  • Last updated: 2022-02-03 12:28:46
  • Estimated time to read: 10 minutes


Queue

Defenition

A queue is an STL used to store and load items using the FIFO System (First in first out), which means items can be added to the end of the queue, and only the items in the front can be accessed (the items that were first added), We can also look at the queue as a line in a shop where the first person arrives is the first person served.

In the queue, 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".

Queue Operations

There are some operations used in the queue to add new items, access items in the queue, and remove items:
  • Add: insert a new item to the right end of the queue (the back).
  • Remove: delete the first item added to the queue (the item in the front).
  • Get: returns the first item added to the queue (the item in the front).
All operations supported by the queue have time complicity of O(1) so the overall complexity of the queue is O(1) the space complicity of the queue is O(n) where n is the number of items.

Example on Queue

Let's observe how the queue works when we apply the following operations in the same order they were given:
  1. Add 2
  2. Add 3
  3. Get
  4. Add 0
  5. Remove
  6. Add 1
  7. Remove
  8. Get
Queue
Queue
(1) In the beginning the queue  is empty, after the first operation 2 will be added to the back of the queue
(now the 2 is in the front and also in the back of the queue since it is the only item)

Queue
Queue
(2) After the second operation 3 will be added to the back of the queue
(now the 2 is in the front and 3 is in the back)

Queue
(3) The third operation is a Get operation and the result is the item in the front (2)

Queue
Queue
(4) The fourth operation is an Add 0 operation so 0 is added to the back of the queue
(now the 2 is in the front and 0 is in the back)

Queue
Queue
(5) The fifth operation is a Remove operation so the item at the front of the queue is removed

Queue
Queue
(6) The Sixth operation is an Add 1 operation so 1 is added to the back of the queue

Queue
Queue
(7) The seventh operation is a Remove operation so the item at the front of the queue is removed

Queue
(8) The eighth operation is a Get operation and the result is the item in the front (0)


Queue Implementation

#include <iostream> #include <queue>//queue header using namespace std; int main(){ /* In C++: push: is used to add items to the queue pop: is used to remove the first item in the queue front: is used to get the item in the front of the queue */ //Create an empty queue queue<int> items; //Add 2 items.push(2); //2 is added to the end of the queue //items = 2 <- item in the back //Add 3 items.push(3); //items = 2, 3 <- item in the back //Get cout << "Item on front is: " << items.front() << endl; //Prints the item in the back of the queue (2) //Add 0 items.push(0); //items = 2, 3, 0 <- item in the back //Remove items.pop(); //Removes the item in the front of the queue (2) //items = 3, 0 <- item in the back //Add 1 items.push(1); //items = 3, 0, 1 <- item in the back //Remove items.pop(); //Removes the item in the front of the queue (3) //items = 0, 1 <- item in the back //Get cout << "Item on front is: " << items.front() << endl; //Prints the item in the back of the queue (0) }
Output:

Item on front is: 2
Item on front is: 0




Table of contents