Data Structures with Generic Types in Python/

...

/

DualArrayDeque: Building a Deque from Two Stacks

DualArrayDeque: Building a Deque from Two Stacks

Learn how to implement a DualArrayDeque data structure.

We'll cover the following...

In this lesson, we present a data structure, the DualArrayDeque, that achieves the same performance bounds as an ArrayDeque by using two ArrayStacks. Although the asymptotic performance of the DualArrayDeque is no better than that of the ArrayDeque, it is still worth studying, since it offers a good example of how to make a sophisticated data structure by combining two simpler data structures.

Two ends of a DualArrayDeque

A DualArrayDeque represents a list using two ArrayStacks. Recall that an ArrayStack is fast when the operations on it modify elements near the end. A DualArrayDeque places two ArrayStacks, called front and back, back-to-back so that operations are fast at either end.

Press + to interact
class DualArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.front = ArrayStack()
        self.back = ArrayStack()

A DualArrayDeque does not explicitly store the number, nn, of elements it contains. It doesn’t need to, since it contains n = front.size() + back.size() elements. Nevertheless, when analyzing the DualArrayDeque we will still use nn to denote the number of elements it contains.

Press + to interact
class DualArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
    def size(self):
        return self.front.size() + self.back.size()

The DualArrayDeque operations

The front ArrayStack stores the list elements that whose indexes are 0,...,front.size()−1,0, ... , \text{front.size}() − 1, but stores them in reverse order. The back ArrayStack contains list elements with indexes in front.size(),...,size()−1\text{front.size}(), . . . , \text{size}() − 1 in the normal order. In this way, get(i) and set(i, x) translate into appropriate calls to get(i) or set(i, x) on either front or back, which take O(1)O(1) time per operation.

Press + to interact
class DualArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def get(self, i):
        if i < self.front.size():
            return self.front.get(self.front.size()-i-1)
        else:
            return self.back.get(i-self.front.size())
    
    def set(self, i, x):
        if i < self.front.size():
            return self.front.set(self.front.size()-i-1, x)
        else:
            return self.back.set(i-self.front.size(), x)

Note that if an index i < front.size(), then it corresponds to the element of front at position front.size() − i − 1, since the elements of front are stored in reverse order.

Visual demonstration

Adding and removing elements from a DualArrayDeque is illustrated below. Arrows denote elements being copied. Operations that result in a rebalancing by _balance() are marked with an asterisk.

The add(i, x) operation manipulates either front or back, as appropriate:

Press + to interact
class DualArrayDeque(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def add(self, i, x):
        if i < self.front.size():
            self.front.add(self.front.size()-i, x)
        else:
            self.back.add(i-self.front.size(), x)
        self._balance()

The add(i, x) method performs rebalancing of the two ArrayStacks front and back, by calling the _balance() method. The implementation of _balance() is described below, but for now it is sufficient to know that balance() ensures that, unless size() < 2, front.size() and back.size() do not differ by more than a factor of 33. In particular, 3⋅front.size()≥back.size()3 \cdot \text{front.size}() \ge \text{back.size}() and 3⋅back.size()≥front.size()3 \cdot \text{back.size}() \ge \text{front.size}().

Next we analyze the cost of add(i, x), ignoring the cost of calls to balance(). If i < front.size(), then add(i, x) gets ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy