Queues
Ø Queues are another restricted access data structure, much like stacks. A queue is like a one-way line where data enters the end of the line and exits from the front of the line.
Ø A queue is a linear data structure which simulates waiting in line. A queue has two ends, a front and a (rear) end.
Ø Data must always enter the queue at the end and leave from the front of the line. This type of action can be summarized as FIFO (first-in, first-out).
Ø All the data stored in a queue must be of the same type.
Ø A queue is the appropriate data structure when simulating waiting in line.
A printer which is part of a multi-user network must process print commands on a first-come, first-served basis.
Ø A queue would be used to store the jobs in a line.
Code using linked list class
#include
"stdafx.h"
#include
<iostream>
#include
<cstdlib>
using
namespace std;
struct
node
{
char name[20];
int age;
float height;
node *nxt;
};
node *start_ptr=NULL;
int
main()
{
void
push ();
void
pop();
char
ch;
cout<<"Queue
data structure implemented using a singly linked list"<<endl;
do
{
cout<<"Select an operation"<<endl<<endl;
cout<<"u for push"<<endl;
cout<<"o for pop"<<endl;
cout<<"e for exit"<<endl;
cin>>ch;
switch(ch)
{
case 'u':
push();
break;
case
'o':
pop();
break;
case 'e':
exit(0);
}
}
while(ch!='e');
return 0;
}
void
pop()
{
node *temp1,*temp2;
if(start_ptr==NULL)
cout<<"The
list is empty"<<endl;
else
{
temp1=start_ptr;
temp2=temp1;
while(temp1->nxt!=NULL)
{
temp2=temp1;
temp1=temp1->nxt;
}
if(temp1==temp2)
{
cout<<temp1->name<<",";
cout<<temp1->age<<",
";
cout<<temp1->height<<endl;
start_ptr=NULL;
}
else
{
cout<<temp1->name<<",
";
cout<<temp1->age<<",
";
cout<<temp1->height<<endl;
temp2->nxt=NULL;
delete
temp1;
}
}
}
void
push ()
{
node *temp;
temp =
new node;
cout <<
"Please enter the name of the person: ";
cin >> temp->name;
cout <<
"Please enter the age of the person: ";
cin >> temp->age;
cout <<
"Please enter the height of the person: ";
cin >> temp->height;
if (start_ptr == NULL)
{
temp->nxt=NULL;
start_ptr = temp;
}
else
{
temp->nxt=start_ptr;
start_ptr=temp;
}
}
#include
"stdafx.h"
#include<string>
#include <iostream>
#include <queue>
using
namespace
std;
int main()
{
queue<string> q;
q.push("First");
q.push("Second");
q.push("Third");
cout<<"There
are "<<q.size()<<" elements in the
queue"<<endl;
cout<<"The
elements in the queue, as removed, are"<<endl;
while(!(q.empty()))
{
cout << q.front()<<endl;
q.pop();
}
}
Member Functions
| back | Returns a reference to the last and most recently added element at the back of the queue. |
| empty | Tests if the queue is empty |
| front | Returns a reference to the first element at the front of the queue |
| pop | Removes an element from the front of the queue |
| push | Adds an element to the back of the queue |
| size | Returns the size of the queue |