3
\$\begingroup\$

I created this double-ended queue using list. I supported the standard operations such as push, pop, peek for the left side and the right side.

I used an integer mid to track the midpoint of the deque. This way elements can be inserted to the left or to the right appropriately. Here is a list of efficiencies according to Python's documentation for list.

enter image description here

class Deque():
    def __init__(self):
        self.array = []
        self.mid = 0

    def push_left(self, val):
        self.array.insert(self.mid, val)

    def push_right(self, val):
        self.array.insert(self.mid, val)

        self.mid = self.mid + 1

    def pop_left(self):
        # If mid is the rightmost element, move it left.
        if self.mid == len(self.array) - 1:
            self.mid = self.mid - 1

        if (len(self.array) > 0):
            return self.array.pop()
        else:
            return None

    def pop_right(self):
        # If the mid is not the leftmost element, move it right.
        if self.mid > 0:
            self.mid = self.mid - 1

        if (len(self.array) > 0):
            return self.array.pop(0)
        else:
            return None

    def peek_left(self):
        if (len(self.array) > 0):
            return self.array[-1]
        else:
            return None

    def peek_right(self):
        if (len(self.array) > 0):
            return self.array[0]
        else:
            return None

    def __str__(self):
        ret = "["

        if len(self.array) == 0:
            return "[]"

        for idx, val in enumerate(self.array):
            if idx == self.mid:
                ret = ret + "({}) ".format(str(val))
            else:
                ret = ret + str(val) + " "

        return ret.strip() + "]"


# Test case
d = Deque()

d.push_left(19)
d.push_left(11)
d.push_left(23)
print(d)

d.push_right(17)
d.push_right(13)
print(d)

d.pop_left()
d.pop_left()
print(d)

d.pop_left()
d.pop_right()
print(d)

# Edge Case where 13 is the only element. Insert 29 left of it.
d.push_right(29)
print(d)

d.push_left(11)
print(d)

d.pop_right()
d.pop_right()
print(d)

# Edge Case where 13 is the only element. Insert 21 right of it.
d.push_left(21)
d.push_left(29)
print(d)

d.push_right(13)
d.push_right(21)
print(d)  # Symmetry!

I'm aware that the __str__ method isn't particularly efficient as it is O(n).

I specifically want to know:

  • Are there any edge cases I missed?
  • Are there any obvious optimisations I missed?
  • Are there any bugs in the data structure itself?
  • Is the code properly "Pythonic"?
\$\endgroup\$
1
  • \$\begingroup\$ In terms of terminology, what youʼve implemented would normally not be called a deque since it doesnʼt satisfy the expected asymptotic runtime guarantees. Furthermore, what is the point of mid? It is not part of the common definition of a deque. \$\endgroup\$ Dec 17, 2019 at 11:47

4 Answers 4

2
\$\begingroup\$
  • Make your deque easier to test by adding an __iter__ method. Then you can easily iterate over it or call useful functions that accept an iterable on it, like list().

    def __iter__(self):
        yield from self.array
    
  • Use unittest to test your code. Much faster and more reliable than writing print statements and checking the results manually via visual inspection on each program run. A well-written test suite doubles as documentation of the expected behavior of your data structure, which brings me to my next point...

  • I know you called it a deque/double-ended queue, but looking at the implementation it's unclear to me how this data structure is supposed to behave. If push_left and push_right are supposed to behave like appendleft and append in collections.deque, then I don't think your deque implementation actually works as advertised. Comparing collections.deque and your deque:

    import unittest
    from collections import deque
    
    # [...]
    
    class TestDeque(unittest.TestCase):
        # passes
        def test_collections_deque(self):
            d = deque()
            d.appendleft(19)
            d.appendleft(11)
            d.appendleft(23)
            d.append(17)
            d.append(13)
            self.assertEqual(list(d), [23, 11, 19, 17, 13])
    
        # fails
        def test_custom_deque(self):
            d = Deque()
            d.push_left(19)
            d.push_left(11)
            d.push_left(23)
            d.push_right(17)
            d.push_right(13)
            # Note: must implement __iter__ in order to call `list` on Deque
            # list(d) == [17, 13, 23, 11, 19]
            self.assertEqual(list(d), [23, 11, 19, 17, 13])
    
    if __name__ == "__main__":
        unittest.main()
    
\$\endgroup\$
2
  • \$\begingroup\$ You are completely right. I overcomplicated the concept of a deque. I should have consulted the standard lib, that was really silly of me. \$\endgroup\$ Dec 17, 2019 at 9:47
  • \$\begingroup\$ github.com/taimoorgit/Data-structures-practice/blob/master/… Here is a fixed example of an implementation, tested using the unittest library against collections.dequeue \$\endgroup\$ Dec 17, 2019 at 9:48
