Q16. Stacks 06 What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm? LinkList Stack Queue Tree Prev

#1

The answer given is linked list.why??

#2

Q7. Queue Operation Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below. while Q is not empty do { if S is empty OR Top(S)<= Head(Q) then { x = Dequeue(Q) Push(S, x) } else { x = Pop(S) Enqueue(Q,x) } } The maximum possible number of iterations of the while loop in the algorithm is 16 32 64 256.Please also explain this

#3

hello @KetanPandey
no , correct answer is stack .

#4

The worst case happens when the queue is sorted in decreasing order. In worst case, loop runs n*n times.

Queue: 4 3 2 1
Stack: Empty

3 2 1
4

3 2 1 4
Empty

2 1 4
3

2 1 4 3
Empty

1 4 3
2

1 4 3 2
Empty

4 3 2
1

3 2
1 4

3 2 4
1

2 4
1 3

2 4 3
1

4 3
1 2

3
1 2 4

3 4
1 2

4
1 2 3

Empty
1 2 3 4