a) (4 points) You are given an initially empty queue and perform the following o
ID: 3906076 • Letter: A
Question
a) (4 points) You are given an initially empty queue and perform the following operations on it: enqueue(B), enqueue(A), enqueue(T), enqueue(I), dequeue), dequeue), enqueue(Z), enqueue(A), dequeue), enqueue(I), enqueue(N), enqueue(L), dequeue), enqueue(G), enqueue(A), enqueue(R), enqueue(F), dequeue), dequeue). Show the contents of the queue after all operations have been performed and indicate where the front and end of the queue are. the queue, you are only allowed to use the methods of a queue ADT. Hint: Consider using an auxiliary data structure.Explanation / Answer
Solution :
a)
enqueue(B) : front -> B <- rear
enqueue(A) : front -> B|A <- rear
enqueue(T) : front -> B|A|T <- rear
enqueue(I) : front -> B|A|T|I <- rear
dequeue() : front -> A|T|I <- rear
dequeue() : front -> T|I <- rear
enqueue(Z) : front -> T|I|Z <- rear
enqueue(A) : front -> T|I|Z|A <- rear
dequeue() : front -> I|Z|A <- rear
enqueue(I) : front -> I|Z|A|I <- rear
enqueue(N) : front -> I|Z|A|I|N <- rear
enqueue(L) : front -> I|Z|A|I|N|L <- rear
dequeue() : front -> Z|A|I|N|L <- rear
enqueue(G) : front -> Z|A|I|N|L|G <- rear
enqueue(A) : front -> Z|A|I|N|L|G|A <- rear
enqueue(R) : front -> Z|A|I|N|L|G|A|R <- rear
enqueue(F) : front -> Z|A|I|N|L|G|A|R|F <- rear
dequeue() : front -> A|I|N|L|G|A|R|F <- rear
dequeue() : front -> I|N|L|G|A|R|F <- rear
b)
Algorithm to reverse a Queue :
- Q = input queue
- Take an empty stack S.
- while(Q is not empty) :
temp = dequeue(Q) // dequeue from Queue Q
push(S, temp) // push temp on stack S
- While(S is not empty) :
temp = pop(S) // pop element from stack S
enqueue(Q, temp) // enqueue element in queue.
- return Q.
Here stack will store all the elements in reverse order.So when elements are popped out, the last element of Q will be on front.
if you have any doubts then you can ask in comment section. If you find the solution helpful then upvote the answer. Thank you.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.