Implementación de una Pila con Nodos en Python

Reto 2

class Array:
    def __init__(self, capacity, fill_value=None):
        self.items = list()
        for _ in range(capacity):
            self.items.append(fill_value)

    def __len__(self):
        return len(self.items)

    def __str__(self):
        return str(self.items)

    def __iter__(self):
        return iter(self.items)

    def __getitem__(self, index):
        return self.items[index]

    def __setitem__(self, index, new_item):
        self.items[index] = new_item


class StackArray(Array):
    def __init__(self, capacity, fill_value=None):
        super().__init__(capacity, fill_value)
        self.capacity = capacity
        self.top = None
        self.size = 0

    def __str__(self):
        result = ''
        if self.size <= 0:
            return 'Stack empty'
        for i in self.items:
            if i != None:
                result += f'{i} '
        return result

    def push(self, data):
        if self.size == self.capacity:
            print('Stack full')
            return -1

        for i, value in enumerate(self.items):
            if value == None:
                self.items[i] = data
                self.top = data
                self.size += 1
                break

    def pop(self):
        for i in range(self.capacity-1, -1, -1):
            if self.items[i] != None:
                self.items[i] = None
                self.size -= 1
                if i > 0:
                    self.top = self.items[i-1]
                else:
                    self.top = None
                break

    def peek(self):
        if self.top:
            return self.top
        else:
            return "The stack is empty"
    
    def clear(self):
        self.__init__(self.capacity)
    
    def search(self, target_item):
        if self.size <= 0:
            print("The stack is empty")
        else:
            if target_item in self.items:
                print(f'Target item {target_item} has been found')
                return self.items.index(target_item)
            else:
                print(f'Target item {target_item} is not in stack')
                return -1

    def iter(self):
        for element in self.items:
            if element != None:
                yield element

from node import Node

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0


    def push(self, data):
        node = Node(data, self.top)

        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1


    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None

            return data
        else:
            return ("The stack is empty")


    def peek(self):
        return self.top.data if self.top else ("The stack is empty")


    def clear(self):
        while self.top:
            self.pop()


    def search_element(self, data):
        if self.top:
            current = self.top
            while current:
                if current.data == data:
                    return (f'Elemet {data} founded')
                current = current.next
            return (f'Elemet {data} not founded')

Reto 1:
Clase:

import gc
from node import Node

class Stack:

    def __init__(self) -> None:
        self.top = None
        self.size = 0
        self.__current__ = None
    

    def __iter__(self):
        self.__current__ = self.top
        return self

    def __next__(self):
        if not self.__current__:
            raise StopIteration
        else:
            next_node = self.__current__
            self.__current__ = next_node.next
        return next_node

    def push(self, data):
        node = Node(data)
        if self.top:
            node.next = self.top
        self.top = node
        self.size += 1

    def pop(self):
        return_data = 'Empty stack'
        if self.top:
            return_data = self.top.data
            self.top = self.top.next
            self.size -= 1
        return return_data
    
    def add(self, stack2):
        if len(stack2) > 0:
            for node2 in stack2:
                self.push(node2.data)
        else:
            print(f'Parameter stack is empty')


    def __contains__(self, data):
        if self.size > 0:
            return_node = self.top
            while return_node and return_node.data != data:
                return_node = return_node.next
        return return_node

    def clear(self):
        self.size = 0
        self.top = None
        gc.collect()

    def peek(self):
        return_data = 'Empty stack'
        if self.top:
            return_data = self.top.data
        return return_data
    
    def __len__(self):
        return self.size
    
    def __str__(self):
        node = self.top
        position = 1
        return_str = '(\r\n'
        while(node):
            return_str += f'\tPosition {position} - dato {node.data}'
            position += 1
            node = node.next
        return_str += '\r\n)'
        return return_str

Aplicación:

from mi_stack import Stack

def run():
    stack = Stack()
    stack.push('A')
    stack.push('B')
    stack.push('C')
    stack.push('D')

    show_stack(stack)
    
    print(stack.pop())
    print(stack.pop())

    show_stack(stack)

    stack2 = Stack()
    stack2.push('X')
    stack2.push('Y')
    stack2.push('Z')

    stack.add(stack2)

    show_stack(stack)

    stack.clear()
    show_stack(stack)


def show_stack(stack):
    print('=======================')
    position = 1
    for node in stack:
        print(f'Position {position} dato {node.data}')
        position += 1


if __name__ == '__main__':
    run()

Reto

Código

Stack con nodos

from typing import Optional, Union
from typing import Iterable

from node import Node


