Очередь #4

Доброго всем вечера.

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

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

Основной принцип очереди:»Первый пришёл — первый вышел» (или FIFO, First In — First Out). Проще всего себе представить очередь очередью (извините за тавтологию) в магазин:

Очередь, связный список

 

То есть, тот, кто пришел первым в магазин и уйдет из него первым (правда просто? :) ). В этом и заключается смысл очереди.

Теперь поговорим о его представлении в памяти. Элементы очереди добавляются всегда! справа от хвоста (самый крайний правый элемент), а это значит, что каждый раз создается новый хвост.

А вот выталкивается (извлекается из списка, помним про pop?) элемент  всегда! с головы (элемент который находится «слева»). Наглядная структура очереди:

queue (2)

Вот и все. Теперь перейдем к реализации очереди средствами С++.

Код класса очереди содержит те же самые методы, что и класс стека: pop, push и peek. Однако, было добавлено одно поле tail (хвост). Это поле хранит адрес хвоста очереди. А вот и сам код:

Каждая строка кода комментирована, думаю,  что дополнительно описывать алгоритм смысла нет. Но если есть какие-то вопросы, то я обязательно на них отвечу.

А вот пример кода использования класса в мейне:

Единственное, что здесь стоит отметить — это строка system(«chcp 1251″). Она изменяет текстовую кодировку консоли, что позволяет корректно отображать кириллицу (Статья о корректном отображении кириллицы).

На этом я завершаю свое повествование. Если хотите не пропустить новые статьи, то подписывайтесь на рассылку блога.

До новых встреч.

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Очередь #4: Один комментарий

  1. Уведомление: Двусвязный список #5 | Всего наилучшего — 73!

Добавить комментарий