Expert: Zlatko - 3/2/2011

Question
QUESTION: hi,
i'm new in c++. can you please explain me briefly what is FIFO, LIFO and Priority Queue. what are the differences btw them? and can i get some sample of source code for FIFO, LIFO and Priority Queue? it'll help me to understand easily. my advance thanks for ur help.

ANSWER: Hello Ganapathy

As you probably know, a queue is a collection of data that you can add to and remove from, but the removal depends on some scheme.

FIFO stands for First-In-First-Out and it is a scheme where items are removed from the queue in the same order that they were put in. For example, if items were inserted in this order A,B,C, and then removed, they would be removed in this order A,B,C.

LIFO stands for Last-In-First-Out and it is a scheme where the next item to be removed from a queue is the last item that was put in. For example, if items were inserted in this order A,B,C, and then removed, they would be removed in this order C,B,A. First C is removed, because C was the last one inserted. Then all that is left is A and B. Of those two, B was the last one inserted, so it is the next one to be removed.

LIFO and FIFO queues can be implemented efficiently using linked lists where the list has a pointer to the first (or head) and last (or tail) elements.

A priority queue is a collection of data, like the other queue types, but items are removed based on a priority. If you have a number of items with the same priority, then a decision has to be made about which to remove. Within the same priority, the items can be remove in FIFO order or LIFO order. One way to implement a priority queue is as a collection of FIFO or LIFO queues, and that can be done efficiently as a collection of linked lists, but there are other ways as well.

Do you know how to create a linked list ?

---------- FOLLOW-UP ----------

QUESTION: i'm not familiar with queue and linked-list. that's why i'm asking for sample of source code, sir

ANSWER: Hello Ganapathy

I will do a LIFO queue for you because it is the easiest. I will show you how to do it with a linked list, because a linked list is efficient for a LIFO queue. You have to know a little about pointers to understand linked lists, and if you don't know about pointers, then you should try to learn about them.

If you can understand this code, then you can do the FIFO queue as an exercise, but be warned, to do a FIFO queue efficiently, you will need to use a doubly linked list.
See http://en.wikipedia.org/wiki/Doubly-linked_list
and you will need to maintain a head pointer to the first element of the list and a tail pointer to the last element of the list. The code is longer, but does not need any new concepts over the singly linked list used for LIFO. Just remember to add to the head, and remove from the tail.

Unfortunately, I cannot teach you an entire data structures and C course in this post and explaining these ideas without diagrams is hard. Maybe soon I'll do a video explaining pointers and linked lists.

Good luck and best regards
Zlatko


#include <malloc.h>
#include <stdio.h>

/* First lets define a queue item. It is the data
that will be put on the queue. Here I am putting the
data right into the struct which holds linked list pointers,
and this is not a professional design, but for an example it is
good enough.
*/
typedef struct sQueueItem
{
   int data; /* this is the data to be held on the queue, for this example it is an integer */
   struct sQueueItem* pNext; /* The pointer to the next queue item */
} QueueItem;

/*
This is a structure which defines the queue. It is a LIFO queue, so we just need a pointer to
the head of the queue. Items will be added to the head, and removed from the head so that the
last item to be put on is the first item to be taken off.
*/
typedef struct sLifoQueue
{
   QueueItem* pHead;
} LifoQueue;

/*
Here is a function to create the queue
*/

LifoQueue* CreateLifoQueue(void)
{
   LifoQueue* queue = (LifoQueue*)malloc(sizeof(LifoQueue));
   queue->pHead = NULL;
   return queue;
}

/*
Here is a function to add data to the LIFO queue
*/
void LifoAdd(LifoQueue* queue, int data)
{
   /* first allocate a linked list element */
   QueueItem* newItem = (QueueItem*)malloc(sizeof(QueueItem));
   newItem->data = data;
   newItem->pNext = NULL;


   /* Now put it onto the head */
   newItem->pNext = queue->pHead;
   queue->pHead = newItem;
}

/*
Here is a function to remove data from the LIFO queue
The data is put into pData, and the function returns
0 for failure and non-zero for success
*/
int LifoRemove(LifoQueue* queue, int* pData)
{
   QueueItem* item;

   /* return failure if the queue is empty */
   if (queue->pHead == NULL) return 0;

   /* remove the first item */
   item = queue->pHead;
   queue->pHead = queue->pHead->pNext;

   /* get a copy of the item's data */
   *pData = item->data;

   /* free the item memory*/
   free(item);

   /* return success */
   return 1;
}

int main()
{
   int data;

   /* Create the queue */
   LifoQueue* queue = CreateLifoQueue();

   /* Add items to the queue */
   for(data = 0; data < 10; ++data)
   {
       printf("Adding %d to LIFO queue\n", data);
       LifoAdd(queue, data);
   }

   /* Remove all the items from the queue */
   while(LifoRemove(queue, &data) != 0)
   {
       printf("Removed %d from LIFO queue\n", data);
   }

   /* finally free the queue memory */
   free(queue);

   return 1;

}


---------- FOLLOW-UP ----------

QUESTION: thanks a lot, sir. i've got picture on LIFO and FiFO and i've feel better now after go through your sample coding. how about the priority queue, sir? is it the same as these two queues?

Answer
You could implement a priority queue as a collection of LIFO or a collection of FIFO queues where each such queue is dedicated to one priority. Perhaps you could have an array of such queues, where the index into the array represents priority. If you understood the linked list code, you will have no problem imagining an array of queues.

Lets say you've decided that items of the same priority are to be removed in LIFO order, because you already have a LIFO implementation. Then you could have a collection of LIFO queues, with each LIFO queue dedicated to a single priority. When it comes time to remove from the priority queue, you check the LIFO queues from highest priority to lowest and stop as soon as you find one that is not empty. Then remove an element from that queue. That will work if you have a fixed number of priorities. There are more complicated data structures, like heaps which also can be used to make priority queues and I encourage you to search on the internet form more information about the heap data structure.