Question

3) Stacks vs Queues: a) A Circular Array is a common data structure for a buffer (a type of queue). Why is this advantageous over a regular array? (Hint: think about common queue operations and what they do to an array). b) Show a traversal of the following tree using a stack: 26 1 25 2 17 3 2. (19 7 1 (The numbers under the bubbles are a node number, not the data. ) c) Why would using a Linear Array for a stack where the top is index[O] have very poor performance? d) Explain how to use a priority queue to implement a stack, queue, and randomized queue.

Answer 1

3)
a)
with circular array, we can perform seeless enqueue and dequeue operations on queue, without having conserns about,managing the gap in the array,since it is circular
while in case of regular array, we must keep track of empty locations, to fill the coming values, in first come first serve fashion
b)
Traversal using stack on tree:
26,25,2,19,17,7,1
c)
while implemeting stack using linear Array, if we use index[0] as top, then, whenever we push new element to stack, we have to move all elements of the stack 1 position, so that the index[0] will be freed to insert new element, so it increases the complexity of push operation
which leads to poor performance
d)
priority queue: inserts elements in passed order, but deletes element with highest priority
implementing stack using priority queue:
stack works in last in first out fashion
means last element inserted is to be deleted first
so, we ensure that every time when a new element is inserted its priority will be highest of the already inserted elements
because, of this priority queue will deletes the last item, that is inserted
which works as Last in first out fashion

implementing queue using priority queue:
queue works in first in first out fashion
means first element inserted is to be deleted first
so, we ensure that every time when a new element is inserted its priority will be lowest of the already inserted elements
because, of this priority queue will deletes the first item which has the highest priorty
which works as first in first out fashion

implementing randomizedqueue using priority queue:
randomized queue inserts in passed order and deletes in random order
so, we ensure that every time when a new element is inserted its priority will be randomized
because, of this priority queue will deletes the item which has the highest priorty