+1 vote
29 views

A First In First Out queue is a data structure supporting the operation Enque, Deque, Print, Enque(x) adds the item $x$ to the tail of the queue. Deque removes the element at the head of the queue and returns its value. Print prints the head of the queue.

1. You are given a queue containing $5$ elements. Using a single additional temporary variable $X,$ write down a sequence of statements each being one of Enque, Deque, Print so that the output of the program results in the $5$ elements of the queue being printed in reverse order.
2. If the queue had $n$ elements to begin with, how many statements would you need to print the queue in reverse order?
in DS
recategorized | 29 views

Let queue contains elements $\bf{(1,2,3,4,5)}$ in order, with $1$ being the head. Therefore the below sequence of instructions will be displayed whenever the state of the queue changes.

Initial queue
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;

$12345$
$23451$
$34512$
$45123$
$51234$

prints $5$

$12345$
$23451$
$34512$
$45123$

prints $4$

$51234$
$12345$
$23451$
$34512$

prints $3$

$45123$
$51234$
$12345$
$23451$

prints $2$

$34521$
$45123$
$51234$
$12345$

prints $1$

Hence, the number of statements in the program = $45$

When we perform X = Deque followed by Enque(X), the elements at the head are moved to the tail. When these two statements are repeated for $n-1$ times the last element will be moved to the head position. Now when $\bf{print}$ statement is called it will print the current head element of the list (which was the last element, previously)

So total instructions needed to move the last element to the head position and print it are: $2(n-1)+1$.

So, finally if the code or the above block of $2(n-1) + 1$ is repeated n times then we will get the above queue in the reverse order.

So total statements required = $\bf{n(2n-1)}$
by Boss (13.4k points)
edited by