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    def __eq__(self, other):
112        """
113        Compare two stacks (static/dynamic) for value-based equality.
114
115        Returns:
116            True if both are Stack or DynamicStack instances and their contents are equal.
117            For non-stack types, returns NotImplemented.
118        """
119        if isinstance(other, (Stack, DynamicStack)):
120            return self.to_list() == other.to_list()
121        return NotImplemented
122    
123    
124class DynamicStack(Stack):
125    """ 
126    A dynamic stack implementation.
127    """
128    def grow(self):
129        """ 
130        Helper method to double the capacity of the current array. 
131        """
132        new_array = [ None ] * len(self._array) * 2
133        
134        # copy elements
135        for i, e in enumerate(self._array):
136            new_array[i] = e
137
138        self._array = new_array
139
140    def shrink(self):
141        """ 
142        Helper method to halve the capacity of the current array.
143        """
144        if self.capacity() < 10:
145            return
146
147        new_capacity = self.capacity() // 2
148        new_array = [ None ] * new_capacity
149        
150        # copy elements
151        for i in range(new_capacity):
152            new_array[i] = self._array[i]
153
154        self._array = new_array
155
156
157    def check_capacity(self):
158        """
159        Check the capacity of the stack. 
160        If count >= capacity, grow the array
161        If count <= 1/4 of capacity, shrink the array
162        """
163        if self.count >= self.capacity():
164            self.grow()
165        elif self.count * 4 <= self.capacity():
166            self.shrink()
167        
168    def push(self, element):
169        """
170        Push an element into the stack. Automatically grows array if capacity needs to increase.
171
172        Args:
173            element: The element to push.
174
175        Returns:
176            None
177        """
178        self.check_capacity()
179        super().push(element)
180        
181    def pop(self):
182        """
183        Return an element from the stack. Automatically shrinks array if capacity is 4x the count.
184
185        Returns:
186            The top element in the stack.
187
188        Raises:
189            Exception: When the stack is empty.
190        """
191        self.check_capacity()
192        return super().pop()