Queue

Queue

The process of inserting an element on one end and deleting an element on the other end.

A logically First-in-First-out (FIFO).

It is a homogenous collection of elements in which new elements are added at one end called rear, and the existing elements are deleted from the other end called front.

Queue Operation

enqueue
Insert (or add) an element to the queue (push). If we try to push (or insert or add) an element to queue where the size of an array is reach, overflow occurs. When queue is full it is naturally not possible to insert any more elements

dequeue
Delete (or remove) an element from a queue (pop). If we try to pop (or delete or remove) an element from queue when it is empty, underflow occurs. It is not possible to delete (or take out) any element when there is no element in the queue.

Other Queues

• Circular queue
• Double-ended queue (Deque)
• Priority queue (can be done using linked list)

Queue CODES

Using Standard Library (QUEUE)

Program 1

//queue library
#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> grade;
	char quest;
	int n;
	cout << "Enter data y/n?";
	cin >> quest;
	while(quest=='Y' || quest=='y')
	{
		cout << "Enter integer data ";
		cin >> n;
		grade.push(n);
		
		cout << "Enter data y/n?";
		cin >> quest;
	}
	cout << endl;
	cout << "front element " << grade.front() << endl;
	cout << "last element " << grade.back() << endl;
	cout << "size of queue " << grade.size() <<endl;
	
	while(!grade.empty())
	{
		cout << grade.front() <<endl;
		grade.pop();
	}
	cout << "size of queue " << grade.size() <<endl;

	cin.ignore().get();
	return 0;

}

Program 2

//queue
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
	queue<string> students;
	string studname;
	char quest;
	cout << "Do you want to enter data y/n? ";
	cin >> quest;
	while (quest =='Y' || quest=='y')
	{
		cout  << "enter data for queue ";
		cin >> studname;
		students.push(studname);
		cout << "Do you want to enter data y/n? ";
		cin >> quest;
	}
	cout <<  endl;
	cout << "front data " << students.front() << endl; //front
	cout << "back data " << students.back() << endl; // rear
	cout << "queue size " << students.size() << endl;
	while (!students.empty()) 
	{
		cout << "popped data " << students.front() << endl;
		students.pop();
	}
	cout << "queue size " << students.size() << endl;
	cin.ignore().get();
	return 0;
	
}

Program 3

#include <iostream>
#define QUEUE_SIZE 5
using namespace std;

int queueArr[QUEUE_SIZE];
void dequeue();
void enqueue(int);
void display();
int front=-1;
int rear=-1;

int main()
{
	while(1)
	{
		int choice;
		system("clear");
		cout << "[1] - Enqueue\n";
		cout << "[2] - Dequeue\n";
		cout << "[3] - Display\n";
		cout << "[4] - Exit\n";
		cout << "===================\n";
		cout << "Enter your choice: ";
		cin >> choice;
		switch(choice){
			case 1: 
				int num;
				cout << "Enter a number to enqueue: ";
				cin >> num;
				enqueue(num);	
				display();
				break;
			case 2:
				dequeue();		
				break;
			case 3:
				display();
				break;
			case 4:
				exit(1);
			default:
				cout << "\nWrong choice!\n";
		}
		cout << endl;
		cin.ignore().get();
	}
	
	return 0;
}

void display()
{
	if(rear==-1 || front>rear)
		cout << "Queue is empty!";
	else
		for(int i=front; i<=rear; i++)
			cout << "[" << i << "] : " <<queueArr[i] << endl;
}

void enqueue(int n)
{
	if(rear<QUEUE_SIZE-1)
	{
		if(front==-1)
			front++;
		queueArr[++rear]=n;	
	}
	else
		cout << "Queue is overflow!";
}

void dequeue()
{
	if(rear<front || front==-1)
	{
		cout << "Queue is empty!";
		front=0;
		rear=-1;
	}
	else
		cout << "Dequeue value is " << queueArr[front++];
}

Program 4

