# Queue

## Fundamentals

• A type of linear data structure
• Queues’ operations are subset of Arrays
• Can only add element (tail) from one end and remove element from the other end (head)
• First in First out

## Implementation

• I will implement a stack with the help of the dynamic array I built before

### Dynamic Array Code

class Array:
def __init__(self, arr=None, capacity=10):
if isinstance(arr, list):
self._data = arr[:]
self._size = len(arr)
return
self._data = [None] * capacity
self._size = 0

def get_size(self):
return self._size

def get_capacity(self):
return len(self._data)

def is_empty(self):
return self._size == 0

"""delete from back to front"""
if not 0 <= index <= self._size:
raise ValueError(
'add failed. Require index >= 0 and index <= array sise.')
if self._size == len(self._data):
if self._size == 0:
self._resize(1)
else:
self._resize(2 * len(self._data))
for i in range(self._size - 1, index - 1, -1):
self._data[i + 1] = self._data[i]
self._data[index] = e
self._size += 1

def get(self, index):
if not 0 <= index < self._size:
raise ValueError('get failed. Index is illegal.')
return self._data[index]

def get_max(self):
res = max(self._data[:self.get_size()])
return res

def get_max_index(self):
return self.find_index(self.get_max())

def get_last(self):
return self.get(self._size - 1)

def get_first(self):
return self.get(0)

def set(self, index, e):
if not 0 <= index < self._size:
raise ValueError('set failed. Index is illegal.')
self._data[index] = e

def contains(self, e):
for i in range(self._size):
if self._data[i] == e:
return True
return False

def find_index(self, e):
for i in range(self._size-1,-1,-1):
if self._data[i] == e:
return i
return -1

def remove(self, index):
if not 0 <= index < self._size:
raise ValueError('remove failed. Index is illegal.')
ret = self._data[index]
for i in range(index + 1, self._size):
self._data[i - 1] = self._data[i]
self._size -= 1
# if len(self._data) = 1，len(self._data) // 2=0 not valid
if (self._size == len(self._data) // 4 and len(self._data) // 2 != 0):
self._resize(len(self._data) // 2)
return ret

def remove_first(self):
return self.remove(0)

def remove_last(self):
return self.remove(self._size - 1)

def remove_max(self):
return self.remove(self.get_max_index())

def peek_max(self):
return self._data[self.get_max_index()]

def remove_element(self, e):
index = self.find_index(e)
if index != -1:
self.remove(index)

def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data

def swap(self, i, j):
if i < 0 or i >= self._size or j < 0 or j >= self._size:
raise ValueError('Index is illegal.')
self._data[i], self._data[j] = self._data[j], self._data[i]

def __str__(self):
return str('Array : {}, capacity: {}'.format(self._data[:self._size], self.get_capacity()))

def __repr__(self):
return self.__str__()


### Queue Code

class ArrayQueue:
def __init__(self, capacity=0):
self._array = Array(capacity)

def get_size(self):
return self._array.get_size()

def is_empty(self):
return self._array.is_empty()

def enqueue(self, E):

def dequeue(self):
return self._array.remove_last()

def get_front(self):
return self._array.get_first()

def __str__(self):
return str('ArrayQueue : {}'.format(self._array))

def __repr__(self):
return self.__str__()


### Test

from time import time
from random import randint

def test_enqueue(queue, op_count):
start_time = time()
for _ in range(op_count):
queue.enqueue(randint(1,op_count))

end_time = time()
return end_time - start_time

def test_dequeue(queue, op_count):
start_time = time()
for _ in range(op_count):
queue.dequeue()

end_time = time()
return end_time - start_time

op_count = 10000
array_queue = ArrayQueue()
print(test_enqueue(array_queue, op_count))
print(test_dequeue(array_queue, op_count))

0.021357059478759766
0.00955510139465332


## Complexity

### enqueue(E)

• O(1) on average when there’s no resize involved

• O(n)

• O(1)

• O(1)

• O(1)