40 points, One time submission ONLY. Timed Assignment. 2 hours. 1. Define a Queu
ID: 3560312 • Letter: 4
Question
40 points, One time submission ONLY. Timed Assignment. 2 hours.
1. Define a Queue. What operations would you need to support ADT Queue ?
2. Based on answer for 1. develop a C++ interface (template) to define Queue operations.
1 and 2 are open ended questions. So do give a complete answer. This exercise should take
you about an hour (maximum) to get it done.
(15 points for 2, 5 points for 1)
3. Based on the interface you defined in 2, implement your Queue, either using
Linked-List (linear) or Array. If necessary you can reuse code from any of your assignments
for this implementation.
I will test your implementation as part of grading.. So do make sure you submit a working program !
(20 points)
Explanation / Answer
1. Definition of queue
In general, a queue is a line of people or things waiting to be handled, usually in sequential order starting at the beginning or top of the line or sequence. In computer technology, a queue is a sequence of work objects that are waiting to be processed. The possible factors, arrangements, and processes related to queues is known as queueing theory.
Here is the minimal set of operations that we would need for an abstract queue:
Create
Add or insert
Remove or delete
Is Empty
Destroy
Useful operations might be Count() and Display().
Queues are useful structures because they produce a certain order in which the contents of the queue are used. This ordering is known as First In First Out (FIFO). Since the queue is holding elements of the same type it should be quite simple to take this structure and implement it using linked nodes, as shown above. Using the linked node structure gives us a distinct advantage over the implementation of the queue using static arrays. We can easily increase the size of the list and we do not need to move elements up to the front of the queue. The node structure we will use will be the same as for the stack data structure. The node will hold some data and also a link / pointer to the next node in the chain.
Looking at the queue structure, we can see that the queue is created and destroyed in a similar manner to the stack data structure. We add and remove from the top of the stack, but we remove from the front of the queue and add at the rear. So that we can make use of the stack pop operation, we shall rename it remove. The create operation is similar to that of the stack; we just point to the null character and the destroy operation will be the same. We won't discuss these operations any further in relation to the queue data structure.
2. C++ code for muni_stop:
// Interfaces:
class PeopleQueue
{
public:
virtual int enq(person *)=0;
virtual person *deq()=0;
virtual int size()=0;
};
class Port
{
public:
virtual city *dest()=0;
virtual time *departs()=0;
};
class BusStop : public virtual PeopleQueue, public virtual Port
{
public:
virtual boolean covered()=0;
virtual int enq(person *)=0;
virtual person *deq()=0;
virtual int size()=0;
virtual city *dest()=0;
virtual time *departs()=0;
};
// Implementations:
class linked_people : public virtual PeopleQueue
{
class recptr *head ,*tail;
public:
linked_people () { head =tail =NULL ;
}
virtual int enq (person *);
virtual person *deq ();
virtual int size ();
};
class muni_stop : public virtual BusStop, public linked_people
{
boolean shelter ;
public:
muni_stop (boolean cover )
{
shelter =cover;
}
virtual int enq(person *p0)
{
return linked_people::enq(p0);
}
virtual person *deq() { return linked_people::deq();
}
virtual int size() { return linked_people::size();
}
virtual city *dest();
virtual time *departs();
virtual boolean covered() { return shelter;
}
}
3. C++ Program to Implement Queue using Linked List
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
struct node
{
int data;
node *next;
}
*front = NULL,*rear = NULL,*p = NULL,*np = NULL;
void push(int x)
{
np = new node;
np->data = x;
np->next = NULL;
if(front == NULL)
{
front = rear = np;
rear->next = NULL;
}
else
{
rear->next = np;
rear = np;
rear->next = NULL;
}
}
int remove()
{
int x;
if(front == NULL)
{
cout<<"empty queue ";
}
else
{
p = front;
x = p->data;
front = front->next;
delete(p);
return(x);
}
}
int main()
{
int n,c = 0,x;
cout<<"Enter the number of values to be pushed into queue ";
cin>>n;
while (c < n)
{
cout<<"Enter the value to be entered into queue ";
cin>>x;
push(x);
c++;
}
cout<<" Removed Values ";
while(true)
{
if (front != NULL)
cout<<remove()<<endl;
else
break;
}
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.