## Lecture 20 - Queues

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab20$ cd ~/cs170/labs/lab20


### Pseudo-code Submissions

It's that time to submit your Pseudo-code for Karplus Strong! I'll have these graded and scanned sometime this evening.

## Emacs Commands

C-x 3
Split window vertically
C-x 2
Split window horizontally
C-x 1
Remove all but the active pane
C-x 0
Closes the current pane
C-x o
Cycle between windows

### Queues

Stacks allow us to write recursive code iteratively, since we can mimic the system stack. You may have noticed that when we used stacks for the paint bucket program, some weird patterns emerged if something went wrong with the program. A data structure related to Stacks are Queues. Maybe Queues will fix that peculiar pattern you all noticed last week?

Lab Activity 1
Queues

Queues are referred to as First In-First Out, or FIFO, data structures. The data you retrieve is always the oldest from within the data structure. For example, the line of people waiting to get their food at the Commons is a queue. We are again going to use our LinkedList to accomplish this goal.

#### Details

To start off, download my LinkedList module. Place this file in your lab20 directory, so you can use it in your queue definition.

Create a new file called queue.py. In this file, you should define a class Queue, which will inherit the linked list class. You will need to import linked_list at the top of your file so that you can have access to the LinkedList class.

Your class must have the three key methods for a queue, plus two additional methods for testing purposes:

• enqueue - Takes data as a parameter, and adds it to the end of the queue.
• dequeue - Removes the node from the front of the queue, and returns its data.
• peek - Returns the data from the node at the front of the queue without removing it.
• size - Returns an integer, the number of items currently in the queue.
• __str__ - Returns a string representation of the queue.

Make sure that your methods work appropriately. You should handle the special cases in dequeue and peek, when there is nothing currently in the queue by printing an error message, and returning a None value

#### Example

>>> my_queue = Queue()
>>> my_queue.enqueue(1)
>>> my_queue.enqueue(2)
>>> my_queue.enqueue(3)
>>> print(my_queue)
Front -> 1 -> 2 -> 3 -> End
>>> print(my_queue.peek())
1
>>> print(my_queue.dequeue())
1
>>> print(my_queue)
Front -> 2 -> 3 -> End
>>> my_queue.dequeue()
>>> print(my_queue)
Front -> 3 -> End
>>> print(my_queue.dequeue())
3
>>> print(my_queue)
Front -> End
>>> print(my_queue.dequeue())
Error: Queue is empty!
None


#### Hint

• Notice that dequeue is almost exactly the same as pop was from your Stack exercises. The code for dequeue should look exactly the same.

peek is also exactly the same as in stacks as well.

• Enqueue is essentially our append method, so just use that method.

### Challenge

As you might have noticed, the enqueue operation as it stands is a O(n) operation. That is fine for small list sizes, but is undesirable once list sizes become large. This is especially true in comparison to Stacks, which have a O(1) push and pop operation.

We can fix this by adding a tail reference to our linked list. The tail will operate under the invariant that it always refers to the last node in the list, or None if the list is empty. Modify the LinkedList class, so that all of the operations handle the tail attribute accordingly. You will also need to modify your enqueue method of Queue.

Lab Activity 2
Maze Traversal

You have been solving mazes for a majority of your lives by this point. You are probably aware that there are systematic mechanisms for finding the exit of the maze. Typically, we are looking for the shortest path out of a maze. Luckily, using a Queue, we can quickly find this path.

#### Details

The file maze.py contains a simply maze traversal program. The maze is simply represented by a 2-dimensional list of integers, either 0 or 1. 0 means the cell is empty, while 1 means the cell is occupied.

BEFORE YOU DO ANYTHING, READ OVER THIS FILE CAREFULLY. MAKE SURE YOU UNDERSTAND ALL OF THE METHODS THAT ARE PROVIDED FOR YOU!

The can_traverse(self, start_cell, end_cell method of the Maze class takes two tuples as parameters: the starting location and ending location in the maze. This method should return True if there exists a path, and False if a path does not exist. You will use a queue and a loop in order to determine this. This seems pretty complicated, but the code for this is fairly short. If you get stuck, don't forget to check the hint section below.

#### Example

\$ python3 maze.py
Actual: True Expected: True
Actual: False Expected: False
Actual: True Expected: True
Actual: False Expected: False


#### Hint

• You need to create a queue, and initialize it with some value. A good starting value would be the starting cell of the path.

• In your loop, you will dequeue a tuple out of the queue. This is the cell you are exploring. You should mark the cell as VISITED, and add all of the unvisited neighbors to the queue.

• If you are exploring the end cell, then a path exists and you return True. If the queue ever becomes empty without finding the end cell, you should return False.

### Challenge

You might notice that we didn't use recursion for this. However, it is still very possible to write this recursively. As a matter of fact, there are two ways you can write this method recursively.

The first way to write it recursively is very similar to how the paint bucket program worked before you got hold of it. Write a method can_traverse_recursive(self, current_cell, ending_cell), which takes as parameters the current cell and the ending cell. This should return the same values as before. Does this explore more cells than the above code?

The other recursive function is to use a queue, just perform the loop recursively. Write a method can_traverse_rec_queue(self, queue, end_cell), which takes a queue of tuples, and the ending cell as parameters. You will have to write a helper function can_traverse_rec_queue_helper(self, start_cell, end_cell), which initializes the queue and calls the real recursive function. Does this method work as well as the previous method?

#### Submission

When you have finished, create a tar file of your lab20 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab20.tgz lab20/


To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 20. Make sure you include a header listing the authors of the file.