Previous Section
 < Free Open Study > 
Next Section


Chapter 4

    1. Yes

    2. No

    3. Yes

    4. No

    5. Yes

    6. No

    7. No

    8. Yes

  1. The accessing protocol of a stack is summarized as follows: Both to retrieve elements and to store new elements, access only the top of the stack. Access occurs through the Pop and Push member functions.

    1. 3 5 4 (on one line)

      5 16 1 0 (each on a separate line)

    2. 0 5 6 5 (each on a separate line)

      5 4 0 (on one line)

    1. Set secondElement to the second element in the stack, leaving the stack without its original top two elements.

      {
        stack.Pop(secondElement);
        stack.Pop(secondElement);
      }
      
    2. Set bottom equal to the bottom element in the stack, leaving the stack empty.

      {
        while (!stack.IsEmpty())
        stack.Pop(bottom);
      }
      
    3. Set bottom equal to the bottom element in the stack, leaving the stack unchanged.

      {
        StackType tempStack;
        ItemType tempItem;
      
        while (!stack.IsEmpty())
        {
          stack.Pop(tempItem);
          tempStack.Push(tempItem);
        }
        bottom = tempItem;
        // Restore stack
        while (!tempStack.IsEmpty())
        {
          tempStack.Pop(tempItem);
          stack.Push(tempItem);
        }
      }
      
    1. Draw a diagram of how the stack might look.

      smallTop: top for the stack of small values, initialized to - 1 and incremented.

      largeTop: top for the stack of large values, initialized to 200 and decremented.

      Click To expand
    2. class DStack
      {
      public:
        DStack();
        void Push(int item);
        void PopLarge(int& item);
        void PopSmall(int& item);
      private:
        int smallTop;
        int largeTop;
        int items[200];
      }
      
    3. void Push(int item)
      {
        if (item <= 1000)
        {
          small++;
          items[small] = item;
        }
        else
        {
          large--;
          items[large] = item;
        }
      }
      
    1. Although the items are technically homogeneous (all integers), they are not semantically homogeneous. The value in the [0] slot has a different meaning from the values in all other slots.

    2. The specifications would not change; all of the implementations would change.

  1. void (StackType& stack, ItemType oldItem, ItemType newItem)
    {
      StackType tempStack;
      ItemType tempItem;
      while (!stack.IsEmpty())
      {
        stack.Pop(tempItem);
        if (tempItem.ComparedTo(oldItem) == EQUAL)
          tempStack.Push(newItem);
        else
          tempStack.Push(tempItem);
      }
      // Restore stack
      while (!stack.IsEmpty())
      {
        tempStack.Pop(tempItem);
        stack.Push(tempItem):
      }
    }
    
    1. None.

    2. None.

    An alternative implementation would add an error data member to the class. This error flag would be set if underflow or overflow occurred and the operation would not be performed. A member function would have to be added to the class to allow the user to check the error flag.

  1. Yes, this sequence is possible.

  1. The accessing protocol is summarized as follows: Items are inserted at the rear and removed from the front. Accessing occurs through the Enqueue and Dequeue member functions.

    1. 1 0 4

      5 16 0 3

    2. 6 4 6 0

      6 5 5

    1. None.

    2. None.

  2. queue.Enqueue(letter);

    Click To expand
  3. queue.Enqueue(letter);

    Click To expand
  4. queue.Enqueue(letter);

    Click To expand
  5. queue.Dequeue(letter);

    Click To expand
  6. queue.Dequeue(letter);

    Click To expand
  7. queue.Dequeue(letter);

    Click To expand
  1. The correct answer is (a).

  2. The correct answer for the first statement is (d); the correct answer for the second statement is (a).

  1. {
      QueType<int> tempQ;
      int item;
    
      while (!queue.IsEmpty())
      {
        queue.Dequeue(item);
        if (item == oldItem)
          tempQ.Enqueue(newItem);
        else
          tempQ.Enqueue(item);
      }
      while (!tempQ. IsEmpty())
      {
        tempQ.Dequeue(item);
        queue.Enqueue(item);
      }
    }
    
    1. No

    2. Yes

    3. No

    4. No

    5. Yes

    6. Yes

    7. No

    8. Yes

    9. No

  2. bool Identical(QueType<float> queue1, QueType<float> queue2)
    {
      QueType<float> tempQ1;
      QueType<float> tempQ2;
      float item1, item2;
      bool same = true;
    
      while (!queue1. IsEmpty() && !queue2.IsEmpty())
      {
        queue1.Dequeue(item1);
        queue2.Dequeue(item2);
        tempQ1.Enqueue(item1);
        tempQ2.Enqueue(item2);
      }
      // Check for same size.
      same = queue1.IsEmpty() && queue2.IsEmpty();
      if (same)   // Check for matching items while copying.
        while (!tempQ1.IsEmpty())
        {
          tempQ1.Dequeue(item1);
          tempQ2.Dequeue(item2);
          queue1.Enqueue(item1);
          queue2.Enqueue(item2);
          if (item1 ! = item2)
            same = false;
        }
      else
      {   // Process rest of queuel and copy back.
        while (!queue1.IsEmpty())
        {
          queue1.Dequeue(item1):
          tempQ1.Enqueue(item1):
        }
        while (!tempQ1.IsEmpty())
        {
          tempQ1.Dequeue(item1);
          queue1.Enqueue(item1);
        }
        // Process rest of queue2 and copy back.
        while (!queue2.IsEmpty())
        {
          queue2.Dequeue(item2);
          tempQ2.Enqueue(item2)
        }
        while (!tempQ1.IsEmpty())
        {
          tempQ2.Dequeue(item2);
          queue2.Enqueue(item2);
        }
      }
      return same;
    }
    
  1. The MakeEmpty operation is a logical operation that sets the structure to empty. A class constructor is a C++ construct that is implicitly called when an object of the type is defined. MakeEmpty is under the control of the client program and can be applied any number of times.

  1. No, this sequence is not possible.

  2. #include "StackType.h"
    #include <iostream>
    bool IsOpen(char symbol);
    bool IsClosed(char symbol);
    bool Matches(char symbol, char openSymbol);
    
    int main()
    {
      using namespace std;
      char symbol;
      StackType stack;
      bool balanced = true;
      char openSymbol;
      try
      {
        cout << "Enter an expression and press return."
             << end1;
        cin.get(symbol);
        while (symbol != '\n' && balanced)
        {
          if (IsOpen(symbol))
          stack.Push(symbol);
    
          else if (IsClosed(symbol))
          {
            if (stack.IsEmpty())
              balanced = false;
            else
            {
              openSymbol = stack.Top();
              stack.Pop();
              balanced = Matches(symbol, openSymbol);
            }
          }
          cin.get(symbol);
        }
      }
      catch (FullStack error)
      {
        cout << "Push called when the stack is full." << end1;
        return 1;
      }
      catch (EmptyStack error)
      {
        cout << "Top or Pop called when stack is empty."
          << end1;
     return 1;
      }
      if (balanced)
      cout << "Expression is well formed." << end1;
      else
      cout << "Expression is not well formed."  << end1;
      return 0;
    }
    
    bool IsOpen(char symbol)
    {
      if ((symbol == '(') || (symbol == '{') || (symbol == '['))
        return true;
      else
        return false;
    }
    
    bool IsClosed(char symbol)
    {
      if ((symbol == ')') || (symbol =='}') || (symbol == ']'))
        return true;
      else
        return false;
    }
    
    bool Matches(char symbol, char openSymbol)
    {
      return  (((openSymbol == '(') && symbol == ')')
        || ((openSymbol == '{') && symbol == '}')
        || ((openSymbol == '[') && symbol == ']'));
    }
    
  1. class CountedStackType : public StackType
    {
    public:
      CountedStackType();
      void Push(ItemType newItem);
      void Pop(ItemType& item);
      int LengthIs() const;
      // Returns the number of items on the stack.
    private:
      int length;
    };
    
    void CountedStackType::Push(ItemType newItem)
    {
      length++;
      StackType::Push(newItem);
    }
    
    void CountedStackType::Pop(ItemType& item)
    {
      length--;
      StackType::Pop(item);
    }
    
    int CountedStackType::LengthIs() const
    {
      return length;
    }
    
    CountedStackType::CountedStack(int) : StackType()
    {
      length = 0;
    }
    


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)