Homework 16

Exercise 1 from Chapter 6 of the textbook (p.294)
(to do with using an ADT for a stack)

1. Suppose that you have a stack S and an empty auxiliary stack T. Show how you can do each of the following tasks by using only the ADT stack operations:

1. Display the contents of S in reverse order; that is, display the top last.
2. Count the number of items in S, leaving S unchanged.
3. Delete every occurrence of a specified item from S, leaving the order of the remaining elements unchanged.

Solution

1. ItemType i;
   while (!EmptyStack (S))
   {
      Pop (S, i);
      Push (i, T);
   }
   while (!EmptyStack (T))
   {
      Pop (T, i);
      i.Display ();
      Push (i, S);
   }   
   

2. ItemType i;
   int Count = 0;
   while (!EmptyStack (S))
   {
      Pop (S, i);
      Push (i, T);
   }
   while (!EmptyStack (T))
   {
      Pop (T, i);
      Count++;
      Push (i, S);
   }   
   

3. Delete ( ItemType ElementToDelete )
   {
      ItemType i;
      while (!EmptyStack (S))
      {
         Pop (S, i);
         if (!(i == ElementToDelete))
            Push (i, T);
      }
      while (!EmptyStack (T))
      {
         Pop (T, i);
         Push (i, S);
      }   
   }