class Stack:
    """A simple stack implementation."""

    _size: int
    _top: Optional[Node]

    def __init__(self, *items):
        """Initializes the stack."""

        self._top = None
        self._size = 0

        if len(items) > 0 and isinstance(items[0], Iterable):
            items = items[0]

        for item in items:
            self.push(item)

    def is_empty(self):
        """Checks if the stack is empty.

        Returns:
            bool: True if the stack is empty, False otherwise.
        """

        return self._size <= 0

    def clear(self):
        """Clears the stack."""

        self._top = None
        self._size = 0

    def copy(self):
        """Returns a copy of the stack.

        Caution: This method returns a shallow copy.

        Returns:
            Stack: A copy of the stack.
        """

        new_stack = Stack()

        new_stack._top = self._top

        return new_stack

    def depthcopy(self):
        """Returns a deep copy of the stack.

        Returns:
            Stack: A deep copy of the stack.
        """

        new_stack = Stack()

        new_stack._top = self._top.depthcopy()

        new_stack._size = self._size

        return new_stack

    def extend(self, other: 'Stack'):
        """Extends the current stack with the items of the other stack.

        Time complexity: O(n) where n is the length of the other stack.

        Args:
            other: The other stack to extend the current stack with.
        """

        if other._top is None:
            return None

        bottom_node = other._top

        while bottom_node.next is not None:
            bottom_node = bottom_node.next

        bottom_node.next = self._top

        self._top = other._top

        self._size += other._size

        return None

    def peek(self, raw: bool = False) -> Union[None, Node, object]:
        """Returns the top item of the stack.

        Raises IndexError if the stack is empty.

        Args:
            raw: If True returns the Node, otherwise it will return the node value.

        Returns:
            object: The top item of the stack.
        """

        if not self._top:
            raise IndexError('The stack is empty.')

        if raw:
            return self._top

        return self._top.value

    def push(self, value: object):
        """Pushes an item onto the stack.

        Time complexity: O(1)

        Args:
            item: The item to be pushed onto the stack.
        """

        self._top = Node(value, self._top)
        self._size += 1

    def pop(self, raw: bool = False):
        """Pops an item off the stack.

        Raises IndexError if the stack is empty.

        Time complexity: O(1)

        Args:
            raw: If True returns the Node, otherwise it will return the node value.

        Returns:
            object: The item that was popped off the stack.
        """

        if self._top is None:
            raise IndexError('The stack is empty.')

        temp = self._top

        self._top = temp.next

        self._size -= 1

        if raw:
            return temp

        return temp.value

    def __len__(self):
        """Returns the length of the stack.

        Time complexity: O(1)

        Returns:
            int: The length of the stack.
        """

        return self._size

    def __str__(self) -> str:
        """Returns a string representation of the stack.

        Time complexity: O(n)
        Space complexity: O(n)

        Returns:
            str: A string representation of the stack.
        """

        items = list(self)

        return str(items)

    def __contains__(self, item: object) -> bool:
        """Checks if the stack contains an item.

        Args:
            item: The item to check if the stack contains.

        Returns:
            bool: True if the stack contains the item, False otherwise.
        """

        pointer = self._top
        while pointer is not None:
            if pointer.value == item:
                return True

            pointer = pointer.next

        return False

    def itervalues(self) -> Iterable:
        """Returns an iterator over the values of the stack.

        Returns:
            iterator: An iterator over the values of the stack.
        """

        pointer = self._top

        while pointer is not None:
            yield pointer
            pointer = pointer.next

    def __iter__(self) -> Iterable:
        """Returns an iterator over the stack.

        Returns:
            iterator: An iterator over the stack.
        """

        return self.itervalues()

    def __add__(self, other):
        """Returns a new stack containing the items of both stacks.

        Args:
            other: The other stack to add to the current stack.

        Returns:
            Stack: A new stack containing the items of both stacks.
        """

        new_stack = self.depthcopy()
        new_stack.extend(other.depthcopy())

        return new_stack

Stack con listas

from typing import Optional, Union
from typing import Iterable


class Stack:
    """A simple stack implementation with list."""

    _items: list

    def __init__(self, *items):
        self._items = list(*items)

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def clear(self) -> None:
        self._items.clear()

    def copy(self) -> 'Stack':
        stack = Stack()

        for item in self._items:
            stack.push(item)

        return stack

    def extend(self, other: Iterable) -> None:

        for item in reversed(other):
            self.push(item)

    def peek(self) -> Optional[object]:
        if self.is_empty():
            raise ValueError('Stack is empty.')

        return self._items[-1]

    def pop(self) -> Optional[object]:
        return self._items.pop()

    def push(self, item: object) -> None:
        self._items.append(item)

    def itervalues(self) -> Iterable:
        return reversed(self._items)

    def __len__(self) -> int:
        return len(self._items)

    def __str__(self) -> str:
        return str(self._items)

    def __contains__(self, item: object) -> bool:
        return item in self._items

    def __iter__(self) -> Iterable:
        return self.itervalues()

    def __repr__(self) -> str:
        return f'Stack({self._items})'

    def __reversed__(self) -> Iterable:
        return self._items

    def __add__(self, other: Union['Stack', Iterable]) -> 'Stack':
        stack = self.copy()

        if isinstance(other, Stack):
            stack.extend(other)
        else:
            stack.extend(other)

        return stack