3
\$\begingroup\$
  1. It's not clear at all to me what the mid pointer represents. It doesn't seem like it stays in the middle of the array.

  2. Why not use collections.deque? https://docs.python.org/2/library/collections.html#collections.deque

  3. Implementing an efficient deque is much easier with a linked list than with an array IMO.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Point 3: I think CPython uses a combination of arrays and a linked list to implement its deque. The array is 64 blocks which reduces the frequency of allocation calls and points to previous/next blocks. But a lot of the logic is array-based. Going all linked list is possibly easier to program but almost certainly less efficient than including some array logic (?). \$\endgroup\$
    – ggorlen
    Dec 16, 2019 at 22:59
  • \$\begingroup\$ It's very simple to make a linked list implementation do everything in O(1) time (and to satisfy yourself that this is so), but the constant factor can be a bit higher than an array-backed solution because you're doing more frequent memory allocations. \$\endgroup\$
    – Samwise
    Dec 16, 2019 at 23:24
  • \$\begingroup\$ The mid variable represents is the last element queued at the front of the array. That way when something is queued to the back of the deque, it is inserted in the array to the right of whatever mid is. I'll rename it to make it more clear. \$\endgroup\$ Dec 17, 2019 at 0:06
  • \$\begingroup\$ As for why: I'm practicing data structures for coding interviews, so I decided to try a deque for practice. I will try making a deque with a linked list, sounds like an interesting exercise. \$\endgroup\$ Dec 17, 2019 at 0:07
2
\$\begingroup\$

For peek_left and peek_right, you can make use of that fact that non-empty collections are truthy to neaten up the condition:

def peek_left(self):
    if self.array:
        return self.array[-1]

    else:
        return None

And at that point, it's short enough that you could just reduce this down using a conditional expression:

def peek_left(self):
    return self.array[-1] if self.array else None

Which should be used is a matter of preference, but here, I think the latter is succinct enough that I'd prefer it.

I'd also consider allowing the user the set their own default value here instead of forcing None. With how you have it now, it isn't possible to differentiate between a failed and successful peek if the deque contains Nones. This would be a pretty simple change to fix:

def peek_left(self, default=None):
    return self.array[-1] if self.array else default

Along the same lines, pop_left can be neatened up a bit too:

def pop_left(self, default=None):
    # If mid is the rightmost element, move it left.
    if self.mid == len(self.array) - 1:
        self.mid = self.mid - 1

    return self.array.pop() if self.array else default

Regarding

I'm aware that the __str__ method isn't particularly efficient as it is O(n)

On top of what @Steven mentioned, I think O(n) would be the best possible runtime complexity anyways. To turn each element into a string to return, you would necessarily have to visit each element at least once.

\$\endgroup\$
2
\$\begingroup\$

Your __str__ is actually O(n^2) because you do repeated string concatenations. In another language you would use a StringBuilder but in Python it's common to collect the results in a list and concatenate them all at the end. Here's how you can do that:

    def __str__(self):
        ret = []
        for idx, val in enumerate(self.array):
            if idx == self.mid:
                ret.append("({})".format(str(val)))
            else:
                ret.append(str(val))

        return "[" + " ".join(ret) + "]"

join will first check how much space is needed, allocate it once and then copy all the strings over, instead of reallocating blocks (potentially) every time there's a new concatenation


The pythonic way to check if a collection is non-empty is with if not self.array:. It's also common to not use parentheses around the if condition.


Also, I would recommend raising an exception instead of returning None in cases where the deque is empty. Otherwise, your caller may not know that they have to deal with None, and the caller also can't distinguish between popping off a None value and the deque being empty.
To do this, I would simply remove the length check and allow the IndexError to be thrown by self.array. If you'd like, you could also catch that Exception and throw your own Exception instead, like QueueEmptyError (for example).


I'll add that if you need a deque for your use cases, you should probably use collections.deque because it's well-optimized for common deque uses. It's implemented with a linkedlist of blocks to keep cache locality good.


Finally, could you describe how your data structure works? It looks like both push methods and pop_right are O(n) because they operate on the middle of the list. Were you trying to implement a circular queue? In that case you should preallocate a list of a certain size (self.array = [None for _ in range(10)]) and then keep track of the index of both the first and last element. Then, all methods are O(1) unless you need to resize. This will make it amortized constant time, as long as you resize infrequently enough (i.e. double the array when you reach capacity).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You're right about strings: I sometimes forget that they are simply arrays :) You are correct about your comment with checking for errors: I will just allow the standard list exceptions to be shown. \$\endgroup\$ Dec 17, 2019 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.