DEV Community

loading...

Implement a Queue using a List.

CodeWithML
Sharing solutions to coding problems.
Originally published at codewithml.netlify.app ・2 min read

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 !!!

Discussion (2)

Collapse
tdhirendra12 profile image
Jesse

Just want to know why we can't create quue object inside main function and pass the ref of queue.size fun'c to test function it gives error like required positional argument ... Can you help?

Collapse
codewithml profile image
CodeWithML Author

I'm assuming you didn't add the second argument.

def main():
    test = TestQueueList()
    queue1 = Queue()
    queue1.enqueue(5)
    test.assertEqual(queue1.size()) 

The second argument required will be the value returned by the function size.
assertEqual compares two values, if both match then the test case will pass, otherwise it will fail.
You should write it like this, in main function

def main():
    test = TestQueueList()
   # Testing inside main function
    queue1 = Queue()
    queue1.enqueue(5)
    test.assertEqual(queue1.size(), 1) 

This will work.