DEV Community is a community of 697,080 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

Discussion (2)

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?

CodeWithML

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.