StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Sunday, July 13, 2008

C++ Queues

 July 13, 2008     Data Structures     No comments   

This article explains the queue data structure and demonstrates sample implementation using C++.

Queue Introduction

  • Queue is a first-in, first-out (FIFO) data structure. i.e. the element added first to the queue will be the one to be removed first.
  • Elements are always added to the back of the queue and removed from the front of the queue.
  • Typical use cases of queues include:- (1) In Inter-Process Communication (IPC) message queues is a common mechanism for communication between processes.
  • Some of the common terminology associated with queues inlcude ADD/ PUSH and DELETE/ POP of elements to the queue.
  • ADD/ PUSH refers to adding an element to the queue.
  • DELETE/ POP refers to removing an element from the queue.
  • Diagram below explains the queue.

Implementation of a simple queue using arrays

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX_SIZE = 100;

class QueueOverFlowException
{
public:
   QueueOverFlowException()
   {
       cout << "Queue overflow" << endl;
   }
};

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class ArrayQueue
{  
private:
   int data[MAX_SIZE];
   int front;
   int rear;
public:
   ArrayQueue()
   {
       front = -1;
       rear = -1;
   }      
 
   void Enqueue(int element)
   {
       // Don't allow the queue to grow more
       // than MAX_SIZE - 1
       if ( Size() == MAX_SIZE - 1 )                 
           throw new QueueOverFlowException();

       data[rear] = element;

       // MOD is used so that rear indicator
       // can wrap around
       rear = ++rear % MAX_SIZE;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = data[front];

       // MOD is used so that front indicator
       // can wrap around
       front = ++front % MAX_SIZE;

       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return data[front];
   }
 
   int Size()
   {
       return abs(rear - front);
   }
 
   bool isEmpty()
   {
       return ( front == rear ) ? true : false;
   }
};

int main()
{  
   ArrayQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

Implementation of a simple queue using linked lists

#include <iostream>
using namespace std;

class QueueEmptyException
{
public:
   QueueEmptyException()
   {
       cout << "Queue empty" << endl;
   }
};

class Node
{
public:
   int data;
   Node* next;
};

class ListQueue
{  
private:
   Node* front;
   Node* rear;
   int count;

public:
   ListQueue()
   {
       front = NULL;
       rear = NULL;
       count = 0;
   }      
 
   void Enqueue(int element)
   {
       // Create a new node
       Node* tmp = new Node();
       tmp->data = element;
       tmp->next = NULL;

       if ( isEmpty() ) {
           // Add the first element
           front = rear = tmp;
       }
       else {
           // Append to the list
           rear->next = tmp;
           rear = tmp;
       }

       count++;
   }      

   int Dequeue()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       int ret = front->data;
       Node* tmp = front;

       // Move the front pointer to next node
       front = front->next;

       count--;
       delete tmp;
       return ret;   
   }      
 
   int Front()
   {          
       if ( isEmpty() )
           throw new QueueEmptyException();

       return front->data;
   }
 
   int Size()
   {
       return count;
   }

   bool isEmpty()
   {
       return count == 0 ? true : false;
   }
};

int main()
{  
   ListQueue q;
   try {
       if ( q.isEmpty() )
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);

       // Size of queue
       cout << "Size of queue = " << q.Size() << endl;

       // Front element
       cout << q.Front() << endl;

       // Dequeue elements
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
       cout << q.Dequeue() << endl;
   }
   catch (...) {
       cout << "Some exception occured" << endl;
   }
}

OUTPUT:-
Queue is empty
Size of queue = 3
100
100
200
300

Queue library usage in standard template library (STL)

#include <iostream>
#include <queue>
using namespace std;

int main()
{
   queue<int> q;
   q.push(100);
   q.push(200);
   q.push(300);
   q.push(400);

   cout << "Size of the queue: " << q.size() << endl;

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   cout << q.front() << endl;
   q.pop();

   if ( q.empty() ) {
   cout << "Queue is empty" << endl;
   }
}
OUTPUT:-
Size of the queue: 4
100
200
300
400
Queue is empty
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk