queqe

Queue Data Structures

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

---

Basic features of Queue

1. Like Stack, Queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

---

Applications of Queue

Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.

---

Implementation of Queue

Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.

When we remove element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one move all the other elements on position forward. In approach [B] we remove the element from head position and then move head to the next position.

In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element. In approach [B] there is no such overhead, but whener we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.# include <iostream>
using namespace std;
# include <process.h>
# include <conio.h>
int display_menu();
class circularqueue
{
  int arr[10];
  int front,rear;
  int size;
  public:
     circularqueue()
     {
      front=0;
      rear=0;
      size=10;
     }
     void display();
     void enqueue();
     void delete_element();
};

void circularqueue :: display()
{
 cout<<endl;
 if(front!=0 && rear!=0)
 {
        int i=front;
        cout<<"arr["<<i<<"] :"<<arr[i]<<endl;
        while(i!=rear)
        {
         i=(i % size)+1;
         cout<<"arr["<<i<<"] :"<<arr[i]<<endl;
        }

 }
 else
 {
    cout<<"Queue is empty"<<endl;
 }
 getch();
}

void circularqueue :: enqueue()
{
 cout<<endl;
 if(front==0 && rear==0)
 {
  cout<<"Enter Number to enqueue at Position arr["<<rear+1<<"] :";
  cin>>arr[1];
  rear=1;
  front=1;
 }
 else
 {
  int next=(rear % size)+1;






  if(next==front)
  {
   cout<<"Queue is Full ...";
   getch();
  }
  else
  {
   cout<<"Enter Number to enqueue at Position arr["<<next<<"] :";
   cin>>arr[next];
   rear=next;
  }
 }
}

void  circularqueue :: delete_element()
{
 cout<<endl;
 if(rear==0 && front==0)
 {
   cout<<"Queue is empty ...";
   getch();
   return;
 }


 if(rear==front)
 {
  rear=0;
  front=0;
 }
 else
 {
  front=(front % size)+1;
 }
}

int main()
{
 circularqueue cq1;
 while(1)
 {
  switch(display_menu())
  {
    case 1: cq1.enqueue();
        break;
    case 2: cq1.delete_element();
        break;
    case 3: cq1.display();
        break;
   
  }
 }
}
int display_menu()
{
 int c;

 cout<<endl;
 cout<<"| 1 | : Enqueue element"<<endl;
 cout<<"| 2 | : Delete element"<<endl;
 cout<<"| 3 | : Display"<<endl;
 cout<<"| 4 | : Exit"<<endl;
 cout<<"Enter your Choice :";
 cin>>c;
 return c;
}
========================================================================

overflow and underflow in it

#include<iostream>

#include<conio.h>

using namespace std;

int a[5];

int front=-1;

int rear=-1;

int main()

{

insert(int 10);

insert(int 20);

deleted();

return 0;

     getch();

 }

    //insert();

//deleted(); 

void insert(int n)

{

if((front ==0 && rear==4)||(front==rear+1))

{

cout<<"overflow";

return;

}

if(front==-1)

{

front=0;

rear=0;

}

else if(rear==4)

{

rear=0;

}

else

{

rear=rear+1;

}

a[rear]=n;

}

void deleted()

{

if(front==-1)

{

cout<<"underflow";

   return;   

}

if(front==4)

{

front=0;

}

else

{

front=front+1;

}

}