Queue implementation using C++
Written by
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 << ”\n Main Menu”; cout << ”\n Adding in Queue”; cout << ”\n Delete from Queue”; cout << ”\n Traverse the queue”; cout << ”\n Exit Main Menu”; cout << ”\n Enter a choice from Main Menu”; cin >> choice; switch (choice) { case 1: do { cout << ”Enter the item to be added to the queue”; cin >> value; rear = add_Q(rear, value); if (front == NULL) front = rear; cout << ”\n Add more element < Y / N > ? ”; cin >> 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 << ”\n Item deleted from queue is”; cout << ”\n Delete more items from the queue< Y / N > ? ”; cin >> 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->data = value; temp->link = NULL; rear->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 << ”queue is empty”; val = -1; } else { temp = front; front =->link; value = temp->data; temp->link = NULL; delete temp; } return (front);
}
// show elements of the queue
void show_Q(node *front)
{
node * temp; temp = front; clrscr(); cout << ”Elements of queue are”; while (temp != NULL) { cout << ”\n” << temp->data; temp = temp->link; }
}