ANSWERS TO STACKS AND QUEUES EXERCISES



 1.        S   Y       E U Q     T S A     O   N I E
 
     E A S A Y A Q U E U Q A S T S A E I O I N I E
       E A E A E A Q U Q A E A S A E   E I E I E
         E   E   E A Q A E   E A E       E   E
                   E A E       E
                     E

 2.  L  S  T  F
    
 3. 
      #include <stdio.h>
      #include <stdlib.h>
      void STACKpush(int item) {
         if (N == maxN) {
            printf("Error:  stack overflow.\n");
            exit(EXIT_FAILURE);
         }
         s[N++] = item; 
      }

      int STACKpop(void) {
         if (N == 0) {
            printf("Error:  stack underflow.\n");
            exit(EXIT_FAILURE);
         }
         return s[--N];
      }

      The exit() function terminates the program. EXIT_FAILURE is a predefined
      constant that is used to signal an abnormal termination.


 4.        E   A       S Y Q     U E S     T   I O N
 
     E E E A A S S S S Y Q U U U E S T T T   I O N
       A A S S Y Y Y Y Q U E E E S T   I I   O N 
         S   Y   Q Q Q U E   S S T       O   N
                   U U E       T             
                     E 

 5.   S  T  O  U  T




 6. The second ( 4 6 8 7 5 3 2 9 0 1 ).  When the 4 is popped, the
    stack must have 3 2 1 0 on it, so 1 has to be popped before 0.

 7.   #include <stdio.h>
      #include "STACK.h"
      
      int main(void) {
         int c;
         while ((c = getchar()) != EOF)      /* read character and   */
            STACKpush(c);                    /* push onto stack      */

         while (!STACKisempty())             /* repeatedly pop from  */
            putchar(STACKpop());             /* stack until empty    */ 
         printf("\n");
         return 0;
      }

      Note the C idiom for reading an arbitrary sequence of characters.


 8.   See /u/cs126/files/exercises/adt/paretheses2.c.


 9.   #include <stdio.h>
      #include "STACK.h"

      int main(void) {
         int n;
         scanf("%d", &n);
         STACKinit();
         while (n > 0) {           /* push 1 if n is odd,   */
            STACKpush(n % 2);      /* push 0 if n is even   */
            n /= 2;
         }

         while (!STACKisempty())
            printf("%d", STACKpop());
         printf("\n");
         return 0;
      }

10.  void STACKmultipop(int k) {
        int i;
        for (i = 0; i < k; i++)
           if (!STACKisempty())
              STACKpop();
     }

11.  We'll maintain two stacks A and B.

        void QUEUEput(int x): push element x onto stack A

        int QUEUEget(void):
           if stack B is empty
   (*)        pop all elements from A and push onto B
           pop element from B and return

        int QUEUEisempty(void):
           return true if both stack A and B are empty

     The crucial reason this works is (*). Popping the elements from
     A and pushing onto B has the effect of reversing all of the 
     elements. This is just what we want since now the topmost element
     on B contains the one least recently added.