#include <iostream>
#include <queue>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
    queue<int> q;
    int choice, item;
    while (1)
    {
        cout<<"\n---------------------"<<endl;
        cout<<"Queue Implementation in Stl"<<endl;
        cout<<"\n---------------------"<<endl;
        cout<<"1.Insert "<<endl;
        cout<<"2.Delete "<<endl;
        cout<<"3.Size of the Queue"<<endl;
        cout<<"4.Front Element "<<endl;
        cout<<"5.Last Element ]"<<endl;
        cout<<"6.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter value to be inserted: ";
            cin>>item;
            q.push(item);
            break;
        case 2:
            item = q.front();
            q.pop();
            cout<<"Element "<<item<<" Deleted"<<endl;
            break;
        case 3:
	    cout<<"Size of the Queue: ";
	    cout<<q.size()<<endl;
            break;
        case 4:
            cout<<"Front Element of the Queue: ";
	    cout<<q.front()<<endl;
            break;
        case 5:
            cout<<"Back Element of the Queue: ";
            cout<<q.back()<<endl;
            break;
        case 6:
            exit(1);
	    break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

Queue using User defined function (Array Implementation)

Program 5

#include <iostream>
#define QUEUE_SIZE 5
using namespace std;

int queueArr[QUEUE_SIZE];
void dequeue();
void enqueue(int);
void display();
int front=-1;
int rear=-1;

int main()
{
	while(1)
	{
		int choice;
		system("clear");
		cout << "[1] - Enqueue\n";
		cout << "[2] - Dequeue\n";
		cout << "[3] - Display\n";
		cout << "[4] - Exit\n";
		cout << "===================\n";
		cout << "Enter your choice: ";
		cin >> choice;
		switch(choice){
			case 1: 
				int num;
				cout << "Enter a number to enqueue: ";
				cin >> num;
				enqueue(num);	
				display();
				break;
			case 2:
				dequeue();		
				break;
			case 3:
				display();
				break;
			case 4:
				exit(1);
			default:
				cout << "\nWrong choice!\n";
		}
		cout << endl;
		cin.ignore().get();
	}
	
	return 0;
}

void display()
{
	if(rear==-1 || front>rear)
		cout << "Queue is empty!";
	else
		for(int i=front; i<=rear; i++)
			cout << "[" << i << "] : " <<queueArr[i] << endl;
}

void enqueue(int n)
{
	if(rear<QUEUE_SIZE-1)
	{
		if(front==-1)
			front++;
		queueArr[++rear]=n;	
	}
	else
		cout << "Queue is overflow!";
}

void dequeue()
{
	if(rear<front || front==-1)
	{
		cout << "Queue is empty!";
		front=0;
		rear=-1;
	}
	else
		cout << "Dequeue value is " << queueArr[front++];
}

Queue using User defined function (Linked List Implementation)

////Program: Queue using linked list
#include <iostream>
#include <iomanip>
using namespace std;

struct node{
	int data;
	node *next;
};//*front,*rear;

void dequeue();
void enqueue(int);
void display();
node *front=NULL;		//head
node *rear=NULL;		//tail

int main()
{
	while(1)
	{
		int choice;
		system("clear");
		cout << "QUEUE USING LINKED LIST\n";
		cout << "[1] - Enqueue\n";
		cout << "[2] - Dequeue\n";
		cout << "[3] - Display\n";
		cout << "[4] - Exit\n";
		cout << "===================\n";
		cout << "Enter your choice: ";
		cin >> choice;
		switch(choice){
			case 1: 
				int num;
				cout << "Enter a number to enqueue: ";
				cin >> num;
				enqueue(num);	
				display();
				break;
			case 2:
				dequeue();	
				display();
				break;
			case 3:
				display();
				break;
			case 4:
				exit(1);
			default:
				cout << "\nWrong choice!\n";
		}
		cout << endl;
		cin.ignore().get();
	}
	
	return 0;
}

void display()
{
	node *p;
	if(front==NULL)
		cout << "Nothing to display!\n";
	else
	{
		cout << "Stack elements:\n";
		cout << setw(10) << "POINTER" << setw(10) << "VALUE" << setw(20) << "NEXT" << endl;
		p=front;
		while(p != NULL)
		{
			cout << setw(10) << p 
				<< setw(10) << p->data 
				<< setw(20) << p->next 
				<< endl;
			p = p->next;
			
		}
	}
}

void enqueue(int n)
{
	node *tmp = new node;
	tmp->data = n;
	tmp->next = NULL;
	if(front==NULL)
	{
		front = tmp;	
		rear = tmp;
		return;
	}
	rear->next=tmp;
	rear=tmp;
}

void dequeue()
{
	node *tmp;
	tmp=front;
	if(front!=NULL)
	{
		cout << "You dequeue value " << front->data << endl;
		front=front->next;
		delete(tmp);
	}
	else
		cout << "Queue is empty!\n";
}

Queue (OOP Implementation)

IntQueue.h

class IntQueue
{
	private:
		int *queueArray;
		int queueSize;
		int front;
		int rear;
		int numItems;
	public:
	IntQueue(int);
	~IntQueue();
	void enqueue(int);
	void dequeue(int &);
	bool isEmpty();
	bool isFull();
	void clear();
};

IntQueue.cpp

#include <iostream>
#include "IntQueue.h"
using namespace std;

// Constructor
	IntQueue::IntQueue(int s)
	{
		queueArray = new int[s];
		queueSize = s;
		front = 1;
		rear = 1;
		numItems = 0;
	}

// Destructor
	IntQueue::~IntQueue(){
		delete [] queueArray;
	}


//********************************************
// Function enqueue inserts the value in num
// at the rear of the queue.

void IntQueue::enqueue(int num)
{
	if (isFull())
		cout << "The queue is full.\n";
	else
		// Calculate the new rear position
	rear = (rear + 1 ) % queueSize;
	// Insert new item
	queueArray[rear] = num;
	// Update item count
	numItems++;
}

//*********************************************
// Function dequeue removes the value at the
// front of the queue, and copies t into num.
void IntQueue::dequeue(int &num)
{
	if (isEmpty())
		cout << "The queue is empty.\n";
	else
		{
		// Move front
		front = (front + 1 ) % queueSize;
		// Retrieve the front item
		num = queueArray[front];
		// Update item count
		numItems--;
		}
}

//*********************************************
// Function isEmpty returns true if the queue
// is empty, and false otherwise.
bool IntQueue::isEmpty() {
	bool status;

	if (numItems)
		status = false;
	else
		status = true;
	return status;

}

//********************************************
// Function isFull returns true if the queue
// is full, and false otherwise.
bool IntQueue::isFull(){
	bool status;
	
	if (numItems < queueSize)
		status = false;
	else
		status = true;
	return status;
}

//*******************************************
// Function clear resets the front and rear
// indices, and sets numItems to 0.
void IntQueue::clear(){
	front = queueSize -1;
	rear = queueSize -1;
	numItems = 0;

}

Main.cpp

// This program demonstrates the IntQeue class
#include <iostream>
#include "IntQueue.h"
using namespace std;

int main(){
	IntQueue iQueue(5);
	cout << "Enqueuing 5 items...\n";
	// Enqueue 5
	for (int x = 0; x <5; x++)
		iQueue.enqueue(x); //0-4
	
	for (int x=0; x<5;x++)
		cout << x;
	
	// Attempt to enqueue a 6th
	cout << "Now attempting to enqueue again...\n";
	iQueue.enqueue(5);
	
	// Deqeue and retrieve all items in the queue
	
	cout << "The values in the queue were:\n";
	while (!iQueue.isEmpty())
		{
			int value;
			iQueue.dequeue(value);
				cout << value << endl;
		}	
	return 0;
}