Abstract Data Types

[zhurong325]

了解：Linux内核和发行版本

exercise:

1. Add method Top () that returns the value from the top of the stack without changing its state. Add method Count that returns the count of elements on the stack. solution:

int IStack::Top () const
{
 assert (_top > 0);
 return _arr [_top - 1];
}
int IStack::Count () const
{ return _top;
}

2. Modify the main function so that one of the stack contracts is violated. See what happens when you run the program with the assertions turned on. solution:

int main ()
{
 IStack stack;
 stack.Pop ();
}

3. Modify the stack so that it becomes CharStack--the stack of characters. Use it to invert strings by pushing all the characters of a string, and then popping and printing them one by one. This is the interface of the stack of characters:

   class CharStack
   {
   public:
   CharStack () :_top (0) {}
   void Push (char c);
   char Pop ();
   char Top () const;
   int Count () const;
   private:
   char _arr [maxStack];
   int _top;
   };

   This is how you reverse a string using a stack of characters:

   int main ()
   {
   CharStack stack;
   char str [] = "esreveR";
   for (int i = 0; str [i] != '\0'; ++i)
   stack.Push (str [i]);
   while (stack.Count () > 0)
   std::cout << stack.Pop ();
   std::cout << std::endl;
   }

4. Design the abstract data type Queue of doubles with methods Put and Get and the FIFO (First-In-First-Out) behavior. Implement it using an array and two indices: the put index, and the get index that trails the put index. The contract of this particular queue reads: The Put method shall never be called more than maxPuts times during the lifetime of the Queue. Thou shalt not Get when the Queue is empty.