The Self-Taught Computer Scientist

Figure 12.3: Queue operation run times

---

Chapter 12 Queues
129
short amount of time before starting the movie so it can fill up its queue with the video data Netflix 
is sending. Once your television software allows you to start watching, more data will come in, and 
the system will add it to its queue. Using a queue enables the video player to take data packets off
the queue’s front in a fixed, constant amount of time, making the viewing experience smooth, even if the
incoming data comes in at an inconsistent rate. If too many data packets come in too quickly, the 
system keeps the packets in the queue until it’s ready for them. If the packets come in too slowly,
the system can keep playing the packets in the queue until it runs out. Ideally, that doesn’t happen, 
but when you get a “buffering” message, the queue has run out of data, and no streaming can happen 
until it starts to fill up again.
Let’s imagine what a program like this looks like. It probably has a loop that runs until you’ve fin-
ished watching your program. Inside the loop, it has an algorithm. That algorithm is responsible for 
adding data to the queue and for removing and displaying the data to the user in the form of a video. 
Together, this algorithm and an appropriate data structure (a queue) are all you need to stream a movie 
to your television or laptop and further illustrates why programs = data structures + algorithms.
Creating a Queue
There are several different ways to implement a queue in Python. One way is to define a 
Queue
class 
that uses a linked list to keep track of data internally. Here is how to create a queue using a linked list:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class Queue:
def __init__(self):
self.front = None
self.rear = None
self._size = 0
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
def dequeue(self):
if self.front is None:

---