Дек. Простой пример на статическом массиве

Было время, когда я как-то искал определение дека, хотел понять что же это такое и как с ним работать. Честно говоря в то время ни один из примеров я так понять и не смог.

  • Дек — двусторонняя очередь.
  • Дек — это не обязательно работа с динамическим распределением памяти.

Это простой пример неполноценного дека. Реализация дека построена на статическом массиве. В примере для дека будут определены только операции добавления в начало и в конец очереди.

Смысл этой статьи в том, чтобы дать читателю наглядный и простой пример того, что же все-таки такое дек.
Исходный код Visual Studio Express 2012. Дек на статическом массиве

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

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

Буду надеяться, что кому-то эта статья помогла.

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

4 комментария: Дек. Простой пример на статическом массиве

  • Вася пупкин говорит:

    за такой код голову надо отрывать. Вы дек очередью называете. Вы хоть знаете чем они различаются

    • admin говорит:

      не, я идиот, который не знает
      а теперь выкиньте из головы то, что вы самый умный и узрите:
      «Дек (deck) (стек с двумя концами) — линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка.»
      а имитировать дек можно даже на самом обычном массиве, что и проделано в статье.

      также читаем http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%B0%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C

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

      можете сделать свой сайт, написать свою книгу или как-то еще научить людей правильному если не сможете с этим смириться.

  • ва говорит:

    addleft — работает за O(n), это очень плохо, надо O(1).

    • admin говорит:

      На масиве быстрее не сделать. Массив есть массив. Эта статья предназначена, чтобы понимать что из себя представляет дек как конструкция.

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

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

Поиск

 
     
Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

- Я тут котёнка завела. Помоги придумать какое-нибудь компьютерное имя... - Мышка! - Ты чё, это же котик! - Ну, тогда БЛОХ ПИТАНИЕ.

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

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