Queue

Go back

Introduction

The queue data structure follows the FIFO (First In First Out) principle where elements that are added first will be removed first. Queues use an encapsulated object of deque or list as its underlying container, providing a specific set of member functions to access its elements.

Advantages

Fast insertion, deletion and access operations.
Useful when a particular service is used by multiple consumers.
Can be used in the implementation of other data structures.
Can be used to solve problems that work with recursion (e.g. BFS Algorithm).

Disadvantages

Limited number of methods.
Random access of elements is impossible in queues.

Using queue with DTL

Initializing a queue

Implementation using an array:

#include "queue.hpp"
#include <iostream>

int main() {
  // Static
  dby::Queue<int> staArrQueue(5); // MAX CAPACITY = 5

  // Pointer
  dby::Queue<int>* ptrArrQueue = new dby::Queue<int>(5); // MAX CAPACITY = 5
  delete ptrArrQueue;

  return 0;
}

Implementation using a linked list:

#include "queue.hpp"
#include <iostream>

int main() {
  // Static
  dby::Queue<int> staListQueue; 

  // Pointer
  dby::Queue<int>* ptrListQueue = new dby::Queue<int>();
  delete ptrListQueue;

  return 0;
}

Queue methods

Exclusive of array implementation

max_size(): Returns the max size of the queue.
full(): Returns whether the queue is full or not.

Both implementations

size(): Returns the current size of the queue.
empty(): Returns whether the queue is empty or not.
front(): Returns a reference to the first element of the queue.
back(): Returns a reference to the last element of the queue.
push(T data): Adds the element 'data' at the end of the queue.
pop(): Deletes the first element of the queue.
extract(): Returns and deletes the first element of the queue.
reverse(): Reverses the order of the elements in the queue.