algorithms/algorithms/stack/ordered_stack.py at main · mitchricker/algorithms · GitHub

History

93 lines (72 loc) · 2.27 KB

Raw

"""

Ordered Stack

A stack that maintains elements in sorted order, with the highest value

at the top and the lowest at the bottom. Push operations preserve the

ordering invariant.

Reference: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Complexity:

Time: O(n) for push, O(1) for pop/peek

Space: O(n)

"""

from __future__ import annotations

class OrderedStack:

"""A stack that keeps elements in ascending order (bottom to top).

Examples:

>>> s = OrderedStack()

>>> s.push(3)

>>> s.push(1)

>>> s.push(2)

>>> s.pop()

"""

def __init__(self) -> None:

"""Initialize an empty ordered stack."""

self.items: list[int] = []

def is_empty(self) -> bool:

"""Check if the stack is empty.

Returns:

True if the stack has no elements.

"""

return self.items == []

def _push_direct(self, item: int) -> None:

"""Append an item without enforcing order.

Args:

item: The value to append.

"""

self.items.append(item)

def push(self, item: int) -> None:

"""Push an item while maintaining sorted order.

Args:

item: The value to push.

"""

temp_stack = OrderedStack()

if self.is_empty() or item > self.peek():

self._push_direct(item)

else:

while item < self.peek() and not self.is_empty():

temp_stack._push_direct(self.pop())

self._push_direct(item)

while not temp_stack.is_empty():

self._push_direct(temp_stack.pop())

def pop(self) -> int:

"""Remove and return the top element.

Returns:

The top (largest) element.

Raises:

IndexError: If the stack is empty.

"""

if self.is_empty():

raise IndexError("Stack is empty")

return self.items.pop()

def peek(self) -> int:

"""Return the top element without removing it.

Returns:

The top (largest) element.

"""

return self.items[len(self.items) - 1]

def size(self) -> int:

"""Return the number of elements in the stack.

Returns:

The stack size.

"""

return len(self.items)

algorithms/algorithms/stack/ordered_stack.py at main · mitchricker/algorithms · GitHub

Expand file tree

Breadcrumbs

ordered_stack.py

Latest commit

History

Breadcrumbs

ordered_stack.py

File metadata and controls