Friday, 10 February 2017

C++ Program to Implement a Queue using Linked List and Classes


In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.

Queue can be implement in two ways
1) By using Array
2) By using Singly Linked List

 Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer.

 C++ Program for implementation of Queue Operations using Linked List is given below.

 PROGRAM: 
 
#include <stdio.h>
#include <stdlib.h>

struct node
{
      int data;
      struct node *next;
};

class Queue
{
      private:
              node *front=NULL;
              node *rear;
              node *current;
      public:
              void push(int x);
              void pop();
              void traverse();
};
void Queue::push(int x)
{
      if(front==NULL)
      {
              rear=(struct node*)malloc(sizeof(struct node));
              rear->data=x;
              rear->next=NULL;
              front=rear;
      }
      else
      {
              rear->next=(struct node*)malloc(sizeof(struct node));
              rear=rear->next;
              rear->data=x;
              rear->next=NULL;
      }
}
void Queue::pop()
{
      struct node *current;
      if(front==NULL)
      {
              printf("\nQueue is empty !");
      }
      else
      {
              current=front->next;
              front=current;
      }
}
void Queue::traverse()
{
      current=front;
      printf("\n");
      while(current!=NULL)
      {
              printf("%d ",current->data);
              current=current->next;
      }
}
int main()
{
      Queue que;
      int choice,ch,item;
      do
      {
             printf("\n--Main Menu--");
             printf("\n1. Insert a node");
             printf("\n2. Delete a node");
             printf("\n3. Traverse the Queue");
             printf("\nEnter your choice: ");
             scanf("%d",&choice);
             switch(choice)
             {
                   case 1: printf("\nEnter the element you want to insert: ");
                           scanf("%d",&item);
                           que.push(item);
                           break;
                   case 2: que.pop();
                           break;
                   case 3: que.traverse();
                           break;
                   default: printf("\nYou have entered the wrong choice, try again!");
             }
             printf("\nDo you want to continue[1/0]: ");
             scanf("%d",&ch);
      }while(ch==1);
      return 0;
}

OUTPUT:


See also:   Implementation of Queue Operations in C Program


EmoticonEmoticon