Queue implementation using C++

Written by

Sonal Moga

Let’s review queue and understand its implementation now. As we already discussed that queue are also abstract data type data structures following FIFO (First-In-First-Out) principle. A queue is similar to a checkout line at a bus stand. The first one in the line will also be the first one to move out after being issued a bus ticket.

Let’s look at the sample program to understand the Insertion, deletion and traverse the elements of the queue.

//the program shows the basic operations performed on a queue
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>

// declares a queue structure

struct node

{

char data;

node * link;

};

//functions to add, delete and show queue

node* add_Q(node *rear, char value); //add queue

node* del_Q(node *front, char &value); //delete queue

void show_Q(node *front);

//main program

void main()

{

node *front, *rear;

char value;

int choice;

char option = ’Y’;

front = rear = NULL;

clrscr();

do

{

	cout &lt;&lt; ”\n Main Menu”;

	cout &lt;&lt; ”\n Adding in Queue”;

	cout &lt;&lt; ”\n Delete from Queue”;

	cout &lt;&lt; ”\n Traverse the queue”;

	cout &lt;&lt; ”\n Exit Main Menu”;

	cout &lt;&lt; ”\n Enter a choice from Main Menu”;

	cin &gt;&gt; choice;

	switch (choice)

	{

		case 1:

			do

			{

				cout &lt;&lt; ”Enter the item to be added to the queue”;

				cin &gt;&gt; value;

				rear = add_Q(rear, value);

				if (front == NULL)

					front = rear;

				cout &lt;&lt; ”\n Add more element &lt; Y / N &gt; ? ”;

				cin &gt;&gt; option;
			} while (toupper(option) == ’Y’);

			break;

		case 2:

			option = ’Y’;

			do

			{

				front = del_Q(front, value);

				if (front == NULL)

					rear = front;

				if (value != -1)

					cout &lt;&lt; ”\n Item deleted from queue is”;

				cout &lt;&lt; ”\n Delete more items from the queue&lt; Y / N &gt; ? ”;

				cin &gt;&gt; option;
			} while (toupper(opt) == ’Y’);

			break;

		case 3:

			show_Q(front);

			break;

		case 4:

			exit(0);
	}
}

while (choice != 4);

}

//to add elements to the queue

node* add_Q(node *rear, char value)

{

node * temp;

temp = new node;

temp-&gt;data = value;

temp-&gt;link = NULL;

rear-&gt;link = temp;

rear = temp;

return (rear);

}

// to delete items from queue

node* del_Q(node *front, char &value)

{

node * temp;

clrscr();

if (front == NULL)

{

	cout &lt;&lt; ”queue is empty”;

	val = -1;
}
else

{

	temp = front;

	front =-&gt;link;

	value = temp-&gt;data;

	temp-&gt;link = NULL;

	delete temp;
}

return (front);

}

// show elements of the queue

void show_Q(node *front)

{

node * temp;

temp = front;

clrscr();

cout &lt;&lt; ”Elements of queue are”;

while (temp != NULL)

{

	cout &lt;&lt; ”\n” &lt;&lt; temp-&gt;data;

	temp = temp-&gt;link;
}

}

Queue implementation using C++