Answer the following questions: a) Bill suggested that he can implement a stack
ID: 3803788 • Letter: A
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
a) Stack ADT:
Stacks and queues may be modeled as particular kinds of priority queues.
In a stack, the priority of each inserted element is monotonically increasing
thus, the last element inserted is always the first retrieved.
So what this question wants us to do.As stacks are implicitly implemented as
priority queues.
LIFO behavior follows from the fact that every new element is pushed with a
priority higher than all the current elements, so it will be popped before any
of them.
Stack :
private:
q : MaxPriorityQueue
counter : 0
public:
push(x) : q.add(x, counter++)
pop() : q.remove()
Priority Queue:
In priority queue elements to be inserted in FIFO order. so the insertion completed
that choose it in priority queue manner i.e.., we give the priority to the queue
element that element should be in highest priority element. suppose two elements should
be same type in priority queue then selected in queue manner.
Pseudo code of Priority queue:
1: MaxPQ()
2: MaxPQ(int max)
3: MaxPQ(Key[] a)
4: void insert(Key v)
5: Key max()
6: Key delMax()
7: boolean isEmpty()
8: int size()
b) it is a way of measuring the rate at which the speed of a function grows.
In other words, big O quantifies an algorithm's efficiency. But the
implementation of it is something else.
For example, in the best case scenario push and pull operations will be O(1)
because the number of steps it takes to remove from or add to the stack are
going to be fixed. Regardless of the value, the process will be the same.
push and pop can degrade performance from O(1) to O(n^2).
If I have an array of n/2 capacity, n push and pop operations, and a dynamic
array that doubles or halves its capacity when full or half full, how is it
possible that the sequence in which these operations occur can affect the speed
in which a program completes? Since push and pop work on the top element of the
stack, I'm having trouble seeing how efficiency goes from a constant to O(n^2).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.