Queue

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.
Press here to see how the queue works

 

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s