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

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

2 голосов
/ 05 февраля 2011

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

Ответы [ 3 ]

4 голосов
/ 05 февраля 2011

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

В псевдо-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.

2 голосов
/ 05 февраля 2011

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

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

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

1 голос
/ 05 февраля 2011

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

В основном вы используете один стек 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

Составная операцияявляется FIFO-подобной структурой.Тем не менее, он не обладает гибкостью правильного FIFO, поскольку работает только в проходах.Это может быть полезным в коде для низкоуровневых микроконтроллеров, где реализация кучи является проблемой, но вы не должны использовать такие стеки на любом современном (то есть после 1980 года) компьютере.

...