The Self-Taught Computer Scientist

Data Structures
130
raise IndexError('pop from empty queue')
self._size − = 1
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
return temp.data
def size(self):
return self._size
First, you define a 
Node
class to represent the nodes in your queue’s internal linked list:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
Inside your queue, you keep track of its front and rear items in the variables 
self.front
and 
self 
.rear
. You track the front and rear of your queue so you can enqueue and dequeue in constant time. 
You also track your queue’s size in the variable 
self._size
.
def __init__(self):
self.front = None
self.rear = None
self._size = 0
Next, you define a method called 
enqueue
that adds an item to the rear of your queue:
def enqueue(self, item):
self._size += 1
node = Node(item)
if self.rear is None:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
Your method accepts the data you want to store in your queue as a parameter:
def enqueue(self, item):
Inside 
enqueue
, first you increment 
self._size
by 1 because you are adding a new item to your 
queue. Then, you create a new node to store the item in your queue’s internal linked list:
self._size += 1
node = Node(item)

---

Chapter 12 Queues
131
If 
self.rear
is 
None
, it means your queue is empty, so you set 
self.front
and 
self.rear
to the 
node you just created (since there is only one item in your queue, that item is both the rear and the 
front). Otherwise, you assign your new node to 
self.rear.next
to add it to your queue’s internal 
linked list. Then, you assign the new node to 
self.rear
, so it is at the rear of your queue.
if self.rear is None:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
Next, you define a method called 
dequeue
to remove an item from the front of your queue:
def dequeue(self):
if self.front is None:
raise IndexError('pop from empty queue')
self._size − = 1
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
return temp.data
The first line of code in your method throws an exception if you try to dequeue an item when your 
queue is empty:
if self.front is None:
raise IndexError('pop from empty queue')
When you call 
dequeue
, you remove and return the item at the front of your queue. To do this, you 
store the node at the front of your queue (
self.front)
in 
temp
so you can reference it later after you 
remove it from your internal linked list:
temp = self.front
Next, you remove the item at the front of your queue from your queue’s internal linked list by 
assigning 
self.front
to 
self.front.next
:
self.front = self.front.next
If there are no more items in your queue after you remove the item at the front of your queue, you 
set 
self.rear
to 
None
because there is no longer an item at the rear of your queue:
if self.front is None:
self.rear = None

---