У меня есть два стека (что следует за LIFO). Я хотел бы знать, могу ли я написать программу C для использования этих двух стеков, работающих как очередь (FIFO).
Один стек используется для вставки новых элементов в очередь. Другой стек используется для удаления элементов. Когда выходной стек пуст, входной стек обращается вспять и становится новым выходным стеком.
В псевдо-C:
typedef struct { stack in, stack out } queue. void insert(queue *q, void *data) { push(q->in, data); } void* remove(queue *q) { if (empty(q->out)) { while (!empty(q->in)) { // q->out = reversed q->in push(q->out, pop(q->in)); } } return pop(q->out); // assumes that it returns NULL if q->out is empty } Это асимптотически такая же сложность, как и обычная очередь, но каждый элемент трогается несколько раз. Поскольку вы работаете в C, почему бы не использовать обычный кольцевой буфер?
Редактировать : Это действительно так, как работают функциональные очереди Окасаки, о которых упоминается ответ @ bdonlan.
Один из таких методов описан в:
Крис Окасаки (Chris Okasaki, 1995). Простые и эффективные чисто функциональные очереди и призы. Журнал функционального программирования, 5, стр. 583-592
Полный текст доступен в формате postscript . Этот метод описан с точки зрения функционального программирования, но нет основополагающей причины, по которой вы не могли реализовать его и в C.
(Почему бы просто не использовать очередь?)
В основном вы используете один стек B, чтобы отменить порядок элементов в другом стеке B, выбирая все элементы из A и нажимая их в B. Когда вы закончите, первый объект, который вы выберете из B, будет первым, что вы нажали на оригинал А.
Если вы нажмете элементы 1, 2, 3, 4 в A в этом порядке, вы получите:
A: 1, 2, 3, 4 (top)
Поп все и нажмите на B:
B: 4, 3, 2, 1 (top)
Если вы начнете выскакивать B, вы будете в порядке:
1, 2, 3, 4
Составная операция представляет собой структуру, подобную FIFO. Однако он не обладает гибкостью соответствующего FIFO, поскольку он работает только в проходах. Это может быть полезно в коде для младших микроcontrollerов, где реализация кучи является проблемой, но вы не должны использовать такие стеки на любом современном компьютере (т.е. после 1980 г.).