Pruebas unitarias

Stack con nodos

# Unitest
import unittest

# Utils
from stack_with_node import Stack


class StackWithNodeTestCase(unittest.TestCase):
    """Stack test cases."""


    def test_empty_instantiation(self):
        """Test instantiation of an empty stack."""
        stack = Stack()
        self.assertEqual(len(stack), 0)

    def test_instantiation_with_items(self):
        """Test instantiation of a stack with items."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(len(stack), 3)

    def test_is_empty(self):
        """Test is_empty method."""
        stack = Stack()
        self.assertTrue(stack.is_empty())

    def test_is_not_empty(self):
        """Test is_empty method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertFalse(stack.is_empty())

    def test_push(self):
        """Test push method."""
        stack = Stack()
        stack.push('a')
        self.assertEqual(len(stack), 1)

    def test_peek(self):
        """Test peek method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(stack.peek(), 'c')

    def test_pop(self):
        """Test pop method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(stack.pop(), 'c')
        self.assertEqual(len(stack), 2)

        for a, b in zip(stack, ['b', 'a']):
            self.assertEqual(a, b)

    def test_pop_empty(self):
        """Test pop method."""
        stack = Stack()
        self.assertRaises(IndexError, stack.pop)

    def test_copy(self):
        """Test copy method."""
        stack = Stack(['a', 'b', 'c'])
        stack_copy = stack.copy()

        self.assertIsNot(stack_copy, stack)

    def test_depthcopy(self):
        """test depthcopy method."""

        stack_1 = Stack([1, 2, 3])
        stack_2 = stack_1.depthcopy()

        self.assertEqual(len(stack_2), len(stack_1))

        for a, b in zip(stack_1, stack_2):
            self.assertIsNot(a, b)

    def test_iter(self):
        """Test iter method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(list(stack), ['c', 'b', 'a'])

    def test_extend(self):
        """Test extends method."""
        stack_1 = Stack([1, 2, 3])
        stack_2 = Stack([4, 5, 6])

        stack_1.extend(stack_2)
        self.assertEqual(len(stack_1), 6)

        for a, b in zip(stack_1, [6, 5, 4, 3, 2, 1]):
            self.assertEqual(a, b)

    def test_add_operator(self):
        """Test add operator."""
        stack_1 = Stack([1, 2, 3])
        stack_2 = Stack([4, 5, 6])

        stack_3 = stack_1 + stack_2

        self.assertEqual(len(stack_3), 6)

        for a, b in zip(stack_3, [6, 5, 4, 3, 2, 1]):
            self.assertEqual(a, b)

Stack con listas

# Unitest
import unittest

# Utils
from stack_with_array import Stack


class StackWithNodeTestCase(unittest.TestCase):
    """Stack test cases."""


    def test_empty_instantiation(self):
        """Test instantiation of an empty stack."""
        stack = Stack()
        self.assertEqual(len(stack), 0)

    def test_instantiation_with_items(self):
        """Test instantiation of a stack with items."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(len(stack), 3)

    def test_is_empty(self):
        """Test is_empty method."""
        stack = Stack()
        self.assertTrue(stack.is_empty())

    def test_is_not_empty(self):
        """Test is_empty method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertFalse(stack.is_empty())

    def test_push(self):
        """Test push method."""
        stack = Stack()
        stack.push('a')
        self.assertEqual(len(stack), 1)

    def test_push_multiple(self):
        """Test push method."""
        stack = Stack()
        stack.push('a')
        stack.push('b')
        stack.push('c')
        self.assertEqual(len(stack), 3)

        for a, b in zip(stack, ['c', 'b', 'a']):
            self.assertEqual(a, b)

    def test_peek(self):
        """Test peek method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(stack.peek(), 'c')

    def test_pop(self):
        """Test pop method."""
        stack = Stack(['a', 'b', 'c'])

        self.assertEqual(stack.pop(), 'c')
        self.assertEqual(len(stack), 2)

        for a, b in zip(stack, ['b', 'a']):
            self.assertEqual(a, b)

    def test_pop_empty(self):
        """Test pop method."""
        stack = Stack()
        self.assertRaises(IndexError, stack.pop)

    def test_copy(self):
        """Test copy method."""
        stack = Stack(['a', 'b', 'c'])
        stack_copy = stack.copy()

        self.assertIsNot(stack_copy, stack)

    def test_iter(self):
        """Test iter method."""
        stack = Stack(['a', 'b', 'c'])
        self.assertEqual(list(stack), ['c', 'b', 'a'])

    def test_extend(self):
        """Test extends method."""
        stack_1 = Stack([1, 2, 3])
        stack_2 = Stack([4, 5, 6])

        stack_1.extend(stack_2)
        self.assertEqual(len(stack_1), 6)

        for a, b in zip(stack_1, [6, 5, 4, 3, 2, 1]):
            self.assertEqual(a, b)

    def test_add_operator(self):
        """Test add operator."""
        stack_1 = Stack([1, 2, 3])
        stack_2 = Stack([4, 5, 6])

        stack_3 = stack_1 + stack_2

        self.assertEqual(len(stack_3), 6)

        for a, b in zip(stack_3, [6, 5, 4, 3, 2, 1]):
            self.assertEqual(a, b)

