Implement Deque using a List

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.
getFront
- If deque is empty,
- return None.
- Else,
- Get the element present at the last index of list.
deleteRear
- If deque is empty,
- return None.
- Else,
- remove the element at the first index of list.
deleteFront
- If deque is empty,
- return None.
- Else,
- remove the element at the last index of list.
isEmpty
- If list is empty,
- return True.
- Else,
- return False.
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()

Github repo

Happy Coding !!!

Published 8 Oct 2020

CodewithML on Twitter