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(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( \le 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?

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following a strings CANNOT be generated using this program?

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is