dsa.stack

  1""" Module containing stack classes. """
  2
  3class Stack:
  4    """ 
  5    A static stack implementation.
  6    """
  7    def __init__(self, capacity: int=10):
  8        """ 
  9        Initialize the stack with a given capacity.
 10
 11        Args:
 12            capacity (int): The initial size of the stack (defaults to 10).
 13        """
 14        self._array = [None] * capacity
 15        #: number of elements in stack
 16        self.count = 0
 17    
 18    def push(self, element):
 19        """
 20        Push an element into the stack. Raise Exception when trying to push more elements than the capacity.
 21
 22        Args:
 23            element: The element to push.
 24        Raises:
 25            Exception: When the capacity is reached.
 26        """
 27        if len(self) >= len(self._array):
 28            raise Exception("Capacity Reached")
 29        self.count += 1
 30        self._array[self.top()] = element
 31        
 32    def pop(self):
 33        """
 34        Pop an element from the stack. Raise Exception when there are no elements to pop.
 35
 36        Returns:
 37            The top element in the stack.
 38        
 39        Raises:
 40            Exception: When the stack is empty.
 41        """
 42        if self.is_empty():
 43            raise Exception("Empty Stack")
 44        element = self._array[self.top()]
 45        self.count -= 1
 46        return element
 47    
 48    def peek(self):
 49        """
 50        Return the element from the top of the stack. Raise Exception if stack is empty.
 51
 52        Returns:
 53            The top element in the stack.
 54        
 55        Raises:
 56            Exception: When the stack is empty. 
 57        """
 58        if self.is_empty():
 59            raise Exception("Empty Stack")
 60        return self._array[self.top()]
 61    
 62    def __len__(self):
 63        """
 64        Return the number of elements in the stack.
 65        """
 66        return self.count
 67    
 68    def is_empty(self):
 69        """
 70        Return a Boolean on whether the stack is empty or not.
 71        """
 72        return self.count == 0
 73    
 74    def top(self):
 75        """
 76        Return the top index of the stack. 
 77        """
 78        return self.count - 1
 79
 80    def capacity(self):
 81        """
 82        Return the capacity of the stack. 
 83        """
 84        return len(self._array)
 85
 86    @classmethod
 87    def from_list(cls, alist: list):
 88        """
 89        Set the contents of a stack from a list. Raise Exception when trying to push more elements than the capacity.
 90
 91        Args:
 92            alist: The list with contents to set as an array.
 93        """
 94        st = cls()
 95        for e in alist:
 96            st.push(e)
 97        return st
 98
 99    def to_list(self):
100        """
101        Return the contents of the stack as an array.
102        """
103        return self._array[:self.count]
104
105    def __repr__(self):
106        """
107        Return a string representation of the stack.
108        """
109        return f"{self._array[0:self.count]} Top: {self.top()} Capacity: {self.capacity()}"
110    
111    
112class DynamicStack(Stack):
113    """ 
114    A dynamic stack implementation.
115    """
116    def grow(self):
117        """ 
118        Helper method to double the capacity of the current array. 
119        """
120        new_array = [ None ] * len(self._array) * 2
121        
122        # copy elements
123        for i, e in enumerate(self._array):
124            new_array[i] = e
125
126        self._array = new_array
127
128    def shrink(self):
129        """ 
130        Helper method to halve the capacity of the current array.
131        """
132        if self.capacity() < 10:
133            return
134
135        new_capacity = self.capacity() // 2
136        new_array = [ None ] * new_capacity
137        
138        # copy elements
139        for i in range(new_capacity):
140            new_array[i] = self._array[i]
141
142        self._array = new_array
143
144
145    def check_capacity(self):
146        """
147        Check the capacity of the stack. 
148        If count >= capacity, grow the array
149        If count <= 1/4 of capacity, shrink the array
150        """
151        if self.count >= self.capacity():
152            self.grow()
153        elif self.count * 4 <= self.capacity():
154            self.shrink()
155        
156    def push(self, element):
157        """
158        Push an element into the stack. Automatically grows array if capacity needs to increase.
159
160        Args:
161            element: The element to push.
162
163        Returns:
164            None
165        """
166        self.check_capacity()
167        super().push(element)
168        
169    def pop(self):
170        """
171        Return an element from the stack. Automatically shrinks array if capacity is 4x the count.
172
173        Returns:
174            The top element in the stack.
175
176        Raises:
177            Exception: When the stack is empty.
178        """
179        self.check_capacity()
180        return super().pop()