The Self-Taught Computer Scientist

Data Structures
132
The last method you define is a method called 
size
that returns the number of items in your queue:
def size(self):
return self._size
With these three methods, you have created a simple queue using a linked list you can add and 
remove data from and check its size. You can now use your queue like this:
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.size())
for i in range(3):
print(queue.dequeue())
>> 3
>> 1
>> 2
>> 3
In the previous code, you created a queue, added the numbers 1, 2, and 3 to it, printed your queue’s 
size, and then printed every item in your queue.
Let’s take a look at what happens inside your queue class when you run this program. When you 
call 
enqueue
, there are no items in your queue, so you add a node to your queue’s internal linked list, 
and it is your queue’s front and rear (Figure 12.4).
Next, you add a 2 to your queue. Now there are two nodes in your queue’s internal linked list, and 
the node with 1 in it is no longer the rear: the node with 2 in it is now the rear (Figure 12.5).
1
F R
Figure 12.4: When there is one item in your queue, it is both the front and the rear.
1
2
F R
R
Figure 12.5: Now the node with 1 in it is the front, and the node with 2 in it is the rear.

---

Chapter 12 Queues
133
Finally, you add a 3 to your queue. Now there are three nodes in your queue’s internal linked list, 
and the node with 2 in it is no longer the rear: the node with 3 in it is (Figure 12.6).
When you call dequeue for the first time, your remove the node with 1 in it. Now the node with 
2 in it is at the front your queue (Figure 12.7).
When you call 
dequeue
for the second time, you remove the node with 2 in it. Now the node with 
3 in it is at the front and the rear of your queue (Figure 12.8).
Now when you call 
dequeue
for the third time, you remove the node with 3 in it, your queue is 
empty, and 
self.front
and 
self.rear
both point to 
None
(Figure 12.9).
R
3
1
2
F R
R