Implement FIFO Using LIFO

Question

Looking at some of the algorithms on the network, I found an interesting one:

How to implement FIFO using LIFO?

I tried myself, but I had only one solution: every time we need a front FIFO element, copy lifo to another lifo ( excluding the last element, which is the front), get the front element and delete it, and then copy the second LIFO to first LIFO.

But this, of course, is terribly slow, it does a simple loop like this:

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

O (n²) instead of O (n) with the standard FIFO implementation.

Of course, LIFOs don’t do FIFOs, and we certainly won’t have the same difficulty using native FIFOs and fake LIFOs based FIFOs, but I think there is definitely a way to do better than O ( n²). Does anyone know about this?

Thanks in advance.

Answer 1

You can get the amortized time complexity of O(1) per OP FIFO [queue] using 2 LIFO [stacks].

Suppose you have 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 

Example:

 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| |-| |-| 

To get real O(1) [not depreciated], it is much more complicated and requires more stacks, look at some answers in this post

EDIT: Difficulty analysis:

• each insert() is trivial O(1) (just pushing it on stack1 ]
• Note that each push() element ed and pop() no more than two times, once from stack1 and once from stack2 . Since there are no more ops, for n elements we have at most 2n push() and 2n pop() s, which gives us at most 4n * O(1) complexity [since both pop() and push() are O(1) ], which is O(n) - and we get the amortized time: O(1) * 4n / n = O(1)

Answer 2

Both LIFO and FIFO can be implemented using an array, the only difference between them is how the tail and head pointers work. Since you start with LIFO, you can add two extra pointers that will reflect the FIFO tail and head, and then add methods to add, remove, and so on with the FIFO pointers.

The output type will be as fast as the highlighted FIFO or LIFO type, however it will support both. You will need to use distinctive type members such as AddToStack / AddToQueue, RemoveFromStack / RemoveFromQueue, etc.