Queues

• Queues
  • Introduction
  • Representation
  • Operations
  • Implementation
    • Simple queue
    • With front always at zero
    • Linked queue
    • Dequeue
    • Priority Queues
      • Max Priority
      • Min Priority

Queues

A queue is a FIFO structure – First In First Out.  A queue is a data structure in which insertion of a new element is done at the rear end and deletion of an element is done at the front end of the queue.  Hence, it is different from the stack, since it uses both the ends to perform insertion and deletion rather than using only one end for these operations.  The operations on queue are similar to those of stack.  Enqueue operation represents insertion of a new element in the queue and Dequeue operation represents deletion of an element from the queue.

Representation:

Queue may be represented using arrays or linked list.  Array representation involves keeping track of two positions via. subscript for front and rear, whereas linked list involves two pointers, one positioned at the front end of the queue and the other positioned at the rear end of the queue.

i)  Array representation of queue:  Queues may be representated using arrays as follows:

 

• Program to implement a Queue using Array with front always at zero

  Queues
  /*Implementation of queues using arrays*/
  /*Queue implementation with front always at zero*/

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  #define MAX 10

  typedef struct queue
  {int front, rear;
  int arr[MAX];
  }queue;

  /*Enqueue will increment rear by one and add new element
  at this subscript*/

  void enqueue(queue *q, int x)
  {if(q->rear==MAX-1)
  {printf(“Queue Overflow!”);
  exit(1);
  }
  q->arr[++q->rear]=x;
  }

  /*Front is always kept at zero.
  Deletion involves shifting of elements to the left by one
  position and rear gets decremented by one*/

  int dequeue(queue *q)
  {
  int i,no;
  if(q->rear<q->front)
  {printf(“Queue Underflow!”);
  exit(1);
  }
  no=q->arr[q->front];
  /*fixed front at zero results in shifting of elements*/
  for(i=q->front;i<q->rear;i++)
  q->arr[i]=q->arr[i+1];
  q->arr[q->rear]=0;
  q->rear–;
  return no;
  }

  void display(queue *q)
  {int i;
  for(i=q->front;i<=q->rear;i++)
  printf(“%d\t”,q->arr[i]);
  }

  void main()
  {
  int ch,num;
  queue q;
  q.front=0;
  q.rear=-1;
  while(1)
  {
  clrscr();
  printf(“\nMenu”);
  printf(“\n\n1. Enqueue”);
  printf(“\n2. Dequeue”);
  printf(“\n3. Display”);
  printf(“\n4. Exit”);
  printf(“\n\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1:
  printf(“\nEnter number?”);
  scanf(“%d”,&num);
  enqueue(&q,num);
  break;
  case 2:
  num=dequeue(&q);
  printf(“\nElement removed from the queue is %d”,num);
  break;
  case 3:
  display(&q);
  break;
  case 4:
  exit(0);
  default:
  printf(“\nInvalid choice!”);
  }
  getch();
  }

  Program to implement a Queue using Array by incrementing front as well as rear

  Queues

  /*Implementation of Linear queues using arrays*/
  /*Queue implementation by shifting front as well as rear*/

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  #define MAX 4

  typedef struct queue
  {int front, rear;
  int arr[MAX];
  }queue;

  /*Enqueue will increment rear by one and add new element
  at this subscript*/

  void enqueue(queue *q, int x)
  {if(q->rear==MAX-1)
  {printf(“\nQueue Overflow!”);
  exit(1);
  }
  q->arr[++q->rear]=x;
  }
  /*Dequeue operation increments front by 1.
  Linear queues are not considered efficient since
  such an approach may result in an overflow, even if
  empty blocks are available at beginning. To remove
  this deficiency circular queues may be considered*/

  int dequeue(queue *q)
  {
  int i,no;
  if((q->rear==-1)&&(q->front>q->rear))
  {printf(“\nQueue Underflow!”);
  exit(1);
  }
  return (q->arr[q->front++]);
  }

  void display(queue *q)
  {int i;
  for(i=q->front;i<=q->rear;i++)
  printf(“%d\t”,q->arr[i]);
  }

  void main()
  {
  int ch,num;
  queue q;
  q.front=0;
  q.rear=-1;
  while(1)
  {
  clrscr();
  printf(“\nMenu”);
  printf(“\n\n1. Enqueue”);
  printf(“\n2. Dequeue”);
  printf(“\n3. Display”);
  printf(“\n4. Exit”);
  printf(“\n\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1:
  printf(“\nEnter number?”);
  scanf(“%d”,&num);
  enqueue(&q,num);
  break;
  case 2:
  num=dequeue(&q);
  printf(“\nElement removed from the queue is %d”,num);
  break;
  case 3:
  display(&q);
  break;
  case 4:
  exit(0);
  default:
  printf(“\nInvalid choice!”);
  }
  getch();
  }
  }

ii) Linked list implementation of queue:  Linked list may also be used to represent a queue as follows:

