Answer the following questions: a) Bill suggested that he can implement a stack

Question

Answer the following questions: a) Bill suggested that he can implement a stack ADT using a priority queue and a constant amount of additional space. Recall that a stack supports push and pop operations, and a priority queue supports remove Min and insert operations. Explain how Bill can achieve this by showing the necessary pseudo code for implementing the stack ADT. b) Referring to a) above, what are the tight big-Oh time complexities of the push and pop operations of the newly designed stack given that the priority queue is implemented using a heap? Explain your answer.

Explanation / Answer

Answer:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int max,i,n;
int input=-1;
class stack
{
int s[20];
public:
void insert();
void delete();
void show();
};
void stack::insert()
{
int value;
if(input==(max-1))
cout<<"Stack is full";
else
{
cout<<"enter data:";
cin>>value;
input=input+1;
s[input]=value;
}}
void stack::delete()
{
if(input==-1)
cout<<"stack is empty";
else
s[input--]='';
}void stack::show()
{cout<<"showing the contents of stack: ";
if(input==-1)
cout<<"stack is empty"<<" ";
else
{for(i=0;i<=input;i++)
cout<<s[i]<<" ";
cout<<" ";
}}
void main()
{
stack sa;
clrscr();
cout<<"enter the range:";
cin>>max;
while(1)
{
cout<<" 1.insert 2.delete 3.show 4.evalueit";
cout<<" enter ur choice:";
cin>>n;
switch(n)
{case 1:
sa.insert();
break;
case 2:
sa.delete();
break;
case 3:
sa.show();
break;
case 4:
exit(0);
default:
cout<<"Invalid option";
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.