Reto 2:

Reto 1

from nodes import Node

class Stack():
    def __init__(self):
        self.top = None #Top or Head
        self.size = 0

    def push(self, data): ##other way to push
        """Add an element in top"""
        node = Node(data)
        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top =  node
        self.size += 1
    
    def pop(self, data): 
        """Remove element on top and returns data"""
        if self.top:
            data = self.top.data
            self.size -= 1
            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None
            return data
        else:
            return 'The stack is empty'

    def peek(self):
        """Returns top element in stack"""
        if self.top:
            return self.top.data
        else:
            return 'The stack is empty'
        
    def clear(self):
        """Erase all data from stack"""
        while self.top:
            self.pop()
        return 'The stack now is empty'
    
    def iter(self):
        """Create a stack iterator"""
        while self.top:
            value = self.top.data
            self.top = self.top.next
            yield value

    def search(self, data):
        count = 0
        for node in self.iter():
            count += 1
            if data == node:
                print (f'Data {data} found!')
                break
            elif count == self.size:
                print ('Data not found!')

    def printList(self):
        current = self.top
        print('Data in Single Linked List:', end='\n')
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print('')
    
if __name__ == '__main__':
    stack = Stack()
    for i in range(6,0,-1):
        stack.push(i)
    stack.search(6)
    stack.pop()
    stack.peek()
    stack.printList()

Reto 2, utilice herencia y agregación

from class_array import Array
from stack import Stack

class stackFromArray(Stack):
    def __init__(self, data=Array(1)):
        super().__init__()

        for i in data:
            self.push(i)

if __name__ == '__main__':
    s = stackFromArray(Array(3))
    s.printList()

Paso a pasito:

El reto #1

El reto #2

Para simplificar la clase realizé el Stack usando nuestro anterior Double Linked List como padre.

Les dejo el código en github.

Considero que nos permite concentrarnos un poco más en entender el tipo de dato que en reinventar los métodos usados anteriormente.

Segundo reto completado!

class ArrayStack(Array):
    def __init__(self, capacity, fill_value=None):
        Array.__init__(self, capacity, fill_value)
        self.top_index = self.__len__() - 1
        self.size = 0

    def iter(self):
        for elm in filter(lambda x: x != None, self.items):
            yield elm

    def push(self, data):
        if self.top_index == 0:
            print("The stack is full")
        else:
            if not self.items[self.top_index]:
                self.items[self.top_index] = data
            else:
                self.top_index -= 1
                self.items[self.top_index] = data
            self.size += 1

    
    def pop(self):
        if self.size > 0:
            val = self.items[self.top_index]
            self.items[self.top_index] = None
            self.top_index += 1
            self.size -= 1
            return val
        else:
            return "The stack is empty"

reto de los metodos del stack

Reto 1: Los métodos que le agregó a la clase Stack

Qué onda 👋 me aventé el código con un stack de listas y otro con nodos:

Con nodos

listas

4

El egg, ham, spam, foo, son usados como placeholders(marcadores) para decir “cualquier cosa”, de donde se use, ej: def foo(): se estaría refiriendo a cualquier function.

Solución al reto

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("Stack is empty")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("Stack is empty")

    def size(self):
        return len(self.items)

    def search(self, item):
        index = self.items.index(item) if item in self.items else -1
        return index

    def traverse(self):
        for item in self.items:
            print(item, end=" ")
        print()

    def clear(self):
        self.items = []

# Crear una instancia de la clase Stack
my_stack = Stack()

# Verificar si el stack está vacío
print(my_stack.is_empty())  # Resultado: True

# Agregar elementos al stack
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)

# Obtener el elemento de la parte superior del stack
print(my_stack.peek())  # Resultado: 3

# Eliminar y obtener el elemento de la parte superior del stack
print(my_stack.pop())  # Resultado: 3

# Obtener el tamaño actual del stack
print(my_stack.size())  # Resultado: 2

# Buscar un elemento en el stack
print(my_stack.search(2))  # Resultado: 1

# Recorrer el stack
my_stack.traverse()  # Resultado: 1 2

# Vaciar el stack
my_stack.clear()
print(my_stack.is_empty())  # Resultado: True

acá está el reto 1 y 2 el primero se llama StackNode y el segundo se llama StackArray

from node import Node
from claseArray import Array

