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
- Enqueue
- Enqueue on an empty Queue.
- Enqueue on non-empty Queue.
- Dequeue
- Dequeue on an empty Queue --> None.
- Dequeue on a Queue with only one element --> value.
- Dequeue on a Queue with multiple elements --> value.
- Size
- Size on an empty Queue --> None.
- Size on non empty Queue --> value.
- isEmpty
- isEmpty on an empty Queue --> True.
- isEmpty on non empty Queue --> False.
Algorithm
- 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.
- Dequeue
- If queue is empty,
- return None
- Else,
- Delete the last element from the list
- Return the element
- If queue is empty,
- Size
- Return the length of the list.
- isEmpty
- If list is empty,
- return True.
- Else,
- return False
- If list is empty,
Time and Space Complexity
- Enqueue.
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
- Dequeue.
- Time complexity: O(1)
- Space complexity: O(1)
- Size
- Time complexity: O(1)
- Space complexity: O(1)
- 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()
Top comments (2)
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?
I'm assuming you didn't add the second argument.
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
This will work.