Queues

A queue is another data structure designed to process temporary data. It’s like a stack in many ways, except that it processes data in a different order. Like a stack, a queue is also an abstract data type.

You can think of a queue as a line of people at the movie theater. The first one in the line is the first one to leave the line and enter the theater. With queues, the first item added to the queue is the first item to be removed. That’s why computer scientists apply the acronym FIFO to queues: first in, first out.

As with a line of people, a queue is usually depicted horizontally. It’s also common to refer to the beginning of the queue as its front and the end of the queue as its back.

Like stacks, queues are arrays with three restrictions (it’s just a different set of restrictions):

Data can be inserted only at the end of a queue. (This is identical behavior to the stack.)
Data can be deleted only from the front of a queue. (This is the opposite behavior of the stack.)
Only the element at the front of a queue can be read. (This, too, is the opposite of behavior of the stack.)

Let’s see a queue in action, beginning with an empty queue.

First, we insert a 5 (a common term for inserting into a queue is enqueue, but we’ll use the terms insert and enqueue interchangeably):

/books/45079/OEBPS/stacks_and_queues/insert_5.png

Next, we insert a 9:

/books/45079/OEBPS/stacks_and_queues/insert_9.png

Next, we insert a 100:

/books/45079/OEBPS/stacks_and_queues/insert_100.png

As of now, the queue has functioned just like a stack. However, removing data happens in the reverse, as we remove data from the front of the queue. (Removing an element from a queue is also known as dequeuing.)

If we want to remove data, we must start with the 5, since it’s at the front of the queue:

/books/45079/OEBPS/stacks_and_queues/remove_5.png

Next, we remove the 9:

/books/45079/OEBPS/stacks_and_queues/remove_9.png

Our queue now only contains one element, the 100.

Queue Implementation

I mentioned that the queue is an abstract data type. Like many other abstract data types, it doesn’t come implemented in many programming languages. Here’s an implementation of a queue:

	class Queue:
	def __init__(self):
	self.data = []

	def enqueue(self, element):
	self.data.append(element)

	def dequeue(self):
	if len(self.data) > 0:
	return self.data.pop(0)
	else:
	return None

	def read(self):
	if len(self.data) > 0:
	return self.data[0]
	else:
	return None

Again, our Queue class wraps the array with an interface that restricts our interaction with the data, only allowing us to process the data in specific ways. The enqueue method allows us to insert data at the end of the array, while the dequeue removes the first item from the array. And the read method allows us to peek at just the very first element of the array.