Книга: Программирование на языке Ruby
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
в качестве отправной точки. Потребуется внести не так много изменений.
В первом издании книги был длинный пример, демонстрирующий работу с очередями. Но, как и некоторые примеры, касающиеся стеков, он был исключен ради экономии места.
- 9.2.1. Более строгая реализация стека
- 9.4.1. Реализация графа в виде матрицы смежности
- Реализация языка SQL
- 9.2 Реализация массива ftAID на платформе Windows NT
- Favicon – делаем сайт более заметным для пользователей
- Как сделать перезапись файлов в Проводнике более удобной?
- При печати появляется сообщение об ошибке подсистемы Диспетчера очереди печати. Что делать?
- Как сделать движения мышью более точными?
- Реализация семафоров в Linux
- Более сложные трансформации
- 16.8. Реализация отношений в Core Data
- 10.16. Реализация с использованием семафоров System V