С++ для начинающих Однонаправленный список FIFO

Однонаправленный список FIFO или по простому очередь. Перед написанием этой статьи была написана похожая статья, но LIFO, сейчас же речь о FIFO
FIFO в отличие от LIFO по другому выбирает данные из списка. First in First out — первый пришел, первый вышел на экране может выглядеть как
Пришел 1 (первый)
Пришел 2 (второй)
Пришел 3 (третий)
Пришел 4 (четвертый)
====================
Итого: 1 2 3 4
Обращение к элементу списка выбирает тот элемент, который пришел первым. Первым пришла единица, следовательно первым будет 1, вторым 2, третьим 3..
Если создать несколько по порядку идущих чисел и поочереди записать их в список, а потом вывести список на экран, то при выводе на экран будет сохранен порядок, в LIFO же переворачивается.

Я как-то долго не мог понять чем отличается очередь от списка FIFO — ответ ничем, это и есть список FIFO. А очередью называется потому как соблюдаются правила «Справедливых» очередей. Т.е. кто первее — того первее обслужат. Надеюсь доступно, понятно и не сложно запомнить. Теперь прийдем к практической части.
 
 
Так как FIFO мало отличается от LIFO, то коды будут очень сильно схожи, но я видоизменю немного под себя.
Итак, чтобы построить очередь FIFO, для начала имеет смысл запомнить, что для FIFO как обязательные элементы адрес начала очереди и адрес конца очереди. Запихивать в очередь я буду обычные числа, т.к. так удобнее смотреть. Ну и добавлю размер. Этот размер не обязателен для примера, но пусть будет.

Итак, со скелетом очереди определились: 2 адреса, значение и размер очереди. Этот скелет имеет смысл запихать в класс или структуру. Т.к. поначалу структуры попроще воспринимаются, я запихаю скелет в структуру. Для тех, кто плохо знаком со структурами и классами имеет смысл прочитать С++ для начинающих Классы Первое знакомство

Код C++ «Скелет» очереди FIFO

Да, выше я не сказал про следующий элемент, но чтобы создать очередь FIFO, нужно как-то связывать текущий элемент с вновь пришедшим. Это как в поликлиннике прибежал какой-то гад, сказал, что за вами и убежал. Но связь создана. Вот чтобы создать такую связь внутри программы используют адреса памяти, проще говоря указатели. Тип этих указателей соответствует названию класса/структуры. В скелете я обозначил переменную *Next. Эта переменная будет хранить адрес памяти последнего поступившего в очередь элемента. Не впереди идущего, а последнего поступившего, но тем не менее он по факту новый, следующий элемент очереди. Немного запутано, но я такого объяснения не видел когда пытался разобраться самостоятельно.
 
 
Теперь когда создан скелет очереди, можно добавить функцию добавления элементов. Чтобы добавить элемент в очередь FIFO, имеет смысл запомнить простой алгоритм:

  • 1) Создать новый элемент, тип которого соответствует типу класса/структуры
  • 2) Записать в этот элемент полученное значение
  • 3) Запомнить адрес начала очереди
  • 4) Проверить очередь на наличие в ней элементов. Не новый элемент проверить, а то, что голова не пустая
    -Если Очередь пустая — то обозначить, что начало очереди это же и конец очереди и, что вновь созданный элемент это и начало и конец очереди одновременно.Короче для всех трех костей адрес должен быть один и тот же.
    -Если очередь не пустая, то записать в хвост очереди созданный элемент из п.1 и сдвинуть хвост, указав что адресом хвоста теперь будет адрес вновь созданного элемента.

_______________________
Такой вот алгоритм показываю на примере.

static int count — переменная — счетчик, которая благодаря ключевому слову static не будет умирать и будет сохранять свое последнее значение после завершения работы Add
Вот при каждом новом вызове Add эта переменная будет увеличиваться на 1 и после этого запоминаться в переменную size структуры MyFIFO
 
 
Так добавление показал и объяснил. Теперь вопрос в том, как работать с этой очередью. Элементарное, что можно с ней сделать — вывести всю очередь на экран. Чтобы вывести ее на экран, нужно узнать адрес начала очереди. После того как адрес очереди известен, можно вывести на экран значение текущего элемента очереди и сдвинуть адрес на адрес следующего запомненного элемента. (Внутри очереди это последний туда поступивший после только что выбранного). Т.к. создавалась связь адресов, то попасть в нужный адрес не будет проблемой, для этого при помощи цикла нужно постепенно обращаться к элементу Next только что выбранного элемента, выводить значение val на экран и вновь двигать очередь. Цикл выполнять имеет смысл до тех пор когда не будет достигнут конец очереди. Так очередь FIFO может быть кольцевой и не кольцевой, признаки могут быть различны. Для некольцевой очереди обычно признак то, что изъятый элемент не будет последним элементом очереди. Ну а в кольцевом — количество элементов для изъятия. В самом конце я покажу кольцевой, он почти не отличается от обычного FIFO, а сейчас обычный FIFO

Вот и все. Теперь осталось написать функцию удаления очереди из памяти. Вместе с ней я вывожу

  • полный код FIFO С++ для начинающих.

