%load_ext watermark
%watermark -a 'Sebastian Raschka' -u -d -v
Sebastian Raschka last updated: 2016-08-02 CPython 3.5.1 IPython 5.0.0
Queues are one of the basic, linear datastructures that have the characteristical 2 end points (here: a front and an end). Queues belong to the so-called FIF (first in, first out) data structures, which means that the first element that has been added is the the first to be removed (in contrast to the last in, first out LIFO principle that is implemented in stacks). So, if we enqueue
an item to a queue, we add it to its end, and if we dequeue an item, we remove it from the front:
Basically, you can picture a queue as a line of people waiting in front of the cahsier at the supermarket. A common application of queues is the PBS/TORQUE scheduler for managing jobs on a computing cluster.
class Queue(object):
def __init__(self):
self.data = []
def enqueue(self, item):
self.data.insert(0, item)
def dequeue(self):
return self.data.pop()
def show_front(self):
return seld.data[-1]
def show_end(self):
return seld.data[0]
q = Queue()
q.enqueue(1)
print(q.data)
q.enqueue('a')
print(q.data)
q.enqueue(3)
print(q.data)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.data)
[1] ['a', 1] [3, 'a', 1] 1 a 3 []
Note that we used a simple python list
object to implement a primitive example of a queue. The disadvantage of this is that one of the two operations (either enqueue or dequeue) will have a time complexity of O(n), since we have to either delete from the beginning or insert at the beginning of the list
. A better way to implement a queue would be to use a doubly linked list.
Deques (not to be confused with the "dequeue" operation in queues) is a datastructure that is closely related to queues. Deque simply stands for "double-ended queue," and as the name implies, it allows us to add and remove items at both sides of a queue.
class Deque(object):
def __init__(self):
self.data = []
def add_front(self, item):
self.data.insert(0, item)
def remove_front(self):
return self.data.pop(0)
def add_end(self, item):
self.data.append(item)
def remove_end(self):
return self.data.pop()
def show_front(self):
return seld.data[-1]
def show_end(self):
return seld.data[0]
Again, because of the nature of Python lists, the remove_front
and add_front
become O(n) operations.