Динамические структуры. Очередь на основе однонаправленного списка

  • Любую организацию сцепки элементов с целью создания массивоподобной структуры называют очередью.
  • В зависимости от места сцепки элемента: или вперёд всех сцепленных, или позади всех сцепленных, или выборочно из этих двух вариантов — очередь называют:

    • Сцепка к переду очереди:
      LIFO, она же — стек, она же однонаправленный список, она же — линейный список.
    • Сцепка в хвост очереди:
      FIFO, она же — просто очередь, она же однонаправленный список, она же — линейный список.
    • Сцепка по выбору: или к переду очереди, или в хвост очереди:
      Дек, двусвязный (двунаправленный) список, она же — линейный список.
Когда автор ci-plus-plus-snachala.ru разбирался с динамическими списками, то столкнулся с проблемой разных названий на одни и те же структуры данных. Из-за этого некоторые темы повторяются. Так, например, очередь на основе однонаправленного списка уже описывалась на страницах

Учитываем, что просто очередью чаще всего называют организацию очереди наиболее похожей на самую обычную очередь из живых людей. Но и стек и дек — это тоже очереди. Линейными списками очереди называют из-за того, что они, очереди, являются массивоподобными, но не являются массивами. Поскольку чаще всего просто очередью называют организацию сцепки элементов в хвост очереди, то в дальнейшем речь идёт о примере очереди FIFO.

Добавляются элементы в очередь так же как и в стек, но если голова у стека постоянно смещается на новый элемент, то у очереди голова остаётся неподвижной, она служит признаком первого занявшего места. Но если мы двигаем указатель-признак на один конец очереди, то нам нужен второй указатель — признак конца очереди. Поскольку мы не сможем без элемента-признака конца сказать, где именно встретился последний вписавшийся в очередь элемент, нам нужен такой признак. Когда мы идём от последнего к первому элементу (LIFO), нам достаточно встретить первый элемент, внутри которого сцепляющий звенья указатель направлен вникуда, и опознать конец, но в случае обхода от первого элемента к последнему (FIFO) сцепляющий указатель последнего будет направлен на идущее перед ним звено. Нам нужно как-то опознавать этот последний элемент, и для этого служит вспомогательный указатель, который обычно обозначается как хвост. Если мы посмотрим порядок обхода человечьими глазами, то получится обход справа-налево, самый правый элемент — голова, самый левый — хвост.
Если сравнивать очередь (т. е. FIFO) и стек (т. е. LIFO), то можно сказать, что стек — это очередь наглецов. (Каждый новый приходящий наглее всех, кто уже стоит в очереди, и не ожидая ни секунды идёт на обслуживание первым). Очередь, которую называют очередь (Queue), это честная очередь. Если пришел, то жди.
Как тут ни объясняй, но как всё это сделать на языках программирования далеко не легко понять новичку. Мы итак все знаем, что такое очередь в жизни.
В примере, демонстрируемом ниже, показывается как добавить функцию удаления элемента из очереди. Первый листинг написан без этой функции, второй с ней.

Чтобы добавить функцию удаления, мне пришлось немного поломать голову. Функция удаления элемента описывается таким образом, чтобы элемент удалялся из конца очереди. Так как в приведённом примере начало справа, конец слева, то и удаляться будут те элементы, что слева, а добавляться элементы будут в правую часть списка. Этот момент наглядно демонстрирует сам факт обслуживания очереди по принципу "Первый пришёл, первый ушёл".

Полагаю, по этому коду видно, что всё не так страшно. Сама функция удаления достаточно маленькая и должна быть проста к пониманию. Использовано то же, что и при выводе списка на экран, только при этом мы берём именно сам указатель на начало списка и перенаправляем его на следующее звено. Так как теряя указатель на начало списка мы теряем часть списка, то использована дополнительная переменная. Дополнительная переменная является указателем и в неё запоминается адрес начала списка. Запоминается перед тем, как начало списка поменяется. Начало списка изменили и используя эту переменную освобождаем память от той предыдущей части списка. Всё это должно в достаточно легкой степени быть читаемо прямо из кода.
По поводу того, что из себя представляет очередь, — думаю, что комментарии описывают это лучше всего.
Я видел много примеров, где использована проверка на пустоту очереди в виде отдельной функции, видел примеры с исключениями и видел, где обязательно что-то припаяют туда. На самом деле проверки важны и их нужно прописывать, чтобы исключать всевозможные ошибки, но я написание проверок в основном пропускаю, чтобы они не отвлекали от основной части кода.
  • Любую организацию сцепки элементов с целью создания массивоподобной структуры называют очередью.
  • В зависимости от места сцепки элемента: или вперёд всех сцепленных, или позади всех сцепленных, или выборочно из этих двух вариантов — очередь называют:

    • Сцепка к переду очереди:
      LIFO, она же — стек, она же однонаправленный список, она же — линейный список.
    • Сцепка в хвост очереди:
      FIFO, она же — просто очередь, она же однонаправленный список, она же — линейный список.
    • Сцепка по выбору: или к переду очереди, или в хвост очереди:
      Дек, двусвязный (двунаправленный) список, она же — линейный список.
