A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

Consider the following statements:

(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

What is the minimum number of stacks of size n required to implement a queue of size n?

A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:

    procedure P (var x :integer; y: integer); 
    and if P is called by ; P(a,b) 

State precisely in a sentence what is pushed on stack for parameters a and b.

(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?

A function f defined on stacks of integers satisfies the following properties.

 f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. 

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

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 _________.

An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x) {
   push (S1, x);
}
  
void delete(Q){
   if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print(“Q is empty”);
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
   x=pop(S2);
}

Let n insert and m(<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

PUSH ( 10 ). PUSH ( 20 ). POP. PUSH ( 10 ). PUSH ( 20 ). POP.  POP. POP. PUSH ( 20 ). POP 

If (rear == maxsize - 1) rear=0; else rear = rear + 1; is required in

The data structure required for breadth first traversal on a graph is

With respect to deque which of the following is true?

____ is First in last out kind of data structure.

Queue structure is used in ____