ADT EXERCISES


WHY NOT DELETE QUEUES. THIS ALLOWS MORE IN DEPTH TREATMENT OF STACKS
WITHOUT SACRIFICING MUCH???

READING 
-------
Notes for lecture
Sedgewick, 127-149, 153-170
Kernighan and Ritchie, 4.11.1, 4.11.2, 5.1, 5,2, 5.3 
King, 419-424 (Stacks)

EXERCISES
---------

 2. Sedgewick, Exercise 4.6.

 4. Sedgewick, Exercise 4.18.

 5. Modify the stack program in the lecture notes to issue a warning and exit if
    the client program attempt to pop an empty stack or push onto a full one.

 6. Sedgewick, Exercise 4.30 (assume maxN is 10, as in Fig. 4.8).

 7. Sedgewick, Exercise 4.31.

 8. Sedgewick, Exercise 4.47.

 9. Suppose that an intermixed sequence of push and pop operations are
    performed.  The pushes push the integers 0 through 9 in order;
    the pops print out the return value. Which of the following sequences 
    could not occur?

           4 3 2 1 0 9 8 7 6 5
           4 6 8 7 5 3 2 9 0 1 
           2 5 6 7 4 8 9 3 1 0
           4 3 2 1 0 5 6 7 8 9

10. Describe a client program that uses Program 4.1 but has different 
    outcomes depending on whether the array (Program 4.4) or linked-list 
    (Program 4.5) implementation is used.
 
11. Write a program that reads in a sequence of characters and prints them
    in reverse order.  Use a stack.

12. Write a program that reads in a sequence of characters, and determines
    whether its parentheses, braces, and curly braces are "balanced."  Hint:
    for left delimiters, push onto stack; for right delimiters, pop
    from stack and check whether popped element matches right delimiter.

13. Write a program that reads in a positive integer and prints the 
    binary representation of that integer.  Hint:  divide the integer
    by 2.

14. Add an interface function void STACKmultipop(int k) that pops k
    elements from the stack, or until the stack is empty.

*15. Show how to implement a queue using two stacks.













.
.
.
.
.
		       ANSWERS TO ADT EXERCISES



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

 4. L  S  T  F
    
 5. 
      #include <stdlib.h>

      void STACKpush(Item item) {
         if (N == maxN) {
            printf("Error:  stack overflow.\n");
            exit(EXIT_FAILURE);
         }
         s[N++] = item; 
      }

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

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


 6. S T  O  U  T

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

 8. Same as Fig. 4.9 until second S is pushed.  Then:

    S      L T F I S
    T      L F I S T
    *   T  L F I S
    *   S  L F I
    *   I  L F
    O      L F O
    U      L F O U
    *   U  L F O
    T      L F O T
    *   T  L F O
    *   O  L F
    *   F  L

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

10. Do a pop().  Array representation would give garbage; linked 
    representation would bomb on segmentation fault.

11.   #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  */
            printf("%c", STACKpop());        /* stack until empty    */ 
         printf("\n");
         return 0;
      }

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

13.   #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;
      }

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

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

        void QUEUEput(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.