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

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

  Первое, что стоит сказать: Добавляются элементы в очередь точно также как и в стек, удаляются с конца списка, а не с начала как в стеке.

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

  Как тут не объясняй, но как все это сделать на языках программирования далеко не легко понять выслушивая все объяснения. Мы итак все знаем что такое очередь в жизни

Код C++ Очередь на основе списка LIFO (Сначала обычный стек)

  Это всё я уже описывал ранее. Если кто-то плохо знаком с этим кодом, то чуть более подробно он изъясняется в статье С++ для начинающих Однонаправленный список LIFO

  Далее идет то, над чем я и ломал голову. Функция удаления элемента описывается таким образом, чтобы элемент удалялся из конца очереди. (Так как в приведенном примере начало справа, конец слева, то и удаляться будут те элементы, что слева, а добавляться они будут в правую часть списка)

Код C++ Очередь на основе списка LIFO (Сначала обычный стек)

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

  По поводу того что из себя представляет очередь думаю комментарии описывают лучше всего.

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

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

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

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 не будет опубликован.

Поиск

 
     

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

https://www.litres.ru/tom-stuart-2/teoriya-vychisleniy-dlya-programmistov/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

- Сынок, сходи в магазин? - А волшебное слово? - Отключу интернет! - Уже бегу!

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

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