The final linear data structure that we will examine is the queue. Like the stack, the queue is a type of restricted list. However, instead of restricting all the operations to one end of the list as a stack does, the queue allows items to be added at one end of the list and removed at the other end. The animation below should give you a good idea of the abstract view of a queue. Follow the directions to manipulate a simple queue and learn about the operations that a queue provides.

The restrictions placed on a queue cause this structure to be a "first-in, first-out" or FIFO structure. This idea is similar to customer lines at a grocery store. When customer X is ready to check out, he or she enters the tail of the waiting line. When the preceding customers have paid, then customer X pays and exits the head of the line. The check-out line is really a queue that enforces a "first come, first serve" policy.

Now let's take another look at the operations that can be performed on a queue. We will represent these two operations with the following notation:

Item  EnqueueItem(Queue, Item)
Item  DequeueItem(Queue)

These two operations are very similar to the operations we learned for the stack data structure. Although the names are different, the logic of the parameters is the same. The EnqueueItem operation takes the Item parameter and adds it to the tail of Queue. The DequeueItem operation removes the head item of Queue and returns this as Item. Notice that we represent the returned item with a keyword located to the left of the operation name. These two operations are part of the abstract view of a queue. Regardless of how we choose to implement our queue on the computer, the queue must support these two operations.