Queues

Queues

Queues are data structures that, like the stack, have restrictions on where you can add and remove elements. To understand a queue, think of a cafeteria line: the person at the front is served first, and people are added to the line at the back. Thus, the first person in line is served first, and the last person is served last. This can be abbreviated to First In, First Out (FIFO).

The cafeteria line is one type of queue. Queues are often used in programming networks, operating systems, and other situations in which many different processes must share resources such as CPU time.

One bit of terminology: the addition of an element to a queue is known as an enqueue, and removing an element from the queue is known as a dequeue.
Although the concept may be simple,programming a queue is not as simple as programming a stack.

Let's go back to the example of the cafeteria line. Let's say one person leaves the line. Then what? Everyone in line must step forward, right? Now, imagine if only one person could move at a time. So, the second person steps forward to fill the space left by the first person, and then the third person steps forwards to fill the space left by the second person, and so on. Now imagine that
no one can leave or be added to the line until everyone has stepped forward.

You can see the line will move very slowly. It is not difficult to program a queue that works, but it is quite a proposition to make a queue that is fast!!

There are a couple of basic ways to implement a queue. The first is to just make an array and shift all the elements to accommodate enqueues and dequeues. This, as we said above, is slow.
The slowness of the previous method is that with many elements, the shifting takes time. Thus, another method, instead of shifting the elements,

shifts the enqueue and dequeue points.

Imagine that cafeteria line again. If the front of the line continually moves backwards as each person leaves the line, then the people don't need to step forward or backwards, which saves time.

Unfortunately, this method is much more complicated than the basic method. Instead of keeping track of just the enqueue point (the "end"), we also need to keep track of the dequeue point (the "front"). This all gets even more complicated when we realize that after a bunch of enqueues and dequeues, the line will need to wrap around the end of the array. Think of the cafeteria line. As people enter and leave the line, the line moves farther and farther backwards, and eventually it will circle the entire cafeteria and end up at its original location.

Implementation Simple

#include<iostream>

#include<conio.h> 

#include<stdlib.h> 

using namespace std;

class queue 

{

 int queue1[5];

 int rear,front; 

 public: queue()

{ 

     rear=-1; front=-1; 

 }

 void insert(int x)

{ 

if(rear > 4) 

{ 

cout <<"queue over flow"; 

front=rear=-1; return; 

}

 queue1[++rear]=x;

 cout <<"inserted" <<x;

} 

void delet() 

{

if(front==rear)

{

 cout <<"queue under flow";

return;

} 

cout <<"deleted" <<queue1[++front];

}

 void display() 

 { 

if(rear==front) 

{ 

cout <<" queue empty";

return;

} 

for(int i=front+1;i<=rear;i++)

cout <<queue1[i]<<" ";

 } 

};

 main() 

{

 int ch; queue qu; 

while(1) 

 

{

 cout <<"\n1.insert 2.delet 3.display 4.exit\nEnter ur choice"; 

cin >> ch;  switch(ch) 

{

 case 1: cout <<"enter the element"; 

cin >> ch;

qu.insert(ch); 

break;

case 2: qu.delet();

break; 

case 3: qu.display();

break;

case 4:

exit(0);

} 

} 

  return (0);

}

OUTPUT

1.insert 2.delet 3.display 4.exit
Enter ur choice1
enter the element21
inserted21
1.insert 2.delet 3.display 4.exit
Enter ur choice1
enter the element22
inserted22
1.insert 2.delet 3.display 4.exit
Enter ur choice1
enter the element16

inserted16
1.insert 2.delet 3.display 4.exit
Enter ur choice3
21 22 16
1.insert 2.delet 3.display 4.exit
Enter ur choice2
deleted21
1.insert 2.delet 3.display 4.exit
Enter ur choice3
22 16
1.insert 2.delet 3.display 4.exit
Enter ur choice

Implementation Code

#include<iostream>

#include<cstdlib>
using namespace std;
struct node

{
int info;
struct node *next;
};
class Queue

{
private:
node *rear;
node *front;
public:
Queue();
void enqueue();
void dequeue();
void display();
};
Queue::Queue()

{
rear = NULL;
front = NULL;
}
void Queue::enqueue()

{
int data;
node *temp = new node;
cout<<"Enter the data to enqueue: ";
cin>>data;
temp->info = data;
temp->next = NULL;
if(front == NULL)

{
front = temp;
}

else

{
rear->next = temp;
}
rear = temp;
}
void Queue::dequeue()

{
node *temp = new node;
if(front == NULL)

{
cout<<"\nQueue is Emtpty\n";
}

else

{
temp = front;
front = front->next;
cout<<"The data Dequeued is "<<temp->info;
delete temp;
}
}
void Queue::display()

{
node *p = new node;
p = front;
if(front == NULL)

{
cout<<"\nNothing to Display\n";
}

else

{
while(p!=NULL)

{
cout<<endl<<p->info;
p = p->next;
}
}
}
int main()

{
Queue queue;
int choice;
while(true)

{
cout<<"\n1.Enqueue\n2. Dequeue\n3. Display\n 4.Quit";
cout<<"\nEnter your choice: ";
cin>>choice;
switch(choice)

{
case 1:
queue.enqueue();
break;
case 2:
queue.dequeue();
break;
case 3:
queue.display();
break;
case 4:
exit(0);
break;
default:
cout<<"\nInvalid Input. Try again! \n";
break;
}
}
return 0;

}