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;
}