El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Implementació de Piles

Següent ►
►

En aquest tema, aprendrem com implementar una pila, una estructura de dades fonamental en la programació. Les piles segueixen el principi LIFO (Last In, First Out), és a dir, l'últim element que entra és el primer que surt. Veurem com implementar una pila utilitzant arrays i llistes enllaçades, i també discutirem les operacions bàsiques que es poden realitzar sobre una pila.

Conceptes Clau

Abans de començar amb la implementació, repassem les operacions bàsiques d'una pila:

  1. Push: Afegeix un element al cim de la pila.
  2. Pop: Elimina i retorna l'element del cim de la pila.
  3. Peek: Retorna l'element del cim de la pila sense eliminar-lo.
  4. isEmpty: Comprova si la pila està buida.
  5. Size: Retorna el nombre d'elements a la pila.

Implementació Utilitzant Arrays

Avantatges i Desavantatges

Avantatges:

  • Accés ràpid als elements mitjançant l'índex.
  • Implementació senzilla.

Desavantatges:

  • Capacitat fixa (cal definir la mida màxima de la pila).
  • Pot requerir més espai de memòria si la mida màxima és gran.

Codi d'Exemple

class PilaArray:
    def __init__(self, capacitat):
        self.capacitat = capacitat
        self.pila = [None] * capacitat
        self.cim = -1

    def push(self, element):
        if self.cim == self.capacitat - 1:
            raise Exception("La pila està plena")
        self.cim += 1
        self.pila[self.cim] = element

    def pop(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        element = self.pila[self.cim]
        self.pila[self.cim] = None
        self.cim -= 1
        return element

    def peek(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        return self.pila[self.cim]

    def is_empty(self):
        return self.cim == -1

    def size(self):
        return self.cim + 1

# Exemple d'ús
pila = PilaArray(5)
pila.push(10)
pila.push(20)
print(pila.pop())  # Sortida: 20
print(pila.peek())  # Sortida: 10
print(pila.size())  # Sortida: 1

Implementació Utilitzant Llistes Enllaçades

Avantatges i Desavantatges

Avantatges:

  • Capacitat dinàmica (no cal definir la mida màxima).
  • Ús eficient de la memòria.

Desavantatges:

  • Accés més lent als elements (cal recórrer la llista).

Codi d'Exemple

class Node:
    def __init__(self, valor):
        self.valor = valor
        self.seguent = None

class PilaLlistaEnllaçada:
    def __init__(self):
        self.cim = None
        self._size = 0

    def push(self, element):
        nou_node = Node(element)
        nou_node.seguent = self.cim
        self.cim = nou_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        element = self.cim.valor
        self.cim = self.cim.seguent
        self._size -= 1
        return element

    def peek(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        return self.cim.valor

    def is_empty(self):
        return self.cim is None

    def size(self):
        return self._size

# Exemple d'ús
pila = PilaLlistaEnllaçada()
pila.push(10)
pila.push(20)
print(pila.pop())  # Sortida: 20
print(pila.peek())  # Sortida: 10
print(pila.size())  # Sortida: 1

Exercicis Pràctics

Exercici 1: Implementació de la Pila amb Arrays

Implementa una pila utilitzant arrays amb les operacions bàsiques (push, pop, peek, is_empty, size). Prova la teva implementació amb diferents casos de prova.

Exercici 2: Implementació de la Pila amb Llistes Enllaçades

Implementa una pila utilitzant llistes enllaçades amb les operacions bàsiques (push, pop, peek, is_empty, size). Prova la teva implementació amb diferents casos de prova.

Solucions

Solució a l'Exercici 1

class PilaArray:
    def __init__(self, capacitat):
        self.capacitat = capacitat
        self.pila = [None] * capacitat
        self.cim = -1

    def push(self, element):
        if self.cim == self.capacitat - 1:
            raise Exception("La pila està plena")
        self.cim += 1
        self.pila[self.cim] = element

    def pop(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        element = self.pila[self.cim]
        self.pila[self.cim] = None
        self.cim -= 1
        return element

    def peek(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        return self.pila[self.cim]

    def is_empty(self):
        return self.cim == -1

    def size(self):
        return self.cim + 1

# Prova
pila = PilaArray(5)
pila.push(10)
pila.push(20)
print(pila.pop())  # Sortida: 20
print(pila.peek())  # Sortida: 10
print(pila.size())  # Sortida: 1

Solució a l'Exercici 2

class Node:
    def __init__(self, valor):
        self.valor = valor
        self.seguent = None

class PilaLlistaEnllaçada:
    def __init__(self):
        self.cim = None
        self._size = 0

    def push(self, element):
        nou_node = Node(element)
        nou_node.seguent = self.cim
        self.cim = nou_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        element = self.cim.valor
        self.cim = self.cim.seguent
        self._size -= 1
        return element

    def peek(self):
        if self.is_empty():
            raise Exception("La pila està buida")
        return self.cim.valor

    def is_empty(self):
        return self.cim is None

    def size(self):
        return self._size

# Prova
pila = PilaLlistaEnllaçada()
pila.push(10)
pila.push(20)
print(pila.pop())  # Sortida: 20
print(pila.peek())  # Sortida: 10
print(pila.size())  # Sortida: 1

Resum

En aquesta secció, hem après com implementar una pila utilitzant arrays i llistes enllaçades. Hem vist les operacions bàsiques que es poden realitzar sobre una pila i hem proporcionat exemples de codi per a cada implementació. També hem inclòs exercicis pràctics per reforçar els conceptes apresos. En el següent tema, explorarem les aplicacions de les piles en la programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats