ALL that being said (whew), you need to look at your enqueue() and dequeue() logic. A LIFO (Last In First Out) structure is called a Stack. Typically, adding things onto the stack is called "pushing" it onto the stack. Removing things is called "popping" the stack. You might want to rename enqueue and dequeue to push() and pop() to stick with convention.

On to your push/pop logic. You're implementing a stack using a singly-linked list -- that is, a list of nodes that store a pointer to the next node in the list. If you read the code for your enqueue() function, you push an item onto the stack by appending it after the LAST node in the list (the TAIL).

This is not the ideal solution, because there's no easy way to get to the node before the tail. You need to access this because after you free the last node, you need to reset the tail pointer to the new tail node.

Here's a visual representation of what I mean. Imagine you have a stack where you've inserted the letters 'a', 'b', and 'c':

       +-----+ +-----+ +-----+
       | a | --> | b | --> | c |
       +-----+ +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------------------+


Now when you dequeue, you want to remove the 'c'. But that means you need to set Tail to the node containing 'b'. This isn't easy to do because you have to start at Head and iterate all the way until you find the node where (node->next == Tail). This is an inefficient way to search for items, since the time it takes to search is linearly proportional to the length of the list.


What's the better solution, then? Since you have arrows pointing in only one direction, it would be better to insert new items at the HEAD of the list, not at the tail. That way, when you pop an item off, you don't need to search through the list at all -- the new Head = (Head->next).


       +-----+ +-----+ +-----+
       | c | --> | b | --> | a |
       +-----+ +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------------------+

     (remove 'c')
node * nextHead = Head->next;
free(Head);
Head = nextHead;

       +-----+ +-----+
       | b | --> | a |
       +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------+



If you take a moment to examine this approach, you realize that you don't need to store a second pointer to the Tail anymore. You never use it. The only reason you had a tail pointer was so you could insert at one location but remove at another. Now you insert and remove from the same place. That means you enqueue and dequeue (well, push n' pop) functions don't need to accept the TAIL pointer. You know when you're at the tail node because the next ptr of that node will be NULL.


Hope this helps get you on your way...


Take care,

Nik
http://www.bigaction.org/