• Program to implement Linear Queues using Linked List

  Queues

  /*Implementation of Linear Queues using Linked List*/

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  typedef struct queue
  {int info;
  struct queue *next;
  }queue;

  queue *create()
  {queue *temp=(queue *)malloc(sizeof(queue));
  if(temp==NULL)
  {printf(“Memory Allocation Error!”);
  exit(1);
  }
  return temp;
  }

  queue *makenode(int x)
  {queue *temp=create();
  temp->info=x;
  temp->next=NULL;
  return temp;
  }

  /*Enqueue operation requires traversing the entire
  queue for inserting a new node.*/

  queue *enqueue(queue *front,int x)
  {
  queue *temp,*ptr=makenode(x);
  if(front==NULL)
  {front=ptr;
  return front;
  }
  /*entire queue is traversed to insert at end*/
  for(temp=front;temp->next!=NULL;temp=temp->next);
  temp->next=ptr;
  return front;
  }

  queue *dequeue(queue *front)
  {
  queue *temp=front;
  if(front==NULL)
  {printf(“\nQueue Underflow!”);
  exit(1);
  }
  /*the following assignment directly operates upon front
  pointer by making it point to the next node and deleting
  the first node*/
  front=front->next;
  free(temp);
  return front;
  }

  void display(queue *front)
  {queue *temp=front;
  while(temp!=NULL)
  {printf(“%d->”,temp->info);
  temp=temp->next;
  }
  printf(“\b\b “);
  }

  void main()
  {
  queue *front=NULL,*rear=NULL;
  int num,ch;
  while(1)
  {
  clrscr();
  printf(“\nMenu”);
  printf(“\n\n1. Enqueue”);
  printf(“\n2. Dequeue”);
  printf(“\n3. Display”);
  printf(“\n4. Exit”);
  printf(“\n\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1: printf(“\nEnter an element?”);
  scanf(“%d”,&num);
  front = enqueue(front,num);
  break;
  case 2: printf(“Removing front element from the queue…!”);
  front=dequeue(front);
  break;
  case 3: display(front);
  break;
  case 4: exit(0);
  default:printf(“\nInvalid choice…!”);
  }
  getch();
  }
  }

  Program to implement Linear Queues using Linked list using global front and rear pointers

  Queues

  /*Implementation of Linear Queues using Linked List
  using global front and rear pointers*/

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  typedef struct queue
  {int info;
  struct queue *next;
  }queue;

  queue *front=NULL,*rear=NULL;

  queue *create()
  {queue *temp=(queue *)malloc(sizeof(queue));
  if(temp==NULL)
  {printf(“Memory Allocation Error!”);
  exit(1);
  }
  return temp;
  }

  queue *makenode(int x)
  {queue *temp=create();
  temp->info=x;
  temp->next=NULL;
  return temp;
  }

  /*Enqueue operation references rear pointer
  to insert a new node at the next address of rear*/

  void enqueue(int x)
  {
  queue *temp=makenode(x);
  if(front==NULL)
  {front=temp;
  rear=temp;
  }
  else/*rear pointer referred without traversing entire queue*/
  {rear->next=temp;
  rear=temp;
  }
  }
  void dequeue()
  {
  queue *temp=front;
  if(front==NULL)
  {printf(“\nQueue Underflow!”);
  exit(1);
  }
  front=front->next;
  free(temp);
  }

  void display()
  {queue *temp=front;
  while(temp!=NULL)
  {printf(“%d->”,temp->info);
  temp=temp->next;
  }
  printf(“\b\b “);
  }

  void main()
  {
  int num,ch;
  while(1)
  {
  clrscr();
  printf(“\nMenu”);
  printf(“\n\n1. Enqueue”);
  printf(“\n2. Dequeue”);
  printf(“\n3. Display”);
  printf(“\n4. Exit”);
  printf(“\n\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1: printf(“\nEnter an element?”);
  scanf(“%d”,&num);
  enqueue(num);
  break;
  case 2: printf(“Removing front element from the queue…!”);
  dequeue();
  break;
  case 3: display();
  break;
  case 4: exit(0);
  default:printf(“\nInvalid choice…!”);
  }
  getch();
  }
  }