class StackNode:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        node = Node(data)

        if self.top is not None:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1

    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None
            
            return data
        
        else:
            return "the stack is empty"
        
    def peek(self):
        if self.top:
            return self.top.data
        else:
            return "the stack is empty"
        
    def clear(self):
        while self.top:
            self.pop()

    def search(self, data):
        """find and return item """
        current = self.top
        position = 1
        while current:
            if current.data == data:
                return f"search found! {current.data}"
            current = current.next
            position += 1
        return "not search found"
    
    def iter(self):
        current = self.top
        while current:
            val = current.data
            current = current.next
            yield val

    def clear2(self):
        self.top = None
        self.size = 0


class StackArray(Array):
    def __init__(self, capacity):
        super().__init__(capacity)
        self.top = -1
        self.capacity = capacity

    def puesh(self, data):
        if self.top < len(self.items):
            self.top += 1
            self.items[self.top] = data
        else:
            return ("stack is full")
        
    def pop(self):
        if self.top >= 0:
            data = self.items[self.top]
            self.top = -1
            return data
        else:
            return ("stac is empty")
        
    def clear(self):
        self.top = -1

    def size(self):
        return self.top + 1
    
    def search(self, data):
        
        for item in range(len(self.items)):
            if self.items[item] == data:
                return item
        return ("not found")

You should definitely watch Spam sketch by Monty Python!
Spam, Spam, Spam!

Reto 1:

from node import Node


class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        node = Node(data)
        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1


    def pop(self):
        if self.top:
            data = self.top.data
            self.size -=1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None

            return data
        
        else:
            return "The stack is empty"

    def peek(self):
        if self.top:
            return self.top.data
        else:
            return "The stack is empty"

    def clear(self):
        self.top = None
        self.size = 0

    def search(self, data):
        probe = self.top
        while probe:
            if probe.data == data:
                return "This element is present in Stack"
            else:
                probe = probe.next
        return "This element not found in Stack"

    def printStack(self):
        probe = self.top
        while probe:
            print(probe.data)
            probe = probe.next

Reto 2:

from node import Node


class StackArray:

    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.top = None

    def push(self, data):
        new_node= Node(data)
        if self.top:
            if self.size+1 <= self.capacity:
                new_node.next = self.top
                self.top = new_node
                self.size += 1
            else:
                print(f"El Stack ya esta lleno, {data} no pudo ingresar.")
        else:
            self.top = new_node
            self.size += 1

    def pop(self):
        data = self.top.data
        if self.top:
            self.top = self.top.next
            self.size -= 1
            print(f"El elemento {data} fue eliminado.")
        else:
            print("El StackArray esta vacio.")

    def clear(self):
        self.top = None
        self.size = 0

    def search(self, data):
        probe = self.top
        while probe:
            if probe.data == data:
                return "This element is present in Stack"
            else:
                probe = probe.next
        return "This element not found in Stack"

    def printStack(self):
        probe = self.top
        while probe:
            print(probe.data)
            probe = probe.next

mencioan a LIFO o last in first out

mencion a FIFO o first in first out

Comparto mi solución a los dos retos.

Reto 1

"""
RETO 1

* Crear una clase stack
* Añadir los metodos para:
    - Retornar / buscar un elemento
    - Recorrer el stack
    - Vaciar el stack
"""

from node import Node


class Stack:
    def __init__(self):
        self.top = None
        self.size = 0 


    def push(self, data):
        node = Node(data)

        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1


    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None

            return data

        else:
            return "The stack is empty"

        
    def peek(self):
        if self.top:
            return self.top.data
        else:
            return "The stack is empty"


    def clear(self):
        while self.top:
            self.pop()

    
    def search_element(self, data):
        if self.top:
            current = self.top
            while current:
                if current.data == data:
                    return (f'Elemet {data} found')
                current = current.next
            return (f'Elemet {data} not found')

Reto 2
Clase array

class Array:
    def __init__(self, capacity, fill_value=None):
        self.items = list()

        for i in range(capacity):
            self.items.append(fill_value)


    def __len__(self):
        return len(self.items)


    def __str__(self):
        return str(self.items)


    def __iter__(self):
        return iter(self.items)


    def __getitem__(self, index):
        return self.items[index]


    def __setitem__(self, index, new_item):
        self.items[index] = new_item


    def __pop__(self):
        return self.items.pop()

Clase Stack

"""
RETO 2

* Crear una clase stack que herede de una clase Array
* Crear los metodos de stack
"""
from array import Array