Вот так вот. Не так уж и сложно. А теперь из сделаем маленький апгрэйд. Из обычной очереди сделаем кольцевую. Для этого хвост должен указывать на начало, а вовнутрь функции приниматься аргумент, который сообщает количество итераций (количество раз выполнения цикла). Весь код абсолютно такой же за исключением маленьких поправок

Т.к. до этого самым первым поступившим в очередь был NULL, который был использован в цикле для проверки окончания работы цикла (в функции Show), то теперь же этим изменеием этот NULL стал Head, т.е. фактически NULL и в Head и в Tail->Next и цикл вообще не выполняется, следовательно нужно видоизменить цикл внутри функции Show

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

  • Полный код C++ кольцевой список FIFO

Вот такие вот пироги. Вы ознакомились с представлением и простейшей реализацией списка FIFO в C++, ну или реализацией обычной очереди. Надеюсь этот материал оказался и интересным и помог вам познать то, что так трудно объясняют в других местах.

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

11 комментариев: С++ для начинающих Однонаправленный список FIFO

  • СВЕТА говорит:

    Долго, очень долго искала информацию в интернете о программировании списков!!! И… вот, наконец-то нашла!!! Спасибо за скрупулезность и доброту! Вы мне очень помогли! Желаю удачи, здоровья, благополучия…




    0



    0
  • Slavik говорит:

    Спасибо автору за статьи, очень нужное дело для начинающих. Обязательно продолжайте писать.
    Дополню в Show утечка памяти и ненужное копирование, можно написать так:
    void List::Show() //метод отображения списка на экране
    {
    element *temp=Head; //прыгаем этим указателем к голове списка

    while (temp!=NULL) //пока что-то встречается
    {
    cout<x<Next; //и переходим к следующему элементу
    }
    }




    0



    0
  • Slavik говорит:

    редактор подвел 🙁
    void List::Show() //метод отображения списка на экране
    {
    element *temp=Head; //прыгаем этим указателем к голове списка

    while (temp!=NULL) //пока что-то встречается
    {
    cout<x<Next; //и переходим к следующему элементу
    }
    }




    0



    0
  • Slavik говорит:

    Да уж в тэги не взял код. В общем в Show()

    element *temp=Head; //прыгаем этим указателем к голове списка
    вместо

    element *temp=new element; //выделяем память указателю
    temp=Head; //прыгаем этим указателем к голове списка
    temp->x=Head->x; //присваиваем в x нашего указателя x головы




    0



    0
  • admin говорит:

    Благодарю. Исправил.




    0



    0
  • Дмитрий говорит:

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

    Автор сайта отвечает:
    Именно список FIFO надо в обратном?
    может вам просто LIFO нужен?




    0



    0
  • Дмитрий говорит:

    admin, LIFO

    Автор сайта отвечает:
    так есть же пример с описанием. Предыдущая статья. Ссылка есть даже на этой странице (вверху переход слева на предудущую статью)
    http://ci-plus-plus-snachala.ru/?p=57




    0



    0
  • Дмитрий говорит:

    там как я понял, идет вывод: если вводим (1, 2 , 3 , 4) то выводит 1->2->3->4->NULL. Это я уяснил.
    А вот как 4->3->2->1, не понимаю что то…

    Автор сайта отвечает:
    Ясно. Сейсач проверять и перепроверять нет возможности, но возможно я там и правда ошибся.
    А вот так 4-3-2-1 — это стек. Насколько я понял по отписанным там комментариям, стек описан мной достаточно удачно, вот ссылка
    http://ci-plus-plus-snachala.ru/?p=91

    Дмитрий говорит: Спасибо за внимание. Нравится ваш сайт

    Автор сайта отвечает:
    Тут по обеим ссылкам , которые я вам дал, описывается решение вашего вопроса.
    В первом случае описывается более сложно, но более подробно, во втором случае описывается достаточно просто.

    я посмотрел код из LIFO и он работает как вам и надо. Что-то вы невнимательно посмотрели и поэтому неправильно поняли.




    0



    0
  • Vus говорит:

    Добрый вечер) Не подскажите, у меня проблемы с данным списком. Поиск одинаковых элементов в списке, делаю по вашему примеру.Получается муть какая то.

    Автор сайта отвечает:
    Скорее всего подскажу.
    Только я не знаю где вы чудите, чтобы я мог вам подсказать. К сожалению, я не экстрасенс и не верю что таковые существуют.
    Функция поиска выполняется достаточно легко, только сам поиск элементов может существовать в разных вариациях. Она очень похожа на функция Show
    В общем, желательно увидеть ваши «жалкие» потуги
    Нужно более полно описать ожидаемый результат. Может вам количество надо, а может просто что есть одинаковые, а может нужно расписать позиции для каждого или может создать массив, который хранит позиции. Тут как бы много вариантов конечного результата возможно.
    ======================
    Да. Я могу помочь. Но нужен ваш пример и ваша задача. Конечный результат может требоваться разный.




    0



    0
  • Руфина говорит:

    Спасибо огромное за такую легкоусвояемую информацию)))




    0



    0
  • Marina говорит:

    в 12-й стройке 2-го кода нету ли ошибки, не понимаю смысл данной строчки.

     

    Автор сайта отвечает:
    Вот в этой?
    Next=temp->Head;




    0



    0

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

Ваш e-mail не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/denis-kolisnichenko/programmirovanie-dlya-android-samouchitel/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор вероисповедание программист

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок