Implement a Queue using a List.

Problem Statement: Implement a Queue with methods like Enqueue, Dequeue, Size, isEmpty using Lists in Python.

This approach will be slow because of the following reason

It is possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
Source

Test Cases

1. Enqueue
   • Enqueue on an empty Queue.
   • Enqueue on non-empty Queue.
2. Dequeue
   • Dequeue on an empty Queue --> None.
   • Dequeue on a Queue with only one element --> value.
   • Dequeue on a Queue with multiple elements --> value.
3. Size
   • Size on an empty Queue --> None.
   • Size on non empty Queue --> value.
4. isEmpty
   • isEmpty on an empty Queue --> True.
   • isEmpty on non empty Queue --> False.

Algorithm

1. Enqueue
   • Insert the element at first index of the list.
   • If an element is already present at the index, it will be shifted one bit.
2. Dequeue
   • If queue is empty,
     • return None
   • Else,
     • Delete the last element from the list
     • Return the element
3. Size
   • Return the length of the list.
4. isEmpty
   • If list is empty,
     • return True.
   • Else,
     • return False

Time and Space Complexity

1. Enqueue.
   • Time complexity: Best case - O(1), Worst case - O(n)
   • Space complexity: O(1)
2. Dequeue.
   • Time complexity: O(1)
   • Space complexity: O(1)
3. Size
   • Time complexity: O(1)
   • Space complexity: O(1)
4. isEmpty
   • Time complexity: O(1)
   • Space complexity: O(1) ***

Code

class Queue(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, data):
        self.items.insert(0, data)

    def dequeue(self):
        if self.isEmpty():
            return None
        print(self.items)
        return self.items.pop()

    def size(self):
        return len(self.items)

Unit Test

import unittest
from queueList import Queue


class TestQueueList(unittest.TestCase):
    def testQueue(self):
        print('Test: Empty Queue')
        queue = Queue()
        self.assertEqual(queue.dequeue(), None)
        self.assertEqual(queue.size(), 0)
        self.assertEqual(queue.isEmpty(), True)

        print('Test: One element')
        queue = Queue()
        queue.enqueue(5)
        self.assertEqual(queue.size(), 1)
        self.assertEqual(queue.dequeue(), 5)
        self.assertEqual(queue.isEmpty(), True)

        print('Test: Multiple elements')
        queue = Queue()
        queue.enqueue(1)
        queue.enqueue(2)
        queue.enqueue(3)
        self.assertEqual(queue.size(), 3)
        self.assertEqual(queue.dequeue(), 1)
        self.assertEqual(queue.dequeue(), 2)
        self.assertEqual(queue.isEmpty(), False)
        self.assertEqual(queue.dequeue(), 3)
        self.assertEqual(queue.isEmpty(), True)
        print('Success: testQueue')


def main():
    test = TestQueueList()
    test.testQueue()


if __name__ == '__main__':
    main()

Github repo

Happy coding !!!