class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.top = None
        self.size = 0 
        self.data = Array(self.capacity)


    def push(self, data):

        if self.size == self.capacity:
            print('Stack full')
            return False

        if self.size < self.capacity:
            self.data[self.size] = data
            self.top = data
            
            self.size += 1


    def pop(self):
        if self.size > 0:
            data = self.top
            self.size -= 1
            self.data.__pop__()

            if self.size > 0:
                self.top = self.data[self.size - 1]
            else:
                self.top = None

            return data

        else:
            return "The stack is empty"

        
    def peek(self):
        if self.top:
            return self.top
        else:
            return "The stack is empty"


    def clear(self):
        while self.top:
            self.pop()

    
    def search_element(self, data):
        if self.top:
            current = self.top
            for i in range(self.size):
                if current == data:
                    return (f'Element {data} found')
                current = self.data[i]
            return (f'Element {data} not found')

Solucion al Reto #1

class Stack:
    """Stack data structure based in nodes"""

    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        node = Node(data)

        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1

    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None

            return data
        else:
            return "The stack is empty"

    def peek(self):
        if self.top:
            return self.top.data
        else:
            return "The stack is empty"

    def clear(self):
        while self.top:
            self.pop()

    def clear_v2(self):
        self.__init__()

    def iter(self):
        probe = self.top
        while probe != None:
            yield probe.data
            probe = probe.next

    def search(self, data):
        if self.top:
            for data_stored in self.iter():
                if data_stored == data:
                    return f"Data '{data}' found"
            return f"Data '{data}' do not  found"
        else:
            return "The stack is empty"

Solucion al reto #2

class Stack_list():
    """Stack data structure based in arrays"""

    def __init__(self, size):
        """Create the Sack based in arrays

        Args:
            size (int): the size or capacity of the stack
        """
        self.top = None
        self.items = Array(size)
        self._size = size
        self._counter = 0  # to know where is the top

    def push(self, data):

        if self._counter < self._size:
            self.items.__setitem__(self._counter, data)
            self._counter += 1
        else:
            return f"The stack is full, the item '{data}' was not added"

    def iter(self):
        """Returns each element, form top to bottom (FIFO)"""
        for index in range(self._counter-1, -1, -1):
            yield self.items.__getitem__(index)

    def pop(self):
        """Returns the peek element and deletes form the stack
            if is empty then returns a string saying the stack is empty
        """
        if self._counter > 0:
            element = self.items.__getitem__(self._counter-1)
            self.items.__setitem__(self._counter-1, None)
            self._counter -= 1
        else:
            return "The stack is empty"
        return element

    def clear(self):
        """Clear the stack, set all the items with None value and
            set the _counter to 0"""
        self.__init__(self._size)

    def search(self, target):
        """Search if a specific data is in the stack and returns the index (int) of the item
            and if the data was not find then returns a None value
            """
        if self._counter > 0:
            index = -1
            for data in self.iter():
                index += 1
                if data == target:
                    print(f"Data '{target}' found")
                    return self._counter-index
            else:
                print(f"Data '{target}' did not find")
                return None
        else:
            print("The stack is empty")
            return None

Aún me gustaria cambiar algo para que el index empezara desde 0 pero será en otra ocasión, haha creo que por ahora ya esta bien.

reto 2

from nuevalista import newlist

class StackArray(newlist):
    def __init__(self, capacity, fill_value = None):
        super().__init__(capacity, fill_value)
        self.capacity = capacity
        self.top = None
        self.size = 0
    
    def push(self, data):
        if self.size == self.capacity:
            print("the Stack is full")
            return("the stack is full")
        else:
            self.__setitem__(self.size , data)
            self.top = self.__getitem__(self.size)
            self.size+=1
            
    
    def pop(self):
        
        self.__setitem__(self.size-1, None)
        self.top = self.__getitem__(self.size-2)
        self.size-=1
        
    def peek(self):
        print(self.top)
            
        

toco = StackArray(5)
toco.push("cumbia")
toco.push("420")
toco.push("samsun")
toco.push("palo")
toco.push("pibe")
toco.push("dato")
toco.pop()
toco.pop()
toco.peek()
print(toco)

Reto 1:

from node import Node

class Stack1:
    def __init__(self):
        self.top = None
        self.size = 0
    
    def push(self,data): # agregar nodo al stack
        node = Node(data)
        if self.top:
            node.next = self.top # aqui es donde anexamos el nuevo nodo al anterior
            self.top = node 
            print(f"Node add to the stack: {self.top.data}")
        else:
            self.top = node
            print(f"Node add to the stack: {self.top.data}")
        
        self.size += 1
    
    def pop(self): # eliminamos el nodo top XD
        data = self.top.data
        if self.top:
            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None
            print(data)
            self.size -= 1    
        else:
            print("the Stack is empty")
    
    def peek(self): #imprime el nodo que esta al top
        if self.top:
            print(f"the Node that is on the top: {self.top.data}")
            return self.top.data
    
    def clear(self): #limpiamos el stack
        self.top = None
        self.size = 0
        print("____________stack empty")
    
    
    def viewstack(self): # recorremos el stack desde el top hasta abajo
        originalstack = self.top
        while self.top:
            print(self.top.data)
            self.top = self.top.next
        self.top = originalstack
    
    def search(self,data): # encotrar dato/nodo
        while self.top != None:
            if self.top.data == data:
                print(f"Data found: {data}")
                return self.top.data
            else:
                if self.top:
                    self.top = self.top.next
        print("Not found")
    
    def size(self): # tamaño del stack
        print(self.size)
        return self.size
    
    def print_stack(self): # imprime el stack completo en forma de lista
        originalstack = self.top
        stacklist=[]
        while self.top:
            stacklist.append(self.top.data)
            self.top = self.top.next
        print(stacklist)
        self.top = originalstack

