Creating a FIFO queue in C

Question

Is it possible to create a FIFO 'stack' in C without using 2 stacks?

Thanks!

(Sorry to those who answered the previous one. I was thinking LIFO and meaning FIFO.)

Answer 1

It's very easy. Just implement a doubly-linked list, holding the pointer to the last item in the list.

To add to the queue, create a new node at the beginning, linking it to the previous beginning. (normal list insert)

To remove from the queue, deref the pointer to the last item, change the pointer to the previous-item pointer, and return the last item... (This is why the doubly-linked list. The other option is a singly-linked list and iterating the whole list to get pointers to the last two elements).

Answer 2

Using 2 stacks for this is a funny solution, and a slow one. Why are you mentioning stack when you can use an ordinary queue? It's FIFO you want, right? You could use an array to make a queue, moduloing its length to make it circular.

Answer 3

It sounds like you're trying to make a queue, where you insert at one end and pull from the other.

One way to do that is with a linked list. You can store pointers to the head and tail. When you insert, append the new record to the tail and when you pop something off the queue, you grab the node pointed to by the head pointer. (Or vice verse, it doesn't much matter)

Answer 4

Wouldn't this just be a standard linked list, except you only define functions to pull off the head element and push stuff onto the tail element? You could even do this in a singly linked list with a tail pointer, rather than a fully doubly-linked list.

Answer 5

You can also implement a queue with a circular array.

Answer 6

I think the OP wanted to know how to handle it if all he's got is stacks, for whatever arcane reason. The trick is to remember that pushing stuff onto a stack and then popping it off reverses the order of the items, so you can use two stacks to reverse it twice.

Incoming items get pushed onto stack1, and are all popped off onto stack2 when stack2 is empty. So the first item gets pushed onto stack1, the immediately popped off and pushed onto stack2, ready for output. Subsequent items stack up on stack1 until stack2 is popped, at which point the last item goes on stack2, then the next-to-last, and so on until stack1 is empty again. Now all of the items are restacked on stack2, with the newest at the bottom and the oldest at the top. New pushes continue to build up on stack1, waiting for stack2 to become empty again, and stack2 just produces the items in the original order until it's empty, at which point we repeat the unstack-restack process.

I won't comment about efficiency, etc.; it's just "you could do it that way". I was asked this in an interview and my immediate answer was "What kind of idiot would do that? Just implement an actual queue and be done with it" - I don't think that was the answer they were looking for though.

Answer 7

Although correct solutions are already proposed, I just would like to correct that FIFO's not really a stack.

That question is often found in Algorithms class, where they ask you to build one using stacks, and prove that the amortized cost for insertion and removal is O(1).

FIFOs can be built using doubly-linked list, an array/vector with a begin and end pointer, with circular arrays, etc etc...