Создание коллекций стеков и очередей

В этой статье объясняется, как создать другие структуры данных, такие как стеки и очереди, из классов списков MFC. В примерах используются классы, производные от CList, но вы можете использовать CList напрямую, если вам не нужно добавлять функциональные возможности.

Стеки

Так как стандартная коллекция списков имеет как голову, так и хвост, легко создать коллекцию производных списков, которая имитирует поведение стека последнего в первом выходе. Стопка подобна стопке подносов в столовой. Когда лотки добавляются в стопку, они помещаются сверху. Последний добавленный лоток — первый, который нужно удалить. Функции-члены AddHead и RemoveHead коллекции списка могут использоваться для добавления и удаления элементов непосредственно из начала списка, таким образом, последний добавленный элемент становится первым, который подлежит удалению.

Создание коллекции типа стек

1. Создайте новый класс списка на основе одного из существующих классов списков MFC и добавьте больше функций-членов для поддержки операций стека.

   В следующем примере показано, как добавить функции-члены для вставки элементов в стек, посмотреть верхний элемент стека и извлечь верхний элемент из стека.

   class CTray : public CObject { };
   
   class CStack : public CTypedPtrList< CObList, CTray* >
   {
   public:
      // Add element to top of stack
      void Push(CTray* newTray)
      {
         AddHead(newTray);
      }
   
      // Peek at top element of stack
      CTray* Peek()
      {
         return IsEmpty() ? NULL : GetHead();
      }
   
      // Pop top element off stack
      CTray* Pop()
      {
         return RemoveHead();
      }
   };
   

Обратите внимание, что этот подход предоставляет базовый CObList класс. Пользователь может вызвать любой CObList метод, независимо от того, имеет ли это смысл для стека.

Очереди

Поскольку коллекция стандартных списков имеет как голову, так и хвост, также легко создать коллекцию производных списков, которая имитирует поведение очереди по принципу "первый пришёл, первый ушёл". Очередь похожа на линию людей в кафетерии. Первый человек в очереди обслуживается первым. По мере того как больше людей приходят, они идут в конец очереди, чтобы дождаться своей очереди. Функции-члены AddTail и RemoveHead коллекции списков могут использоваться для добавления и удаления элементов непосредственно из начала или конца списка; таким образом, последний добавленный элемент всегда удаляется последним.

Создание коллекции очередей

1. Создайте новый класс списка на основе одного из предопределенных классов списка, предоставляемых библиотекой классов Microsoft Foundation, и добавьте дополнительные функции-члены для поддержки семантики операций с очередями.

   Следующий пример показывает, как использовать функции-члены для добавления элемента в конец очереди и извлечения элемента из начала очереди.

   class CQueue : public CTypedPtrList< CObList, CPerson* >
   {
   public:
      // Go to the end of the line
      void AddToEnd(CPerson* newPerson)
      {
         AddTail(newPerson);
      }        // End of the queue
   
   // Get first element in line
      CPerson* GetFromFront()
      {
         return IsEmpty() ? NULL : RemoveHead();
      }
   };
   

См. также

коллекции