Problem Statement: Implement a Deque with all it's functions using a List.
A Deque is a double ended queue, where elements can be added from both the ends of the queue.
Functions to be implemented
- addRear
- addFront
- getRear
- getFront
- deleteRear
- deleteFront
- isEmpty
- Size
Test Cases
-
addRear
- Add element at the rear of deque on an empty deque.
- Add element at the rear of deque on a non-empty deque.
-
addFront
- Add element at the front of deque on an empty deque.
- Add element at the front of deque on a non-empty deque.
-
getRear
- Get element from the rear of deque on an empty deque --> None.
- Get element from the rear of deque on a non-empty deque --> value.
-
getFront
- Get element from the front of deque on an empty deque --> None.
- Get element from the front of deque on a non-empty deque --> value.
-
deleteRear
- Delete element from the rear of deque on an empty deque --> None.
- Delete element from the rear of deque on a non-empty deque --> value.
-
deleteFront
- Delete element from the front of deque on an empty deque --> None.
- Delete element from the front of deque on a non-empty deque --> value.
-
isEmpty
- isEmpty on an non-empty deque --> True.
- isEmpty on a empty deque --> False.
-
Size
- size on an non-empty deque --> None.
- size on a empty deque --> value.
Algorithm
-
addRear
- Insert the element at the first index of list.
-
addFront
- Insert the element at the last index of list.
-
getRear
- If deque is empty,
- return None.
- Else,
- Get the element present at the first index of list.
- If deque is empty,
-
getFront
- If deque is empty,
- return None.
- Else,
- Get the element present at the last index of list.
- If deque is empty,
-
deleteRear
- If deque is empty,
- return None.
- Else,
- remove the element at the first index of list.
- If deque is empty,
-
deleteFront
- If deque is empty,
- return None.
- Else,
- remove the element at the last index of list.
- If deque is empty,
-
isEmpty
- If list is empty,
- return True.
- Else,
- return False.
- If list is empty,
-
Size
- Return the length of the list.
Time and Space complexity
-
addFront
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
-
addRear
- Time complexity: Best case - O(1), Worst case - O(n)
- Space complexity: O(1)
-
getFront
- Time complexity: O(1)
- Space complexity: O(1)
-
getRear
- Time complexity: O(1)
- Space complexity: O(1)
-
deleteFront
- Time complexity: O(1)
- Space complexity: O(1)
-
deleteRear
- Time complexity: O(1)
- Space complexity: O(1)
-
isEmpty
- Time complexity: O(1)
- Space complexity: O(1)
-
Size
- Time complexity: O(1)
- Space complexity: O(1)
Code
class Deque(object):
def __init__(self):
self.deque = []
def isEmpty(self):
return self.deque == []
def addRear(self, data):
self.deque.insert(0, data)
def addFront(self, data):
self.deque.append(data)
def getRear(self):
if self.isEmpty():
return None
return self.deque[0]
def getFront(self):
if self.isEmpty():
return None
return self.deque[-1]
def removeRear(self):
if self.isEmpty():
return None
return self.deque.pop(0)
def removeFront(self):
if self.isEmpty():
return None
return self.deque.pop()
def size(self):
return len(self.deque)
Unit Test
import unittest
from deque import Deque
class TestDeque(unittest.TestCase):
def testDeque(self):
print('Test: Empty Deque')
deque = Deque()
self.assertEqual(deque.size(), 0)
self.assertEqual(deque.getFront(), None)
self.assertEqual(deque.getRear(), None)
self.assertEqual(deque.removeFront(), None)
self.assertEqual(deque.removeRear(), None)
self.assertEqual(deque.isEmpty(), True)
print('Test: One element')
deque = Deque()
deque.addFront(5)
self.assertEqual(deque.size(), 1)
self.assertEqual(deque.getFront(), 5)
self.assertEqual(deque.removeFront(), 5)
self.assertEqual(deque.isEmpty(), True)
deque.addRear(5)
self.assertEqual(deque.isEmpty(), False)
self.assertEqual(deque.size(), 1)
self.assertEqual(deque.getRear(), 5)
self.assertEqual(deque.removeRear(), 5)
self.assertEqual(deque.isEmpty(), True)
print('Test: Multiple elements')
deque = Deque()
deque.addFront(1)
deque.addRear(3)
deque.addFront(2)
deque.addRear(4)
self.assertEqual(deque.size(), 4)
self.assertEqual(deque.getFront(), 2)
self.assertEqual(deque.removeFront(), 2)
self.assertEqual(deque.size(), 3)
self.assertEqual(deque.removeRear(), 4)
self.assertEqual(deque.getRear(), 3)
self.assertEqual(deque.size(), 2)
self.assertEqual(deque.isEmpty(), False)
self.assertEqual(deque.removeFront(), 1)
self.assertEqual(deque.removeRear(), 3)
self.assertEqual(deque.isEmpty(), True)
print('Success: testDeque')
def main():
test = TestDeque()
test.testDeque()
if __name__ == "__main__":
main()
Top comments (0)