Question 3. Stacks and Queues [ 10 marks ]

(a) For a stack that currently contains N elements, (and assuming a sensible stack impementation) which answer below best represents the time needed to push a new element on the stack?

  1. O(N) i.e. proportional to N
  2. O(log2(N)) i.e. proportional to log2(N)
  3. O(1) i.e. independent of N
  4. none of the above

(b) Suppose we have typical stack and queue classes that includes the following methods (amongst others): 

      Stack                   Queue
      ----------------        --------------------
      void push(int i)        void enqueue(int i)
      void pop(int &i)        void dequeue(int &i)
      bool isempty()          bool isempty()
If a stack contains values 1,2,3,4,5 (in that order), and we pass it as a parameter to the function F below, what values will it contain (and in what order) afterwards? 
    void F(Stack &S)
    {
       int i;
       Queue Q;
       while (!S.isempty()) {
          S.pop(i);
          Q.enqueue(i); 
       }
       while (!Q.isempty()) {
          Q.dequeue(i);
          S.push(i);
       }
    }