Когда автор ci-plus-plus-snachala.ru разбирался с динамическими списками, то столкнулся с проблемой разных названий на одни и те же структуры данных. Из-за этого некоторые темы повторяются. Так, например, очередь на основе однонаправленного списка уже описывалась на страницах

Учитываем, что просто очередью чаще всего называют организацию очереди наиболее похожей на самую обычную очередь из живых людей. Но и стек и дек — это тоже очереди. Линейными списками очереди называют из-за того, что он, очереди, являются массивоподобными, но не являются массивами. Поскольку чаще всего просто очередью называют организацию сцепки элементов в хвост очереди, то в дальнейшем речь идёт о примере очереди FIFO.

Добавляются элементы в очередь так же как и в стек, но если голова у стека постоянно смещается на новый элемент, то у очереди голова остаётся неподвижной, она служит признаком первого занявшего места. Но если мы двигаем указатель-признак на один конец очереди, то нам нужен второй указатель — признак конца очереди. Поскольку мы не сможем без элемента-признака конца сказать, где именно встретился последний вписавшийся в очередь элемент, нам нужен такой признак. Когда мы идём от последнего к первому элементу (LIFO), нам достаточно встретить первый элемент, внутри которого сцепляющий звенья указатель направлен вникуда, и опознать конец, но в случае обхода от первого элемента к последнему (FIFO) сцепляющий указатель последнего будет направлен на идущее перед ним звено. Нам нужно как-то опознавать этот последний элемент, и для этого служит вспомогательный указатель, который обычно обозначается как хвост. Если мы посмотрим порядок обхода человечьими глазами, то получится обход справа-налево, самый правый элемент — голова, самый левый — хвост.
Если сравнивать очередь (т. е. FIFO) и стек (т. е. LIFO), то можно сказать, что стек — это очередь наглецов. (Каждый новый приходящий наглее всех, кто уже стоит в очереди, и не ожидая ни секунды идёт на обслуживание первым). Очередь, которую называют очередь (Queue), это честная очередь. Если пришел, то жди.
Как тут ни объясняй, но как всё это сделать на языках программирования далеко не легко понять новичку. Мы итак все знаем, что такое очередь в жизни.
В примере, демонстрируемом ниже, показывается как добавить функцию удаления элемента из очереди. Первый листинг написан без этой функции, второй с ней.

Чтобы добавить функцию удаления, мне пришлось немного поломать голову. Функция удаления элемента описывается таким образом, чтобы элемент удалялся из конца очереди. Так как в приведённом примере начало справа, конец слева, то и удаляться будут те элементы, что слева, а добавляться элементы будут в правую часть списка. Этот момент наглядно демонстрирует сам факт обслуживания очереди по принципу "Первый пришёл, первый ушёл".

Полагаю, по этому коду видно, что всё не так страшно. Сама функция удаления достаточно маленькая и должна быть проста к пониманию. Использовано то же, что и при выводе списка на экран, только при этом мы берём именно сам указатель на начало списка и перенаправляем его на следующее звено. Так как теряя указатель на начало списка мы теряем часть списка, то использована дополнительная переменная. Дополнительная переменная является указателем и в неё запоминается адрес начала списка. Запоминается перед тем, как начало списка поменяется. Начало списка изменили и используя эту переменную освобождаем память от той предыдущей части списка. Всё это должно в достаточно легкой степени быть читаемо прямо из кода.
По поводу того, что из себя представляет очередь, — думаю, что комментарии описывают это лучше всего.
Я видел много примеров, где использована проверка на пустоту очереди в виде отдельной функции, видел примеры с исключениями и видел, где обязательно что-то припаяют туда. На самом деле проверки важны и их нужно прописывать, чтобы исключать всевозможные ошибки, но я написание проверок в основном пропускаю, чтобы они не отвлекали от основной части кода.
Вы могли уже и до этого момента сами писать или просто думать, как организовать очередь, даже не зная, что подобная организация работы с памятью называется очередью.
Я не стал называть класс именем Queue, предпочтя название List, так как скорее всего это немного облегчит понимание материала. Хотя логично называть вещи так, чтобы их имена соответствовали их сути, и во встречаемы примерах часто можно встретить название Queue. Название Queue красноречиво выражает организацию работы с памятью FIFO. Название List обычно наиболее красноречиво выражает организацию работы с памятью по принципу двусвязного списка. Но я немного переиначил, что не совсем правильно.
P. S.

На двусвязном списке очередь строится аналогично, там изменяется только сама функция добавления элементов в список. Т. е. сначала пишется код Двусвязный список в С++ для начинающих, после чего добавляется функция удаления элементов, которая описана в этой теме как void List::del().

