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

Solution 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).

Solution 2

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)

Solution 3

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.

Solution 4

You can also implement a queue with a circular array.

Solution 5

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.

View more solutions

Comments

[Dana]

I'm not sure why you say you need a doubly-linked list. Why not just maintain two pointers, one to the head, and one to the tail?

[Tyler]

Thanks for the reply! I'm not that far in K&R yet so its not easy for me (yet).

[user2665801]

If you remove the element at the head you don't need double linked or to store more than two pointers. Because the head points to the next element.

[paxdiablo]

For a start, it's a queue, not a stack :-). You also don't need a linked list of any sort if you know the maximum size. Just use an array of pointers, which would be more efficient. Queues never insert or delete from the middle.

[Tyler]

I'm working through K&R right now and I haven't reach the chapter about structures yet. Only three more pages!

[Dana]

@Pax - but if you're using an array, aren't you going to need to shuffle the array elements on either insertion or deletion?

[Sunilsingh]

The disadvantage is the posibility of Stack Overflow. It imposes a limit on the maximum number of items queued.

[Sunilsingh]

@Dana - no, you just track the current head and tail indexes, and wrap to 0 when they get to the end.

[user54650]

@Everyone who said it: Yup, If you insert at the tail and delete at the head, you only need a single linked list. @Pax: I'm not fond of using arrays and "hoping" I don't cross a size threshold. I'd reject it for any release application without dynamic arrays... and those can be harder than lists.

[Calyth]

It is a funny solution, and generally something asked in Algorithms class.

[Yngve Sneen Lindal]

It takes some minutes with pen and paper, yes ;-)

[unclerojelio]

Yes true, I figured that for a homework problem he/she would probably be given a max size.