The Self-Taught Computer Scientist

Figure 12.6: The node with 1 in it is the front, and the node with 3 in it is the rear.
3
1
2
F R
F R
R
Figure 12.7: When you dequeue the 1, the front changes to the node with 2 in it.
3
1
2
F R
F R
F R
Figure 12.8: When you dequeue again, there is only one item left, so it is both the front and the rear.
3
1
2
F R
F R
F R
Figure 12.9: Now your queue is empty.

---

Data Structures
134
Python’s Built- In Queue Class
Python also has a built- in class to create a queue you can use. Here is how it works:
from queue import Queue
q = Queue()
q.put('a')
q.put('b')
q.put('c')
print(q.qsize())
for i in range(3):
print(q.get())
>> 3
>> a
>> b
>> c
First, you import 
Queue
from the 
queue
module:
from queue import Queue
Next, you create a queue by calling the 
Queue
method:
q = Queue()
You add three strings onto your queue using the built- in method 
put
:
q.put('a')
q.put('b')
q.put('c')
Then you check your queue’s size using the built- in method 
qsize
:
print(q.qsize())
Finally, you use a 
for
loop to pop all the items off your queue and print them:
for i in range(3):
print(q.get())
Create a Queue Using Two Stacks
A common technical interview question is to create a queue using two stacks. Here is how to do it:

---

Chapter 12 Queues
135
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
def enqueue(self, item):
while len(self.s1) != 0:
self.s2.append(self.s1.pop())
self.s1.append(item)
while len(self.s2) != 0:
self.s1.append(self.s2.pop())
def dequeue(self):
if len(self.s1) == 0:
raise Exception("Cannot pop from empty queue")
return self.s1.pop()
First, you define a 
Queue
class with two internal stacks, 
self.s1
and 
self.s2
:
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
Next, you define a method called 
enqueue
to add a new item to your queue:
def enqueue(self, item):
while len(self.s1) != 0:
self.s2.append(self.s1.pop())
self.s1.append(item)
while len(self.s2) != 0:
self.s1.append(self.s2.pop())
When you add a new item to your queue, you need to put it at the rear of your first stack. Because 
you can add items only to the front of a stack, to put something at the rear of your first stack, you 
have to pop everything off it, add the new item, and then put everything back on.
In this case, you pop everything from your first stack, put it all onto your second stack, add the 
new item to your first stack (once it is empty), and then put everything back onto it. When you finish, 
your first stack will have all the original items, plus the new item at its rear.
while len(self.s1) != 0:
self.s2.append(self.s1.pop())
self.s1.append(item)
while len(self.s2) != 0:
self.s1.append(self.s2.pop())

---