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

    def add_last(self, e):
        self.add(self._size, e)

    def add_first(self, e):
        self.add(0, e)

    def add(self, index, e):
        """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):
        self._array.add_last(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

dequeue()

  • O(n)

front()

  • O(1)

getSize()

  • O(1)

isEmpty()

  • O(1)