Problem Statement: Implement a queue using a linked list with methods like enqueue and dequeue.
What is a Queue?
A Queue is a linear data structure, where the elements are stored in a particular order. It follows the FIFO(First In First Out) order in which the operations are performed.
Test Cases:
- Enqueue
- Enqueue on an empty queue
- Enqueue on a non-empty queue
- Dequeue
- Dequeue on an empty queue. --> None
- Dequeue on a non-empty queue. --> value
- getData
- getData on an empty queue. --> None
- getData on a non-empty queue. --> List of elements in queue
Algorithm:
- Enqueue
- Create a new node with data
- If head and tail pointers are None,
- set head and tail to new node
- Else,
- set tail to new node.
- Dequeue
- If the queue is empty,
- return None
- If queue has only one element, i.e head and tail pointers are equal,
- save head's value
- set head and tail value to None
- return value.
- Else,
- save head's value.
- set head to next of head.
- return value.
- If the queue is empty,
- getData
- initialise an empty list and a current pointer pointing to head.
- iterate through the queue till current pointer is not None.
- append value to the list at each iteration
- return the list.
Time and Space Complexity
- Enqueue
- Time: O(1)
- Space: O(1)
- Dequeue
- Time: O(1)
- Space: O(1)
- getData
- Time: O(n)
- Space: O(n)
- Length
- Time: O(n)
- Space: O(1)
Code
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class Queue(object):
def __init__(self):
self.head = None
self.tail = None
def __len__(self):
counter = 0
curr_node = self.head
while curr_node is not None:
counter += 1
curr_node = curr_node.next
return counter
def enqueue(self, data):
node = Node(data)
if self.head is None and self.tail is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def dequeue(self):
if self.head is None and self.tail is None:
return None
data = self.head.data
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
return data
def getData(self):
data = []
curr_node = self.head
while curr_node is not None:
data.append(curr_node.data)
curr_node = curr_node.next
return data
Unit Test
import unittest
from queue import Queue
class TestQueue(unittest.TestCase):
def testEnqueue(self):
print('Test: Enqueue on an empty queue')
qu = Queue()
qu.enqueue(1)
self.assertEqual(qu.getData(), [1])
print('Test: Enqueue on a non-empty queue')
qu = Queue()
qu.enqueue(2)
qu.enqueue(3)
self.assertEqual(len(qu), 2)
self.assertEqual(qu.getData(), [2, 3])
print('Success: enqueue')
def testDequeue(self):
print('Test: Dequeue on an empty queue')
qu = Queue()
self.assertEqual(qu.dequeue(), None)
print('Test: Dequeue on a non-empty queue')
qu = Queue()
qu.enqueue(1)
qu.enqueue(3)
qu.enqueue(5)
self.assertEqual(len(qu), 3)
self.assertEqual(qu.dequeue(), 1)
self.assertEqual(qu.dequeue(), 3)
self.assertEqual(qu.dequeue(), 5)
print('Success: testDequeue')
def main():
test = TestQueue()
test.testEnqueue()
test.testDequeue()
if __name__ == "__main__":
main()
Happy Coding !!! 🌟
Top comments (1)
Remember that it's CS. Understanding over use. If given a restricted environment in maybe a strange language, then it allows recognition. If you were coding at a higher level and needed a queue then you would never implement on top of a linked list in Python for example.