search
Log In
2 votes
231 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 by
231 views

2 Answers

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
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 vote
1 answer
1
150 views
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
asked Sep 13, 2019 in Theory of Computation gatecse 150 views
0 votes
1 answer
2
77 views
A student requests a recommendation letter from a professor. The professor gives three sealed envelopes. Each envelope contains either a good recommendation letter or a bad recommendation letter. Make a list of all the possible scenarios. Suppose now the professor tells the ... true and the other two are false. Can the student find out the contents of the envelopes without breaking their seals?
asked Sep 13, 2019 in Numerical Ability gatecse 77 views
1 vote
1 answer
3
113 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 exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
asked Sep 13, 2019 in Graph Theory gatecse 113 views
2 votes
1 answer
4
110 views
You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by $2$ positions. Give an $O(\log n)$ time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)
asked Sep 13, 2019 in Algorithms gatecse 110 views
...