Data Structures with Generic Types in Python/

...

/

Array Implementation of Stack

Array Implementation of Stack

Learn how to implement ArrayStack using an array.

We'll cover the following...

ArrayStack overview

The List and Queue interfaces can be implemented so that the underlying data is stored in an array, called the backing array. The following table summarizes the running times of operations for these data structures:

Press + to interact
Running times of operations for array-based stack
Running times of operations for array-based stack

Advantages and limitations

Data structures that work by storing data in a single array have many advantages and limitations in common:

  • Arrays offer constant time access to any value in the array. This is what allows get(i) and set(i, x) to run in constant time.

  • Arrays are not very dynamic. Adding or removing an element near the middle of a list means that a large number of elements in the array need to be shifted to make room for the newly added element or to fill in the gap created by the deleted element. This is why the operations add(i, x) and remove(i) have running times that depend on nn and ii.

  • Arrays cannot expand or shrink. When the number of elements in the data structure exceeds the size of the backing array, a new array needs to be allocated and the data from the old array needs to be copied into the new array. This is an expensive operation.

The third point is important. The running times cited in the table above do not include the cost associated with growing and shrinking the backing array. We will see that, if carefully managed, the cost of growing and shrinking the backing array does not add much to the cost of an average operation. More precisely, if we start with an empty data structure, and perform any sequence of mm add(i, x) or remove(i) operations, then the total cost of growing and shrinking the backing array, over the entire sequence of m operations is O(m)O(m). Although some individual operations are more expensive, the amortized cost, when amortized over all mm operations, is only O(1)O(1) per operation.

ArrayStack: fast stack operations using an array

An ArrayStack implements the list interface using an array aa, called the backing array. The list element with index ii is stored in a[i]. At most times, aa is larger than strictly necessary, so an integer nn is used to keep track of the number of elements actually stored in aa. In this way, the list elements are stored in a[0],...,a[n−1]a[0],. . . ,a[n − 1] and, at all times, a.length≥n\text{a.length} \ge n.

Press + to interact
class ArrayStack(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.a = new_array(1)
        self.n = 0

The basics

Accessing and modifying the elements of an ArrayStack using get(i) and set(i, x) is trivial. After performing any necessary bounds-checking, we simply return or set, respectively, a[i].

Press + to interact
class ArrayStack(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.a = new_array(1)
        self.n = 0
    def get(self, i):
        if i < 0 or i >= self.n: raise IndexError()
        return self.a[i]
    def set(self, i, x):
        if i < 0 or i >= self.n: raise IndexError()
        y = self.a[i]
        self.a[i] = x
        return y

The operations of adding and removing elements from an ArrayStack are illustrated below. A sequence of add(i, x) and remove(i) operations on an ArrayStack. Arrows denote elements being copied. Operations that result in a call to resize() are marked with an asterisk.

To implement the add(i, x) operation, we first check if aa is already full. If so, we call the method resize() to increase the size of aa. How resize() is implemented will be discussed later. For now, it is sufficient to know that, after a call to resize(), we can be sure that a.length > n. With this out of the way, we now shift the elements a[i],...,a[n−1]a[i], . . . , a[n − 1] right by one position to make room for xx, set a[i] equal to xx, and increment nn.

Press + to interact
class ArrayStack(BaseList):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable) 
    def add(self, i, x): 
        if i < 0 or i > self.n: raise IndexError()
        if self.n == len(self.a): self._resize()
        self.a[i+1:self.n+1] = self.a[i:self.n]
        self.a[i] = x
        self.n += 1

If we ignore the cost of the potential call to resize(), then the cost of the add(i, x) operation is proportional to the number of elements we have to shift to make room for ...

Create a free account to access the full course.

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