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

Sample solution
A reasonable stack implementation needs only a constant
number of steps to push a new element, hence O(1)

(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);
       }
    }
Sample solution
Assuming 1 is the top of the stack,
   then the items are enqueued in order 1, 2, 3, 4, 5
Then the dequeued items are pushed in order 1, 2, 3, 4, 5
   which means the resulting stack contents are
   5, 4, 3, 2, 1
i.e. the stack contents are reversed by function F