recategorized by
911 views
2 votes
2 votes

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? 
recategorized by

3 Answers

0 votes
0 votes
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)}$
edited by
0 votes
0 votes
Let queue contains elements (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  # 12345
X = Deque; Enque(X); # 23451
X = Deque; Enque(X); # 34512
X = Deque; Enque(X); # 45123
X = Deque; Enque(X); # 51234
Print; Deque; # prints 5, queue now is 1234

X = Deque; Enque(X); # 2341
X = Deque; Enque(X); # 3412
X = Deque; Enque(X); # 4123
Print; Deque; # print 4, queue now is 123

X = Deque; Enque(X); # 231
X = Deque; Enque(X); # 312
Print; Deque; # print 3, queue now is 12

X = Deque; Enque(X); # 21
Print; Deque; # print 2, queue now is 1
 
Print; # print 1

Hence, the number of statements in the program = 29

This is a superior solution compared to the one with 45 steps. The saving comes from the fact that you don't need to preserve the element you just printed.

So total statements required is:
$\sum\limits_{i=1}^n 2i - 1$

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
2 answers
3
gatecse asked Sep 13, 2019
625 views
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...