This Lesson introduces our second ADT, the Queue. The topics include:
By the end of this lesson, you should be able to
In this lesson, we are going to introduce the Queue ADT. First, we discuss the concept of a Queue, how it works, what its interface is, and how it could be used for solving a problem. Then we get into the code and see how we can develop and use a Queue in Python.
The Queue ADT represents a First-In-First-Out (FIFO) structure. Any waiting line such as the check-out line at a store, the cars at a stop light, or the line-up outside a department store is a Queue.
Figure 2 below shows the conceptual view of a Queue ADT. Queue has two properties named front and rear. When a value is added to the Queue, it will be placed at the rear (end) of the Queue (think of a person joining a line, takes a place at the end of the line). When a value is removed from a Queue, it is the value at the front of the Queue (Think of the person at the front of the line who has waited the longest). The Queue ADT implements First-In-First-Out (FIFO) behaviour because the value removed is the one that has been in the Queue for the longest time.
initialize()
insert(value)
value to the rear of the Queue
remove()
peek()
is_empty()
True if the Queue is empty, False
otherwise
is_full()
True if the Queue is full, False
otherwise
len()
Any implementation of a Queue must define these methods.
The rear of the Queue is the right-most element in the Queue's underlying array. The front of the queue is always position 0. As data is added to the rear of the Queue, the index of the right-most inhabited element increases but the index of the front of the queue never changes. The size of the Queue at any given time is simply the size of the Python list in the Queue. A Queue is empty if its underlying list is empty.
This diagram displays the workings of the array-based Queue. Use and to see how it works:
The following code shows how to implement part of the array-based Queue in Python. The rest is left to you as an exercise for labs and assignments.
__init__
from copy import deepcopy
class Queue:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty queue. Data is stored in a Python list.
Use: queue = Queue()
-------------------------------------------------------
Returns:
a new Queue object (Queue)
-------------------------------------------------------
"""
self._values = []
The Queue initialization is very simple: the Queue data is held in a
Python list attribute named _value, and that attribute is
initialized as an empty list. Note the naming convention - the
attribute name starts with an underscore '_'. This
indicates that no program that uses the Queue should ever refer to
this attribute directly. _value is to be treated as a private
attribute that is available only to the Queue itself. Any and all
attempts to access or modify the Queue must be done through the public
methods, those methods whose names do not start with an underscore.
insert
def insert(self, value):
"""
-------------------------------------------------------
Adds a copy of value to the rear of the queue.
Use: queue.insert(value)
-------------------------------------------------------
Parameters:
value - a data element (?)
Returns:
None
-------------------------------------------------------
"""
self._values.append(deepcopy(value))
return
insert simply uses the Python list method append
to add value to the end of the _values list.
Except for the name, this method is identical to the Stack push
method including the use of deepcopy.
The following code defines the Python magic method __len__,
which allows the use of the len function, as shown in the
Use: comment.
__len__
def __len__(self):
"""
-------------------------------------------------------
Returns the length of the queue.
Use: n = len(queue)
-------------------------------------------------------
Returns:
the number of values in queue.
-------------------------------------------------------
"""
return len(self._values)
The rest of the implementation is left to you as an exercise. Note that in particular the array-based Queue differs from the array-based Stack in how data is removed.
In this section, we are going to solve the maze problem using Queue. In the previous lesson, we used Stack to solve this problem.
The following sample maze is the same one seen when we looked at the Stack ADT.
As mentioned in previous lesson, in this sample maze, the letters represent either a decision point or an end point. We can't tell what the letter represents until we visit the point. X represents the exit point. The rules to follow when solving the maze are:
Repeat steps 1 and 2 until the exit is found.
Note that the above algorithm does not return the path from start to exit. It just determines whether there is a path or not. To get the path, we need a more elaborated algorithm.
The result queue for this maze follows:
The result queue for this maze follows:
Note that although both the stack and queue based algorithms solve the maze, they traverse the maze points in a different order. As with the stack-based solution, changing the order in which points are added to the queue changes the amount of the maze visited.
The array-based implementation of the Queue that we have already seen is very simple to implement, but that simplicity - and the use of the Python list - hides a very inefficient implementation. The array-based implementation adds data to the end of an array upon insertion and takes data from the front of an array upon removal. If, however, we are always removing data from position 0 in the array, how is it that 0 always holds the front of the queue? Every time a value is removed from position 0 all of the following values must be moved up one position in the array. This is a great deal of work - we don't see it when using the Python list, but you can imagine the overhead necessary to implement a Queue this way. (Note that this problem does not happen with an array-based Stack, because values are pushed and popped from only one end of the array and nothing has to be shifted within the array.)
A solution is to implement a circular array. The circle is conceptual only - computer memory is strictly linear - but this concept is fairly easy to grasp. In a circular array items are never shifted from the position they are given when they are inserted into a queue; instead the indexes of the front and rear of the queue change with each insertion or removal.
These diagrams display the circular array as a circle of memory. Use and to see how it works:
The diagram above can be illustrated as a linear array of memory. and work for this diagram as well:
When an item is removed from the front of the queue, the value of the
index front must be changed. If front is a
value from 0 to capacity-1, it gets changed to front+1.
If front is capacity-1, it gets changed to 0.
That is easy to do with the modulus operator:
front = (front + 1) % capacity
The value of rear is handled in a similar manner.
Note that rear refers to the index of the next available
slot in the array, not the index of the last item in the queue. Thus
when the circular queue is empty, front is None
and rear refers to any empty slot in the array. However,
when the queue is full, front refers to the location of
the data at the front of the queue, and rear should be None,
to indicate that there is no location available to insert new data.
Given that Python's list is dynamic, how can we create a fixed size
array from it? We can do so quite simply by filling the list with
placeholders when we create it and never changing the size of the list
(i.e. by never calling pop or append on it)
in any of the Circular Queue methods. The initialization is:
__init__
class Queue:
"""
-------------------------------------------------------
Constants
-------------------------------------------------------
"""
# a default capacity when one is not provided
DEFAULT_CAPACITY = 10
def __init__(self, capacity=DEFAULT_CAPACITY):
"""
-------------------------------------------------------
Initializes an empty queue. Data is stored in a fixed-size list.
Use: target = Queue(capacity)
Use: target = Queue() # uses default max size
-------------------------------------------------------
Parameters:
capacity - maximum size of the queue (int > 0)
Returns:
a new Queue object (Queue)
-------------------------------------------------------
"""
assert capacity > 0, "Queue size must be > 0"
self._capacity = capacity
self._values = [None] * self._capacity
self._front = None # queue has no data
self._rear = 0 # first available index for insertion
self._count = 0 # number of data items
This queue could then be constructed by a call such as:
from Queue_circular import Queue
queue = Queue()
Inside the circular queue, this creates the Python list _values:
[None, None, None, None, None, None, None, None, None, None]
The Circular Queue data structure may change the contents of this list, but may not make the list larger or smaller. i.e. do not use any Python list method that changes the list size such as:
insertappendextendpopremovedelImplementation of the rest of the Circular Queue is left as an exercise for you.
Queue ADT has many uses. In this section, we mention some of the applications of Queue ADT:
Note that the answers we receive from these simulations are only useful if the inputs are reasonable approximations of reality. This requires observation, record-keeping, and data analysis.
As another example, imagine that a grocery store has to decide between opening up more self-serve check-outs or staffing more check-outs. The store has kept records on how many people use the store throughout the day. It knows the minimum, maximum, and average amount of time a customer takes to use a self-serve checkout. It knows the same information for the standard check-outs. It can then run a series of computer simulations using these numbers with more and fewer of each type of check-out and try to determine the best value for their money.
In this lesson, we introduced the Queue ADT and discussed different approaches to implement the Queue ADT using arrays. We discussed how a Queue can be implemented using Python lists and how Queues can be used to solve problems. Later we in the course we will talk about another implementation of the Queue ADT using a linked structure.