Вы могли уже и до этого момента сами писать или просто думать, как организовать очередь, даже не зная, что подобная организация работы с памятью называется очередью.
Я не стал называть класс именем Queue, предпочтя название List, так как скорее всего это немного облегчит понимание материала. Хотя логично называть вещи так, чтобы их имена соответствовали их сути, и во встречаемы примерах часто можно встретить название Queue. Название Queue красноречиво выражает организацию работы с памятью FIFO. Название List обычно наиболее красноречиво выражает организацию работы с памятью по принципу двусвязного списка. Но я немного переиначил, что не совсем правильно.
P. S.

На двусвязном списке очередь строится аналогично, там изменяется только сама функция добавления элементов в список. Т. е. сначала пишется код Двусвязный список в С++ для начинающих, после чего добавляется функция удаления элементов, которая описана в этой теме как void List::del().

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

10 комментариев: Динамические структуры. Очередь на основе однонаправленного списка

  • Виктор говорит:

    Здравствуйте, подскажите пожалуйста как можно эту очередь заполнить рамдомно?
    Заранее спасибо.




    0



    0
    • admin говорит:

      Например так




      0



      0
  • Николай говорит:

    Здравствуйте, хочу реализовать неограниченную очередь где каждые 2 минуты появляется новый элемент, элементы могут ждать 20 минут, а потом приплюсовываются в статистику упущенных, не подскажите как?(максимум допустим 100-200 элементов)




    0



    0
    • admin говорит:

      не очень-то и понял, но наверное как-то так это будет

      я не стал тут писать под 20 минут, просто чтоб было видно как работает и лишний раз много ждать не нужно было.
      lst.AddByTime(100,200,20); — так вот должно как вы спросили срабатывать.




      0



      0
  • Николай говорит:

    Спасибо, буду пробывать разбираться!




    0



    0
    • admin говорит:

      тут, где я показал, я не ставил чтоб каждые 2 минуты. А просто появляется элемент, который появился и ждет какое-то время, когда он подождал, то появляется следующий элемент и так происходит пока счетчик цикла не станет равным ожидаемому максимуму элементов. Можно добавить ожидание в 2 минуты сверху после случайного ожидания элемента, но скорее всего не нужно.
       
      С другой стороны то, как вы спросили больше похоже на параллельное программирование и на очередь с приоритетами. Я НЕ уверен, что прав, но я так думаю. А если я прав, то я подсказать не смогу, как-то это для меня сложно очень. Вы уж извиняйте если что.




      0



      0
  • Николай говорит:

    Ну видимо я не правильно сформулировал свою проблему.По факту мне нужно: приходит элемент с рандумным временем(это я понял как сделать), после этого проходит проверка(ну допустим в магазине, если продавец занят, то он стоит в очереди в среднем 20 минут), так вот если продавец свободен он идет к нему, происходит какой то процесс и он допустим записывается в статистику обслуженного покупателя( это я тоже понимаю как делать), ну и очередь опять пустой становится(заранее не известно какой очередь будет), но если все продавцы заняты он стоит в очереди 20 минут, после чего уходит, и записываем его в статистику упущенного, если бы была очередь из 1го элемента я понимаю как все сделать, но если в очереди будет больше 1го, то мне нужно сделать какой то цикл который будет проверять, освободился ли продавец, а если нет — отнимать у элемента 1 минуту( ну я по тактам делаю, так проще). Собственно в этом и проблема не пойму как сделать, через что лучше вот пока остановился на queue




    0



    0
    • admin говорит:

      Я не смогу дельного посоветовать, кроме как обратиться за помощью на какой форум. На форумах буквально живут крутые дядьки-программеры, которые в зависимости от настроения смогут помочь разобраться и технологически покажут как правильнее делать чтоб не набыдлокодить. Только вопрос надо задавать не типа «вот условие — решите задачу», а как «вот условие, я пробовал так, но не разобрался…», ну дописать разумеется, показать что было сделано и самое главное написать условие задачи так, чтобы вопросов по условию не возникало. Вот приблизительно как в последней попытке.
      На хорошо поставленные вопросы отвечать приятнее, поэтому шансов на ответ точно будет больше.




      0



      0
  • Николай говорит:

    Еще раз спасибо!




    0



    0
  • XanSalo говорит:

    сука поскуда быстр задачу про клетки решил мразь,я не понял хуле так медлено я уже заебался ждать мразь ебанная

    Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? (1<=M,N<=100)
    Пример.
    Если из шахматной доски удалить все клетки одного цвета,то оставшаяся часть распадется на 32 куска.
    Формат входного файла:
    M N
    K ( Кол-во удаленных клеток )
    I1 J1 … Ik Jk ( Положение удаленной клетки )

    Пример ввода:

    3 3
    4
    1 2 2 1 2 3 3 2
    

    Пример вывода:

    5



    0



    0

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

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

− 2 = 2

Поиск

 
     

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

https://www.litres.ru/brayan-p-hogan/html5-i-css3-veb-razrabotka-po-standartam-novogo-pokoleniya-11643814/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

- Алло! Скажите, почему ваш антивирус так долго проверяет фильм? - А как вы хотели? Он его смотрит!

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

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