Double Ended Queues (Dequeue):

A double ended queue allows fast insertion and deletion at the beginning as well as at the end of the queue.  It supports all the operations applicable for an ordinary queue.  But, enqueue may be done at front end too and dequeue may be done at rear end.

• Program to implement Dequeue (Double Ended Queues) using Arrays with front always at zero

  Double Ended Queues (Dequeue)

  /*Implementation of De-queue using arrays*/

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  #define MAX 10

  typedef struct dequeue
  {int front,rear;
  int arr[MAX];
  }dq;

  /*If flag is zero, insertion is done at beginning
  else if flag is one, insertion is done at end.
  */
  void enqueue(dq *q,int x,int flag)
  {
  int i;
  if(q->rear==MAX-1)
  {printf(“\nQueue overflow!”);
  exit(1);
  }
  if(flag==0)
  {for(i=q->rear;i>=q->front;i–)
  q->arr[i+1]=q->arr[i];
  q->arr[q->front]=x;
  q->rear++;
  }
  else if(flag==1)
  {q->arr[++q->rear]=x;
  }
  else
  {printf(“\nInvalid flag value…!”);
  return;
  }
  }

  void de_queue(dq *q,int flag)
  {int i;
  /*front is initialized with zero, then rear=-1
  indicates underflow*/
  if(q->rear<q->front)
  {printf(“\nQueue Underflow…!”);
  exit(1);
  }
  if(flag==0)/*deletion at beginning*/
  {for(i=q->front;i<=q->rear;i++)
  q->arr[i]=q->arr[i+1];
  q->arr[q->rear]=0;
  q->rear–;
  }
  else if(flag==1)
  {q->arr[q->rear--]=0;
  }
  else
  {printf(“\nInvalid flag value…!”);
  return;
  }
  }

  void display(dq *q)
  {
  int i;
  for(i=q->front;i<=q->rear;i++)
  printf(“%d\t”,q->arr[i]);
  }

  void main()
  {
  dq q;
  q.front=0;
  q.rear=-1;
  int ch,num;
  while(1)
  {
  clrscr();
  printf(“\nMenu-Double Ended Queue”);
  printf(“\n\n1. Enqueue – Begin”);
  printf(“\n2. Enqueue – End”);
  printf(“\n3. Dequeue – Begin”);
  printf(“\n4. Dequeue – End”);
  printf(“\n5. Display”);
  printf(“\n6. Exit”);
  printf(“\n\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1:
  printf(“\nEnter the number?”);
  scanf(“%d”,&num);
  enqueue(&q,num,0);
  break;
  case 2:
  printf(“\nEnter the number?”);
  scanf(“%d”,&num);
  enqueue(&q,num,1);
  break;
  case 3:
  printf(“\nDeleting element from beginning…!”);
  de_queue(&q,0);
  break;
  case 4:
  printf(“\nDeleting element from end…!”);
  de_queue(&q,1);
  break;
  case 5:
  display(&q);
  break;
  case 6:
  exit(0);
  default:
  printf(“\nInvalid Choice…!”);
  }
  getch();
  }
  }

Priority Queues:

In a priority queue, the elements are dequeued according to their priority and their current queue position.  Priority may be assigned to elements such that dequeue operation may be based on priority.  Thus, it is not necessary in a priority queue, that the element at the front position is the candidate for deletion.  Priorities may be assigned such that higher priorities may be associated with lower numbers and lower priorities may be associated with higher numbers or vice-versa.   The elements may be arranged at the time of entry or using some ordering function.  Two versions of priority queues may be implemented in general.  First one is Max priority queue and the second one is Min priority queue.

