Реализация FIFO с использованием LIFO - PullRequest
Новая
       7

Реализация FIFO с использованием LIFO

9 голосов
/ 12 марта 2012

Глядя на некоторые алгоритмы в сети, я нашел интересный:

Как бы вы реализовали FIFO с использованием LIFO?

Я попробовал себя, но в итоге получил только одинРешение: каждый раз, когда нам нужен элемент front в FIFO, копируйте лифо в другой lifo ( исключая последний элемент, который является передним), достаете передний элемент и удаляйте егозатем скопируйте обратно второй LIFO в первый LIFO.

Но это, конечно, очень медленно, это делает простой цикл вроде этого: 

for(!myfifo.empty()) {
  myfifo.pop();
}

собирается O (n²) вместо O (n) в стандартной реализации FIFO.

Конечно, LIFO не созданы для FIFO, и у нас точно не будет такой же сложности.использование "родного" FIFO и поддельного FIFO на основе LIFO, но я думаю, что, безусловно, есть способ добиться большего успеха, чем O (n²).У кого-нибудь есть идеи по этому поводу?

Заранее спасибо.

Ответы [ 2 ]

13 голосов
/ 12 марта 2012

Вы можете получить сложность амортизированного времени из O(1) за OP FIFO [очередь], используя 2 LIFO [стеки].

Предположим, у вас есть stack1, stack2: 

insert(e):
   stack1.push(e)

take():
   if (stack2.empty()):
      while (stack1.empty() == false):
            stack2.push(stack1.pop())
   return stack2.pop() //assume stack2.pop() handles empty stack already

пример: 

push(1)

|1|  | |
|-|  |-|

push(2)
|2|  | |
|1|  | |
|-|  |-|

pop()
push 2 to stack2 and pop it from stack1:
|1|  |2|
|-|  |-|
push 1 to stack2 and pop it from stack2:
| |  |1|
| |  |2|
|-|  |-|
pop1 from stack2 and return it:
| |  |2|
|-|  |-|

Чтобы получить реальный O(1) [не амортизируется], это намного сложнее и требует больше стеков, посмотрите нанекоторые ответы в этом посте

РЕДАКТИРОВАТЬ: Анализ сложности:

  1. каждый insert() тривиально O(1) [простонажав на stack1]
  2. Обратите внимание, что каждый элемент имеет push() ed и pop() ed максимум дважды, один раз из stack1 и один раз из stack2.Поскольку операций больше нет, то для n элементов мы имеем самое большее 2n push() s и 2n pop() s, что дает нам максимум 4n * O(1) сложность [поскольку оба pop()и push() равны O(1)], что составляет O(n) - и мы получаем амортизированное время: O(1) * 4n / n = O(1)
1 голос
/ 12 марта 2012

И LIFO, и FIFO могут быть реализованы с массивом, единственное различие между ними заключается в том, как работают tail и head указатели. Учитывая, что вы начинаете с LIFO, вы можете добавить два дополнительных указателя, которые будут отражать хвост и голову FIFO, а затем добавить методы для Add, Remove и так далее, используя указатели FIFO.

Тип вывода будет таким же быстрым, как выделенный тип FIFO или LIFO, однако он будет поддерживать оба. Вам необходимо использовать отличительные элементы типа, такие как AddToStack / AddToQueue, RemoveFromStack / RemoveFromQueue и т. Д.

...