Python - DS: Queues

Question 1

What is a queue? What are the 3 methods of interaction and what do they do?

Answer 1

The first person in the queue is the first to be served. Queues are a First In, First Out or FIFO structure.

This data structure mimics a physical queue of objects like a line of people buying movie tickets. Each person has a name (the data). The first person to enqueue, or get into line, is both at the front.
_____

Queues provide three methods for interaction:

Enqueue - adds data to the “back” or end of the queue

Dequeue - provides and removes data from the “front” or beginning of the queue

Peek - reveals data from the “front” of the queue without removing it

Question 2

What data structure do we use to implement a queue?
How do we roughly do this?
Is traversal allowed?
What is it called when a queue has a limit to its size?

Answer 2

Queues can be implemented using a linked list as the underlying data structure.

The front of the queue is equivalent to the head node of a linked list and the back of the queue is equivalent to the tail node.

Since operations are only allowed affecting the front or back of the queue, any traversal or modification to other nodes within the linked list is disallowed. Since both ends of the queue must be accessible, a reference to both the head node and the tail node must be maintained.

One last constraint that may be placed on a queue is its length. If a queue has a limit on the amount of data that can be placed into it, it is considered a bounded queue.

Question 3

Take a look at the following code based on the Queue class you’ve been working with. What do we know is true for muffins_to_be_eaten?

Answer 3

muffins_to_be_eaten.head == muffins_to_be_eaten.tail

muffins_to_be_eaten was instantiated with a max_size of 10, not a size of 10.

Question 4

Which two Queue methods should alert that the queue is empty?

Answer 4

dequeue() and peek()

Question 5

Why is has_space() a useful method for the Queue class to have?

Answer 5

It allows us to see if we can enqueue() a new value on the end of the queue.

Question 6

Which values go where in Queue‘s __init__() method?

Answer 6

#1: 0,
#2: None,
#3: None,
#4: max\_size

Question 7

If you instantiate an empty queue, what should self.head and self.tail be set to?

Answer 7

None and None

Question 8

What should be the if statement for has_space()?

Answer 8

self.max_size

If the queue has a max_size then it should check if the max_size is greater than its size. If there is no max_size, then there is space for an additional item.

Question 9

What will the return value be if we add a final statement calling dequeue() on sharks_in_the_shark_tank?

Answer 9

“Dhruti”

Question 10

Fill in the method name:

Answer 10

enqueue

Question 11

Fill in the blank:

is_empty() is a useful method for preventing __.

Answer 11

queue underflow

Question 12

Fill in the method name:

Answer 12

dequeue