3
\$\begingroup\$

I encountered this question as I am preparing for my code interview.

Using Python, create an implementation of Deque (double-ended queue) with linked list nodes that has attributes of both front and back enqueue and dequeue.

from linkedlist import LinkedList

class DeQueue(object):
    def __init__(self, iterable=None):
        """Initialize this queue and enqueue the given items, if any."""
        # Initialize a new linked list to store the items
        self.list = LinkedList()
        if iterable is not None:
            for item in iterable:
                self.enqueue_back(item)

    def __repr__(self):
        """Return a string representation of this queue."""
        return 'Queue({} items, front={})'.format(self.length(), self.front())

    def is_empty(self):
        """Return True if this queue is empty, or False otherwise."""
        return self.list.is_empty()

    def length(self):
        """Return the number of items in this queue."""
        return self.list.size

    def enqueue_back(self, item):
        """Insert the given item at the back of this queue.
        Running time: O(1) - just does prepend, which is O(1)"""
        self.list.prepend(item)

    def enqueue_front(self, item):
        """Insert the given item at the front of this queue.
        Running time: O(1) - just does append, which is O(1)"""
        self.list.append(item)

    def front(self):
        """Return the item at the front of this queue without removing it,
        or None if this queue is empty."""
        if self.is_empty():
            return None
        return self.list.tail.data

    def back(self):
        """Return the item at the back of this queue without removing it,
        or None if this queue is empty."""
        if self.is_empty():
            return None
        return self.list.head.data

    def dequeue_front(self):
        """Remove and return the item at the front of this queue,
        or raise ValueError if this queue is empty.
        Running time: O(1) - since tail, it happens easily
        If this wasn't a double-linked list, it would take O(n)"""
        if self.is_empty():
            raise ValueError
        output = self.list.tail.data
        self.list.delete(self.list.tail.data)
        return output
    def dequeue_back(self):
        """Remove and return the item at the back of this queue,
        or raise ValueError if this queue is empty.
        Running time: O(1) - since head, it happens easily."""
        if self.is_empty():
            raise ValueError
        output = self.list.head.data
        self.list.delete(self.list.head.data)
        return output

# Implement LinkedQueue and ArrayQueue above, then change the assignment below
# to use each of your Queue implementations to verify they each pass all tests
Queue = DeQueue
#Queue = ArrayQueue
# Implement LinkedQueue and ArrayQueue above, then change the assignment below
# to use each of your Queue implementations to verify they each pass all tests
q = DeQueue()
print(q.list)
q.enqueue_back('E')
print(q.enqueue_back('E'))
print(q.list)
print(q.enqueue_front('A'))
print(q.list)
print(q.enqueue_front('M'))
print(q.list)
print(q.enqueue_back('T'))
print(q.list)
print(q.front())
print(q.back())
print(q.list)
q.dequeue_back()
print(q.list)
q.dequeue_front()
print(q.list)
print(q.dequeue_front())
print(q.list)
q.dequeue_front()
print(q.list)
print(q.front())

I wrote the following tests to make sure that my code works a pretty comprehensive following unit test cases, and it passed against all test cases, so the code seems to be working fine.

from queue import Queue
import unittest


class DblQueueTest(unittest.TestCase):

    def test_init(self):
        q = DeQueue()
        assert q.front() is None
        assert q.length() == 0
        assert q.is_empty() is True

    def test_init_with_list(self):
        q = DeQueue(['A', 'B', 'C'])
        assert q.front() == 'A'
        assert q.length() == 3
        assert q.is_empty() is False

    def test_length(self):
        q = DeQueue()
        assert q.length() == 0
        q.enqueue_back('A')
        assert q.length() == 1
        q.enqueue_front('B')
        assert q.length() == 2
        q.dequeue_front()
        assert q.length() == 1
        q.dequeue_back()
        assert q.length() == 0

    def test_enqueue(self):
        q = DeQueue()
        q.enqueue_back('B')
        assert q.front() == 'B'
        assert q.length() == 1
        q.enqueue_back('C')
        assert q.front() == 'B'
        assert q.length() == 2
        q.enqueue_front('A')
        assert q.front() == 'A'
        assert q.length() == 3
        assert q.is_empty() is False

    def test_front_back(self):
        q = DeQueue()
        assert q.front() is None
        q.enqueue_back('A')
        assert q.front() == 'A'
        q.enqueue_back('B')
        assert q.front() == 'A'
        q.dequeue_front()
        assert q.front() == 'B'
        q.dequeue_back()
        q.enqueue_front('C')
        assert q.front() == 'C'
        q.enqueue_front('B')
        assert q.front() == 'B'
        q.enqueue_front('A')
        assert q.front() == 'A'
        assert q.back() == 'C'
        q.dequeue_front()
        assert q.front() == 'B'
        assert q.back() == 'C'
        q.dequeue_front()
        q.dequeue_front()
        assert q.front() is None
        assert q.back() is None



if __name__ == '__main__':
    unittest.main()
\$\endgroup\$
  • \$\begingroup\$ I appreciate any comment from anyone for this question. \$\endgroup\$ – NinjaG Nov 6 '17 at 17:41
1
\$\begingroup\$

I have some issues with your coding style, and possibly with the guide you are using. There's a lot of Java in your code.

Consider this:

from linkedlist import LinkedList

class DeQueue(object):
    def __init__(self, iterable=None):
        """Initialize this queue and enqueue the given items, if any."""
        # Initialize a new linked list to store the items
        self.list = LinkedList()
        if iterable is not None:
            for item in iterable:
                self.enqueue_back(item)

How many times did you reference LinkedList in your entire code?

I counted one - the line shown above. So why use an aliasing import? Why not just set self.list = linkedlist.LinkedList()?

This is a personal-coding-style issue: in a program that might have 10 or 15 import statements, are you going to use aliasing or spell out the name of the providing module? As a reader, I want to see the name of the module for names that don't get frequently used. (Obviously, if you have to type LinkedList 50 times, by all means alias it! But if it's only once or twice, please give me the module name in-line.)

Next, consider your doc comment: Initialize this queue and enqueue the given items, if any.

This is misleading, because you only allow one optional parameter - an iterable. Please make this explicit in your comment. Consider this documentation for Python's built-in set and frozenset:

class set([iterable]) 
class frozenset([iterable])

Return a new set or frozenset object whose elements are taken from iterable. The elements of a set must be hashable. To represent sets of sets, the inner sets must be frozenset objects. If iterable is not specified, a new empty set is returned.

Notice that it's clear the iterable will be used to take elements for membership in the set?

Next, why are you using the method names you chose? The class you are defining is a collection. Python has some standard names for collection operations. Use them! In fact, Python also provides abstract base classes for collections: use those, too!

If I have a list and I want to make the list longer by enqueuing an item at the end of the list, what do I use?

my_list = [1, 2, 3]
my_list.enqueue_back(4)    # NO!

I use .append:

my_list.append(4)

Or I use .extend:

my_list.extend([5, 6, 7])

If you want to provide a collection class that has a similar behavior to existing collection classes, then use the same method names for the same operations!

Likewise, provide similar functionality! I don't see a definition of __len__ but you do have .length? What's that? Where's __bool__? Where's __contains__?

Take a look at the Python docs for Common Sequence Operations, for both mutable and immutable sequences. See how many operations you can implement, using the dundermethods, to make your class a drop-in substitute for a list, or an iterable, or whatever.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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