Stack & Queue

If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?

• ABCD

• DCBA

• DCAB

• ABDC

In linked list implementation of a queue, the important condition for a queue to be empty is?

• FRONT is null

• REAR is null

• LINK is empty

• None of the mentioned

Are stacks FIFO or FILO?

• FILO
• FIFO
• LIFO
• LILO

How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.

• 1

• 2

• 3

• 4

How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.

• 1

• 2

• 3

• 4

Which of the following is true about linked list implementation of queue?

• In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.

• In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.

• Both of the above

• None of the above

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

• Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

• Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

• Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

• Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

• O(n)

• O(n+k)

• O(nk)

• O(n^2)

Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

• A queue cannot be implemented using this stack.

• A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

• A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

• A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

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.

The maximum possible number of iterations of the while loop in the algorithm is

• 16

• 32

• 64

• 256