LINUX.ORG.RU

Реализация очереди, используя стек


0

0

Нужно реализовать fifo queue, используя абстрактную реализацию стека (для вывода одного алгоритма из другого, детали в общем не важны). Есть стандартный метод: два стека Butt и Head; чтобы вставить элемент в очередь, push'аем его в Butt, чтобы достать елемент из очереди, pop'аем его из Head, если он не пустой, а если пустой, то по очереди pop'аем все из Butt и push'аем в Head, а потом pop'аем из Head. Получается, если начинать с пустой очереди, амортизированная стоимость одной операции над ней - не больше трех стековых операций. Для задачи достаточно, но просто интересно, есть ли более хитрый подход.

★★★★★

Re: Реализация очереди, используя стек

хм, а если в основу положить _один_ список. где операция push является обёрткой над lst_add_to_head, а операция pop - над lst_del_from_tail.

или саму реализацию стека ломать нельзя? (из описания не совсем понятно, можно ли менять контекст абстракции)

asgard ()

Re: Реализация очереди, используя стек

Гм... Кхем... Ты, всё-таки, поосторожнее с этими "push'аем в Butt".

Miguel ★★★★★ ()
Ответ на: Re: Реализация очереди, используя стек от asgard

Re: Реализация очереди, используя стек

Есть стек, умеющий push и pop. Реализацию менять нельзя (можно считать, что она неизвестна). Нужна очередь, умеющая enqueue и dequeue с разумной стоимостью в стековых операциях.

grob ★★★★★ ()
Ответ на: Re: Реализация очереди, используя стек от asgard

Re: Реализация очереди, используя стек

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

grob ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.