i)  Max Priority Queue:

In a max priority queue, each element is assigned a priority.  The element to be dequeued is the element with the max priority.  The elements are extracted in the descending order of priority.  The program to implement max priority queue is as follows-

• Program to implement MAX Priority Queue

  Priority Queues

  #include <stdio.h>
  #include <stdlib.h>
  #include <conio.h>
  #define MAX 5

  void display(struct queue *q);

  struct queue
  {int front,rear;
  int arr[MAX];
  };

  void push(struct queue *q,int arr[],int n)
  {
  int i=0,j,f,r;
  for(i=0;i<n;i++)
  {if(q->front==-1)
  {q->arr[0]=arr[i];
  q->front=q->rear=0;
  }
  else
  {f=q->front;
  r=q->rear;
  while(f<=r && q->arr[f]>arr[i])
  f++;
  for(j=r+1;j>=f;j–)
  q->arr[j+1]=q->arr[j];
  q->arr[f] = arr[i];
  q->rear++;
  }
  }
  }

  void display(struct queue *q)
  {
  int f;
  if(q->front==-1)
  {printf(“\nQueue is empty!”);
  exit(1);
  }
  for(f=q->front;f<=q->rear;f++)
  printf(“%d\t”,q->arr[f]);
  }

  int pop(struct queue *q)
  {if(q->front == -1)
  {printf(“\nQueue empty! Underflow.”);
  return 0;
  }
  return (q->arr[q->front++]);
  }

  void main()
  {
  int arr[MAX],n,i,j,f;
  struct queue q;
  q.front = q.rear = -1;
  clrscr();
  printf(“\nEnter total numbers?”);
  scanf(“%d”,&n);
  printf(“\nEnter numbers?”);
  for(i=0;i<n;i++)
  scanf(“%d”,&arr[i]);
  push(&q,arr,n);
  printf(“\nDisplaying elements of MAX Priority queue:”);
  display(&q);
  printf(“\nPop an element from MAX Priority queue:”);
  i=pop(&q);
  printf(“\nPopped element is maximum element i.e. %d”,i);
  printf(“\nMax Priority Queue after pop operation:”);
  display(&q);
  getch();
  }

ii) Min Priority Queue:

In a min priority queue, each element is assigned a priority.  The element to be dequeued is the element with the min priority.  The elements are extracted in the ascending order of priority.  The program to implement min priority queue is as follows-

• Program to implement MIN Priority Queue

  Priority Queue

  #include <stdio.h>
  #include <conio.h>
  #include <stdlib.h>

  #define MAX 10

  struct queue
  {int front,rear;
  int arr[MAX];
  };

  void push(struct queue *q,int x)
  {
  int f,r,i;
  if(q->front==-1)
  {q->arr[0]=x;
  q->front=q->rear=0;
  }
  else
  {
  f=q->front;
  r=q->rear;
  while(f<=r && q->arr[f]<x)
  f++;
  for(i=r;i>=f;i–)
  q->arr[i+1]=q->arr[i];
  q->arr[f]=x;
  q->rear++;
  }
  }

  void display(struct queue *q)
  {
  int f,r;
  for(f=q->front;f<=q->rear;f++)
  {printf(“%d\t”,q->arr[f]);
  }
  }

  int pop(struct queue *q)
  {
  if(q->front==-1)
  {printf(“Queue empty!”);
  exit(1);
  }
  return(q->arr[q->front++]);
  }

  void main()
  {
  int ch,x;
  struct queue q;
  q.front=-1;
  q.rear=-1;
  while(1)
  {
  clrscr();
  printf(“\nMenu\n1. Push\n2. Pop\n3. Display\n4. Exit”);
  printf(“\nEnter your choice?”);
  scanf(“%d”,&ch);
  switch(ch)
  {
  case 1:
  printf(“\nEnter the number?”);
  scanf(“%d”,&x);
  push(&q,x);
  break;
  case 2:
  x=pop(&q);
  printf(“\nPopped element is %d”,x);
  break;
  case 3:
  display(&q);
  break;
  case 4:
  exit(0);
  default:
  printf(“\nInvalid choice!”);
  }
  getch();
  }
  }