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

У меня есть две стопки (которые следуют за ЛИФО). Я хотел бы знать, могу ли я написать программу на языке Си, чтобы использовать эти два стека как очередь(FIFO).

3 2
stack queue

3 ответа:

Один стек используется для вставки новых элементов в очередь. Другой стек используется для удаления элементов. Когда выходной стек пуст, входной стек реверсируется и становится новым выходным стеком.

В псевдо-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, почему бы не использовать обычный кольцевой буфер?

Edit : именно так работают функциональные очереди Okasaki это упоминалось в ответе @bdonlan.

4

Один из таких методов описан в:

Крис Окасаки (1995). Простые и эффективные чисто функциональные очереди и деки. Журнал функционального программирования, 5, стр. 583-592

Полный текст доступен в формате postscript . Этот метод описан в терминах функционального программирования, но нет фундаментальной причины, по которой вы не могли бы реализовать его также и на языке Си.

2

(Почему бы просто не использовать очередь?)

В основном вы используете один стек B, чтобы изменить порядок элементов в другом стеке B, выталкивая все элементы из A и помещая их в B. Когда вы закончите, первый объект, который вы вытащите из B, будет первым, который вы вставили в исходный A.

Если вы задвинете элементы 1, 2, 3, 4 В A в таком порядке, вы получите: 

A: 1, 2, 3, 4 (top)

Поп все и толкать в B: 

B: 4, 3, 2, 1 (top)

Если вы начнете хлопать B, вы попадете внутрь порядок:

1, 2, 3, 4
Составная операция представляет собой ФИФОПОДОБНУЮ структуру. Однако он не обладает гибкостью настоящего ФИФО, поскольку работает только в проходах. Это может быть полезно в коде для низкоуровневых микроконтроллеров, где реализация кучи является проблемой, но вы не должны использовать стеки, подобные этому, на любом современном (т. е. после 1980 года) компьютере.
1