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

Статья
10/12/2023

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

Стеки

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

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

Наследуйте новый класс списка из одного из существующих классов списков 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 коллекции списков и могут использоваться для добавления и удаления элементов конкретно из головы или хвоста списка. Таким образом, последний добавленный элемент всегда является последним для удаления.

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

Наследуйте новый класс списка от одного из предварительно определенных классов списка, предоставляемых библиотекой классов 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();
   }
};
```

См. также

Коллекции

Поделиться через