Очереди как структуры данных. Теория и практика::Журнал СА 5.2014
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Подписка
Архив номеров
Где купить
Наука и технологии
Авторам
Рекламодателям
Контакты
   

  Опросы
  Статьи

День сисадмина  

Учите матчасть! Или как стать системным администратором

Лето – время не только отпусков, но и хорошая возможность определиться с профессией

 Читать далее...

День сисадмина  

Живой айтишник – это всегда движение. Остановка смерти подобна

Наши авторы рассказывают о своем опыте и дают советы начинающим системным администраторам.

 Читать далее...

Виртуализация  

Рынок решений для виртуализации

По данным «Обзора российского рынка инфраструктурного ПО и перспектив его развития», сделанного

 Читать далее...

Книжная полка  

Как стать креативным и востребованным

Издательский дом «Питер» предлагает новинки компьютерной литературы, а также книги по бизнесу

 Читать далее...

Книжная полка  

От создания сайтов до разработки и реализации API

В издательстве «БХВ» недавно вышли книги, которые будут интересны системным администраторам, создателям

 Читать далее...

Разбор полетов  

Ошибок опыт трудный

Как часто мы легко повторяем, что не надо бояться совершать ошибки, мол,

 Читать далее...

Принципы проектирования  

Dependency Inversion Principle. Принцип инверсии зависимостей в разработке

Мы подошли к последнему принципу проектирования приложений из серии SOLID – Dependency

 Читать далее...

Рынок труда  

Вакансия: Администратор 1С

Администратор 1С – это специалист, который необходим любой организации, где установлены программы

 Читать далее...

Книжная полка  

Книги для профессионалов, студентов и пользователей

Книги издательства «БХВ» вышли книги для тех, кто хочет овладеть самыми востребованными

 Читать далее...

Принципы проектирования  

Interface Segregation Principle. Принцип разделения интерфейсов в проектировании приложений

Эта статья из серии «SOLID» посвящена четвертому принципу проектирования приложений – Interface

 Читать далее...

Книжная полка  

Секрет успешных людей

Книги издательства «БХВ» по ИТ рассчитаны на разные категории читателей: от новичков

 Читать далее...

Учебные центры  

Карьерные мечты нужно воплощать! А мы поможем

Школа Bell Integrator открывает свои двери для всех, кто хочет освоить перспективную

 Читать далее...

Гость номера  

Дмитрий Галов: «Нельзя сказать, что люди становятся доверчивее, скорее эволюционирует ландшафт киберугроз»

Использование мобильных устройств растет. А вместе с ними быстро растет количество мобильных

 Читать далее...

Прошу слова  

Твердая рука в бархатной перчатке: принципы soft skills

Лауреат Нобелевской премии, специалист по рынку труда, профессор Лондонской школы экономики Кристофер

 Читать далее...

1001 и 1 книга  
19.03.2018г.
Просмотров: 11252
Комментарии: 0
Потоковая обработка данных

 Читать далее...

19.03.2018г.
Просмотров: 9505
Комментарии: 0
Релевантный поиск с использованием Elasticsearch и Solr

 Читать далее...

19.03.2018г.
Просмотров: 9554
Комментарии: 0
Конкурентное программирование на SCALA

 Читать далее...

19.03.2018г.
Просмотров: 5975
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

 Читать далее...

12.03.2018г.
Просмотров: 6684
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

 Читать далее...

12.03.2018г.
Просмотров: 3978
Комментарии: 0
Глубокое обучение с точки зрения практика

 Читать далее...

12.03.2018г.
Просмотров: 2903
Комментарии: 0
Изучаем pandas

 Читать далее...

12.03.2018г.
Просмотров: 3704
Комментарии: 0
Программирование на языке Rust (Цветное издание)

 Читать далее...

19.12.2017г.
Просмотров: 3714
Комментарии: 0
Глубокое обучение

 Читать далее...

19.12.2017г.
Просмотров: 6204
Комментарии: 0
Анализ социальных медиа на Python

 Читать далее...

19.12.2017г.
Просмотров: 3055
Комментарии: 0
Основы блокчейна

 Читать далее...

19.12.2017г.
Просмотров: 3359
Комментарии: 0
Java 9. Полный обзор нововведений

 Читать далее...

16.02.2017г.
Просмотров: 7171
Комментарии: 0
Опоздавших не бывает, или книга о стеке

 Читать далее...

17.05.2016г.
Просмотров: 10552
Комментарии: 0
Теория вычислений для программистов

 Читать далее...

30.03.2015г.
Просмотров: 12264
Комментарии: 0
От математики к обобщенному программированию

 Читать далее...

18.02.2014г.
Просмотров: 13901
Комментарии: 0
Рецензия на книгу «Читаем Тьюринга»

 Читать далее...

13.02.2014г.
Просмотров: 9033
Комментарии: 0
Читайте, размышляйте, действуйте

 Читать далее...

12.02.2014г.
Просмотров: 6996
Комментарии: 0
Рисуем наши мысли

 Читать далее...

10.02.2014г.
Просмотров: 5304
Комментарии: 3
Страна в цифрах

 Читать далее...

18.12.2013г.
Просмотров: 4532
Комментарии: 0
Большие данные меняют нашу жизнь

 Читать далее...

18.12.2013г.
Просмотров: 3345
Комментарии: 0
Компьютерные технологии – корень зла для точки роста

 Читать далее...

Друзья сайта  

 Очереди как структуры данных. Теория и практика

Архив номеров / 2014 / Выпуск №5 (138) / Очереди как структуры данных. Теория и практика

Рубрика: Разработка /  Проектирование

Александр Календарев АЛЕКСАНДР КАЛЕНДАРЕВ, РБК Медиа, программист, akalend@mail.ru

Очереди как структуры данных
Теория и практика

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

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

В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (First-In-First-Out – первым вошел – первым вышел).

Основные операции, которые можно осуществить с элементами очереди:

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

Существует два классических варианта реализации очередей: с помощью массива и с помощью списка. Есть еще и другие варианты, но принципиально в них заложены именно эти две идеи.

Рисунок 1. Реализация очереди с помощью массива

Рисунок 1. Реализация очереди с помощью массива

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

Чтобы не сдвигать все элементы очереди, в отдельном поле Pbeg будем хранить индекс элемента массива, с которого начинается очередь, и Pend – индекс конца очереди. Как только один из указателей достигает границы массива, например, Pmax, то он сразу сбрасывается в ноль (P0). Добавление элементов происходит в конец очереди – Pend, а изъятие из начала очереди – Pbeg. Можно и наоборот – это не принципиально. Такой подход имеет один недостаток – фиксированный размер очереди, который не может превышать размерность массива, – Pmax.

Рисунок 2. Реализация очереди с помощью двух направленных списков

Рисунок 2. Реализация очереди с помощью двух направленных списков

В отличие от классического списка реализация очереди предполагает наличие двух указателей: один на начало очереди – Pbeg, второй на ее конец – Pend. В списках указатели на первый и последний элемент очереди принято называть «голова» (head) и «хвост» (tail). Вставляя элемент в очередь, мы его вставляем перед первым элементом, на который указывает указатель Pbeg, а впоследствии присваиваем указателю адрес этого элемента, таким образом, он становится первым. Извлечение из очереди, напротив, возвращает указатель на последний элемент – Pend, а сам указатель передвигаем на предыдущий. Чтобы это у нас работало, нам нужно использовать двунаправленный список.

Статью целиком читайте в журнале «Системный администратор», №5 за 2014 г. на страницах 49-53.


Комментарии отсутствуют

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

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru