Define an ADT to support the operations enqueue, dequeue and onqueue. onqueue(x)
ID: 3864836 • Letter: D
Question
Define an ADT to support the operations enqueue, dequeue and onqueue. onqueue(x) is a function returning true or false depending on whether x is on the queue. Write also onqueue and compute its running time. Extend the ADT queue to include the following operations: last that will return the rear element of the queue (which shall not be deleted from the queue) length that will return the number of elements on the queue. enqueueN that will enqueue an array of N elements on the queue dequeueN that will dequeue and return an array of N elements from the queue Write an implementation for each operation and compute their running time. Extend the ADT queue to include an operation called searchqueue that searches for an item on the queue and returns its position. Write a program for the new function and compute its running time. Implement the ADT that provides a circular implementation of a queue. Extend the queue ADT to include a function that returns the number of elements on the queue. Implement such a function. A dequeue (doubled-ended queue) is a list from which elements can be inserted or deleted at either end. Present a specification for the dequeue ADT and develop array as well as pointer implementations of it.Explanation / Answer
The c++ code for above problem is:
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class ATDQueue
{
int atdq[5];
int rear,front;
public:
queue()
{
rear=-1;
front=-1;
}
void rearprint()
{
if(front==rear)
{
cout <<"queue under flow";
return;
}
cout <<atdq[rear]<<" ";
}
void lengthq()
{
if(front==rear)
{
cout <<"queue under flow";
return;
}
cout <<rear<<" ";
}
void enqueueN(int x)
{
if(rear > 4)
{
cout <<"queue over flow";
front=rear=-1;
return;
}
atdq[++rear]=x;
cout <<"inserted" <<x;
}
void dequeueN()
{
if(front==rear)
{
cout <<"queue under flow";
return;
}
cout <<"deleted" <<atdq[++front];
}
void displayq()
{
if(rear==front)
{
cout <<" queue empty";
return;
}
for(int i=front;i<=rear;i++)
cout <<atdq[i]<<" ";
}
};
int main()
{
int choice;
ATDQueue q;
while(1)
{
cout <<" 1.enqueueN 2.dequeueN 3.rear 4.length 5.display 6.exit Enter ur choice";
cin >> choice;
switch(choice)
{
case 1: cout <<"enter the element";
cin >> choice;
q.enqueueN(choice);
break;
case 2: q.dequeueN(); break;
case 3: q.rearprint();break;
case 4: q.lengthq();break;
case 5: q.displayq();break;
case 6: exit(0);
}
}
return 0;
}
Time complexity:
insert- O(1)
delete- O(1)
length-O(1)
rear print-O(1).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.