class pila:
    def __init__(self, data, nodo_after = None, nodo_next = None) -> None:
        self.data = data
        self.next = nodo_next
        self.after = nodo_after


class listPila:
    def __init__(self):
        self.after = None
        self.top = None
        self.size = 0

    def add(self, data):
        if not self.top:
            self.top = pila(data,self.after)
        else:
            self.after = self.top
            self.top.next = pila(data,self.after)
            self.top = self.top.next
        self.size += 1



    def pop(self):
        if self.top == None :
            return "esta vacia"

        else:
            self.data = self.top.data
            self.top = self.after
            self.after = self.top.after
            self.size -= 1
        return self.data

    def clear(self):
        while(self.top):
            print(f"se ha eliminado {self.top.data}")
            self.top.data = None
            self.top = self.top.after

    def find(self,data):
        after = self.top 
        indice = 0
        while after:
            indice += 1
            if (after.data == data):
                return f"encontrado en el indice {indice - 1}"
            after = after.after
        return f"el dato {data} no existe"
        

    def idx(self,index):
        after = self.top

        if not after: raise IndexError
        if index < 0 and self.size - index >= 0:
            index = self.size - index
        elif index > self.size or index < 0:
            raise IndexError
            
        idx = self.size
        while idx:
            if idx == index:
                return after.data
            idx -= 1
            after = after.after
        return self.top.data

    def printf(self):
        if not self.top:
            print("No hay valor")
            return
        idx = 0
        top = self.top
        while top:
            print(f" [{idx}] = {top.data}")
            idx += 1
            top = top.after

if __name__ == "__main__":
    lista = listPila()
    lista.add("uno")
    lista.add("tres")
    lista.add("ok")
    lista.printf()
    print(f"se elimino el dato {lista.pop()}")
    lista.printf()
    print(lista.find("tres"))
    print(lista.idx(1))
    lista.clear()
    lista.printf()

Reto#1

class Node():
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        node = Node(data)

        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node

        self.size += 1
    
    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None
            
            return data
        else:
            return "The stack is empty"
    
    def peek(self):
        if self.top:
            return self.top.data
        else:
            return "The stack is empty"
        
    def clear(self):
        while self.top:
            self.pop()

    def search(self, target_item):
        if self.size <= 0:
            print("The stack is empty")
        else:
            probe = self.top
            while probe.next != None and target_item != probe.data:
                probe = probe.next

            if probe.data == target_item:
                print(f'Target item {target_item} has been found')
                return probe
            else:
                print(f'Target item {target_item} is not in stack')
                return -1
    
    def iter(self):
        probe = self.top

        while probe:
            val = probe.data
            probe = probe.next
            yield val

    def __str__(self):
        probe = self.top
        result = []
        while probe != None:
            result.append(str(probe.data))
            probe = probe.next
        result.reverse()
        return " ".join(result)
    
    def empty(self):
        self.__init__()

Reto 1:

Reto 2:

Mi solución al reto "stack con base en arrays"
Implemente los magic methods necesarios para que la iteración ocurra de manera natural como en cualquier lista en python

class ArrayStack(Array):

    def __init__(self, size=0):
        super().__init__(size)
        self._top = -1

    def push(self, data):
        if self._top + 1 == len(self.items):
            return 'Full Stack'

        self._top += 1
        self.items[self._top] = data

    def pop(self):
        if self.items[self._top]:
            self.items[self._top] = None
            self._top -= 1
        else:
            return 'Empty Stack'

    def __iter__(self):
        self.size = len(self.items)
        return self

    def __next__(self):
        if self.size == 0:
            raise StopIteration
        else:
            value = self.items[self.size - 1]
            self.size -= 1
            return value
    
    def peek(self):
        return self.items[self._top]

    def clear(self):
        for index in range(0, len(self.items)):
            self.items[index] = None
            self._top = -1

Reto 1, agregue estos metodos al Stack:

     def clear(self):
        self.top = None
        self.size = 0
    
    def contains(self, data):
        probe = self.top
        while probe != None:
            if probe.data == data:
                return True
            probe = probe.next
        
        return False
    
    def __iter__(self):
        self._probe = self.top
        return self
    
    def __next__(self):
        if self._probe == None:
            raise StopIteration
        data = self._probe.data
        self._probe = self._probe.next
        return data

