LINUX.ORG.RU
Форум — Development  

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


0

0

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

★★★★★
← Установка boost 1.34.0
gdkpixbuf модуь для поддержки формата JPEG2000 →

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

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

asgard ★
()
Ответ на: комментарий от asgard

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

grob ★★★★★
() автор топика
Ответ на: комментарий от asgard

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

grob ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Установка boost 1.34.0
Development
gdkpixbuf модуь для поддержки формата JPEG2000 →