Как я могу использовать два стека (LIFO), чтобы он мог работать как очередь (FIFO)?

У меня есть два стека (что следует за 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 г.).