"""
PROJECT 4 - QUEUES
Name:
PID:
"""
class CircularQueue:
"""
Circular Queue Class
"""
# DO NOT MODIFY THESE METHODS
def __init__(self, capacity=4):
"""
DO NOT MODIFY.
Initialize the queue with an initial capacity
:param capacity: the initial capacity of the queue
"""
self.capacity = capacity
self.size = 0
self.data = [None] * capacity
self.head = 0
self.tail = 0
def __eq__(self, other):
"""
DO NOT MODIFY.
Defines equality for two queues
:return: true if two queues are equal, false otherwise
"""
if self.capacity != other.capacity:
return False
for i in range(self.capacity):
if self.data[i] != other.data[i]:
return False
return self.head == other.head and self.tail == other.tail and self.size == other.size
def __str__(self):
"""
DO NOT MODIFY.
String representation of the queue
:return: the queue as a string
"""
if self.is_empty():
return "Empty queue"
result = ""
str_list = [str(self.data[(self.head + i)%self.capacity]) for i in range(self.size)]
return "Queue: " + (", ").join(str_list)
# -----------MODIFY BELOW--------------
def __len__(self):
"""
O(1) time complexity, O(1) space complexity
:return: the size of the queue
"""
pass
def is_empty(self):
"""
O(1) time complexity, O(1) space complexity
:return: whether or not the queue is empty (bool)
"""
pass
def head_element(self):
"""
O(1) time complexity, O(1) space complexity
:return: the front element of the queue
"""
pass
def tail_element(self):
"""
the last element of the queue
:return: O(1) time complexity, O(1) space complexity
"""
pass
def enqueue(self, val):
"""
Add an element to the back of the queue
O(1)* time complexity, O(1)* space complexity
Do not use python list methods (ie: append)
:param val:
:return: None
"""
pass
def dequeue(self):
"""
Remove an element from the front of a queue.
O(1)* time complexity, O(1)* space complexity
Do not use python list methods (ie: remove, pop)
:return: element popped. If empty, return None.
"""
pass
def tail_dequeue(self):
"""
Remove an element from the back of a queue.
:return: element popped. If empty, return None
O(1)* time complexity, O(1)* space complexity
Do not use python list methods (ie: remove, pop)
"""
pass
def grow(self):
"""
Doubles the capacity of the queue immediately when capacity is
reached to make room for new elements
Moves the head to the front of the newly allocated list
O(n) time complexity, O(n) space complexity
:return:
"""
pass
def shrink(self):
"""
Halves the capacity of the queue immediately if the size
is 1/4 or less of the capacity
Capacity should never go below 4
Moves the head to the front of the newly allocated list
O(n) time complexity, O(n) space complexity
:return:
"""
pass
def greatest_val(w, values):
"""
find the greatest value in the list values at each possible
array of size w. You will append that greatest value to a new list,
and return the list of all greatest values at the end of the function.
You MUST use the CircularQueue data structure and methods to solve
this problem. Any solution that doesn’t use a CircularQueue will
lose all points relating to this function.
If values is not empty, it will only contain valid numbers.
It will never contain strings or Booleans.
w will never be larger than the length of list values
:param w:
:param values:
:return:
"""
pass