FIFO is just First In First Out. You could do it easily with a linked list, always adding to the beginning of the list and removing from the beginning of the list.

A small C-like example would be:

[EDIT] - OOops got my FIFO and FILO mixed...editing post...
[EDIT 2] - Actually, even witht the code for a FILO below, you should be able to figure out how to change it to a FIFO. The only function that needs changing would be the remove() function (since it removes from the end of the list instead of the beginning).

myList would then only contain the message "Hello".

I noticed that after I wrote my post and tried to stick a quick edit in saying I was changing the post. Guess it wasn't quick enough.

Okay, as far as the push and pop commands are concerned: I'm slightly confused as to how the data is actually taken into account?

As for the other example of remove... I'm not very familiar with pointers... but I'm assuming I would have to adjust it to loop through lList until lList->next == NULL?

Something like:

LIST *remove(LIST *lList)
{
     LIST *lTemp = lList->next;

     for(;;) {
        lTemp = lTemp->next;
        if( lTemp->next == NULL ) break;
     }

     free(lList);
     return lTemp;
}

If data is not taken into account (I see what you are saying)... then why have you included a data integer in the node_st struct?

I've explained my situation (and what I'm looking to achieve)... but now I'm even more confused as to which data structure I actually need!

The data is there just to let you know there is some data in the node. In other words, instead of 'int data' put all the information you need, like text, length, health point, etc, or a struct with your data. The important thing is that the node encapsulates your data, being it a simple integer or a full class.

Oh, stack... I always say pile instead of stack

Here's my attempt using some Queue structure code I found via Google:

Most of it works well (messages are added and can be displayed). Except, after the first message dies (see SortQueue), garbage is displayed for that specific string and then the rest functions normally for a few more messages before crashing. I'm guess this is down to me breaking the link between the list elements, but I'm not sure how I should really go about it?

typedef struct {
    char message[MSG_SIZE];
    int lifetime, type;
    struct listelement *link;
} listelement;

"Pila" is the Spanish word we use for stack(LIFO), and "pile" is the most common mistake you can expect from a Spanish talker.
There is also another stupid examples of course, like "cola" which also means a$$, we say "cola" instead of buffer:D

Wow, didn't notice you're from Argentina, Paul. Your English certainly doesn't tell. There are quite a few "false friends" between Spanish and most Germanic languages (English, German and Dutch are the ones I use). Took me a few weeks to find out that German / Dutch / English "tempo" (in music) unfortunately doesn't correspond to "tiempo", but rather to "aire", which, in turn, I had taken to mean something like "atmosphere" or "general feel".
In Cuban music, there is also the disturbing fact that one word usually means at least 3 things. For example, a "montuno" can be:
- a pattern the piano, guitar, or tres, plays (a.k.a. "guajeo", "tumbao")
- the second part of a salsa or son, sort of an open vamp section
- the chord sequence used in that part of the music
- a music genre
- a dance
It gets less disturbing once one understands that these seemingly different things, after all, are manifestations of the same thing.
Also, Cubans seem to use the words "bailar" and "tocar" interchangeably when referring to playing an instrument.

Enough OT.