9.2.4. Более строгая реализация очереди

9.2.4. Более строгая реализация очереди

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

class Queue

 def initialize

  @store = []

 end

 def enqueue(x)

  @store << x

 end

 def dequeue

  @store,shift

 end

 def peek

  @store.first

 end

 def length

  @store.length

 end

 def empty?

  @store.empty?

 end

end

Отметим, что класс Queue имеется в библиотеке thread для поддержки многопоточных программ. Имеется даже вариант SizedQueue для организации очереди ограниченного размера.

В упомянутых классах методы имеют короткие имена: enq и deq. У них есть также синонимы push и pop, что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.

Разумеется, класс Queue в библиотеке thread.rb безопасен относительно потоков. Если вы хотите реализовать такой же класс Stack, рекомендую взять Queue в качестве отправной точки. Потребуется внести не так много изменений.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

3. Очереди

Из книги Информатика и информационные технологии: конспект лекций автора Цветкова А В


19. Очереди

Из книги Информатика и информационные технологии автора Цветкова А В


Строгая форма имени

Из книги Язык программирования С# 2005 и платформа .NET 2.0. [3-е издание] автора Троелсен Эндрю

Строгая форма имени Перед установкой компоновочного блока в GAC вы должны назначить компоновочному блоку строгое имя, которое уникальным образом идентифицирует издателя данного двоичного объекта .NET. При этом следует понимать, что "издателем" может быть и отдельный


У6.10 Очереди

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

У6.10 Очереди Описать в виде АТД очереди (первым пришел - первым ушел) в том же стиле, что и стеки. Обратите внимание на общие и отличительные черты этих АТД. (Указание: аксиомы для item и remove должны отличаться, при описании put (s,x) рассмотрите случаи, когда очередь s пуста и


Объект очереди

Из книги Системное программирование в среде Windows автора Харт Джонсон М

Объект очереди До сих пор мы связывали с каждым мьютексом только одно событие, но в общем случае могут существовать несколько предикатов переменных условий. Например, в случае очереди, действующей по принципу "первым пришел, первым ушел" (first in first out, FIFO), поток, который


9.2. Стеки и очереди

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

9.2. Стеки и очереди Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stack и Queue, в отличие от Array и Hash (впрочем, класс Queue есть в библиотеке thread.rb, которую мы еще будем рассматривать).И все же в


9.2.1. Более строгая реализация стека

Из книги Linux: Полное руководство автора Колисниченко Денис Николаевич

9.2.1. Более строгая реализация стека Мы обещали показать, как можно сделать стек защищенным от некорректного доступа. Выполняем обещание! Вот пример простого класса, который хранит внутри себя массив и управляет доступом к этому массиву. (Есть и другие способы, например


26.5. Очереди сообщений

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

26.5. Очереди сообщений 26.5.1. Основные структуры ядра для работы с очередями Очередь сообщений — это связный список, находящийся в адресном пространстве ядра. Каждая очередь имеет свой уникальный идентификатор IPC.Структура ядра msgbuf (описана в файле /usr/src/linux/include/linux/msg.h)


26.5.4. Получение сообщений очереди

Из книги Linux программирование в примерах автора Роббинс Арнольд

26.5.4. Получение сообщений очереди Для получения сообщения используется системный вызов msgrcv():int msgrcv(int msqid, struct msgbuf *msgp, int msgsz, long mtype, int msgflg);Первый аргумент определяет очередь, из которой нужно получить сообщение. Второй аргумент — это адрес буфера, в который будет записано


Очереди

Из книги UNIX: разработка сетевых приложений автора Стивенс Уильям Ричард


Очереди выполнения

Из книги автора

Очереди выполнения Основная структура данных планировщика — это очередь выполнения (runqueue). Очередь выполнения определена в файле kernel/sched.c[21] в виде структуры struct runqueue. Она представляет собой список готовых к выполнению процессов для данного процессора.Для каждого


Очереди запросов

Из книги автора

Очереди запросов Для блочных устройств поддерживаются очереди запросов (request queue), в которых хранятся ожидающие запросы на выполнение операций блочного ввода-вывода. Очередь запросов представляется с помощью структуры request_queue, которая определена в файле <linux/blkdev.h>.