Reto 2:

class StackArray(Array):

    def __init__(self, capacity, fill_value=None):
        super().__init__(capacity, fill_value=fill_value)
        self.size = 0

    def push(self, data):
        if self.size == self.capacity:
            raise MemoryError("Stack is full")
        if self.size <= -1:
            self.size = 0
        
        self[self.size] = data
        self.size = self.size + 1
    
    def pop(self):
        if self.size <= -1:
            return None
        
        if self.size == self.capacity:
            self.size = self.size - 1

        data = self[self.size]
        self[self.size] = None
        self.size = self.size - 1
        
        return data
    
    def peek(self):
        if self.size <= -1:
            return None
        if self.size == self.capacity:
            return self[self.size - 1]
        
        return self[self.size]
    
    def clear(self):
        self.items = list()
        self.size = 0
    
    def contains(self, data):
        for item in self:
            if data == item:
                return True
        
        return False
    
    def __iter__(self):
        self._top_pos = self.size
        if self._top_pos == self.capacity:
            self._top_pos = self._top_pos - 1
        return self
    
    def __next__(self):
        if self._top_pos <= -1:
            raise StopIteration
        data = self[self._top_pos]
        self._top_pos = self._top_pos - 1
        return data

Reto 2

import random

class Array:
    def __init__(self, capacity, fill_value=None):
        self.items = list()
        for i in range(capacity):
            self.items.append(fill_value)
        

    def __len__(self):
        return len(self.items)


    def __str__(self):
        return str(self.items) 


    def  __iter__(self):
        return iter(self.items)


    def __getitem__(self, index):
        return self.items[index]
        

    def __setitem__(self, index, new_item):
        self.items[index] = new_item


    def __remitem__(self, name_array):
        for i in range(len(name_array)):
            self.items[i] = random.randint(0, 100)
    
    def __sumitem__(self):
        try:    
            return print(sum(self.items))
        except TypeError:
            print('Se produjo en error, al parecer hay un string en la lista')

    def append(self, data):
        return self.items.append(data)

    
    def pop(self, index):
        return self.items.pop(index)

from array import Array

class OneArray(Array):
    def __init__(self, capacity, fill_value = None):
        Array.__init__(self, capacity, fill_value)
        

class StacksArray:
    def __init__(self, capacity):
        self.top = OneArray(capacity)
        self.top.__remitem__(self.top)
        

    def push(self, data):
        if self.top == None:
            self.top.append(data)
        else:
            self.top.append(data)
        

    def travel(self):
        if self.top == None:
            return print('the stack is empty')
        else:
            for i in range(len(self.top)):
                print(self.top[i])
            print("*" * 20)


    def pop(self):
        for i in range(len(self.top)):
            if self.top[i] == None:
                return print('the stack is empty')
            else:
                i += 1
        i -= 1
        self.top.pop(i)
        
    def peek(self):
        for i in range(len(self.top)):
            if self.top[i] == None:
                return print('the stack is empty')
            else:
                i += 1
        i -= 1
        print(self.top[i])
        print("*" * 20)

    
    def search(self, data):
        item = data
        for i in range(len(self.top)):
            if self.top[i] == item:
                return print(f"the element {self.top[i]} has been found ")
                i += 1
        i -= 1
        if self.top[i] != item:
            print(f"the element {item} is not in the stack")
        
           
    def clear(self):
        self.top = None
      

if __name__ == '__main__':
    stack = StacksArray(5)
    stack.push(100)
    stack.push(29)
    stack.push(42)
    stack.push(89)
    stack.travel()
    stack.peek()
    stack.pop()
    stack.travel()
    stack.peek()
    stack.search(29)
    stack.clear()
    stack.travel()

Reto 1

from node import Node

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
        


    def push(self, data):
        node = Node(data)

        if self.top:
            node.next = self.top
            self.top = node
        else:
            self.top = node


        self.size += 1

    def pop(self):
        if self.top:
            data = self.top.data
            self.size -= 1

            if self.top.next:
                self.top = self.top.next
            else:
                self.top = None


            return print(data) 

        else:
            return "the stack is empty"



    def peek(self):
        if self.top:
            return print(self.top.data)
        else:
            return print("the stack is empty")


    def search(self, data):
        item = data
        while self.top != None and item != self.top.data:
            self.top = self.top.next

        if self.top != None:
            print(f"the element {self.top.data} has been found ")
        else:
            print(f"the element {item} is not in the stack")
            
    def travel(self):
        probe = self.top
        while probe != None:
            print(probe.data)
            probe = probe.next
        if self.top is None:
            print('the stack is empty')





    def clear(self):
        self.top = None
        self.size = None

if __name__ == '__main__':
    food = Stack()
    food.push('ham')
    food.push('egg')
    food.push('spam')
    food.travel()
    food.search('egg')
    food.clear()
    food.peek()