Introduction

Its Friday night and you have arrived late at your favourite restaurant.  There is a line up out the door.  Fortunately, you are a computer scientist and you know what a LIFO list is, so you walk up to the host and say you would like the next available table.  Unfortunately, you are informed that the line-up to this restaurant is first come-first served, so you have to wait until everyone in front of you gets a table first.  Does this sound familiar?

The above is an example of a first-in, first-out or FIFO list.  These structures exist when it is desired that items be processed in the order that they arrive.  Sometimes, this is important to ensure fairness (e.g. line-ups at the bank), and sometimes it is important because it alters the nature of the algorithm (e.g. traversals of search trees).  FIFO lists are known more simply as queues.
 

Resources

• For starters, here's an example of a queue.  As an abstract data type (ADT), a queue has two primary methods (enqueue and dequeue).  This animation demonstrates these methods of the queue ADT.
• Now that you understand the concept of a queue, it's time to examine the implementation.  This queue demo allows you to see how the queue operations affect an array-based, circular queue implementation.  You can also see a scripted demo.