Què és una Pila?

Una pila és una estructura de dades lineal que segueix el principi LIFO (Last In, First Out), és a dir, l'últim element que entra és el primer que surt. Les piles són molt útils en diverses aplicacions informàtiques, com ara la gestió de la memòria, l'avaluació d'expressions aritmètiques i la navegació en navegadors web.

Característiques Principals de les Piles

LIFO (Last In, First Out): L'últim element afegit a la pila és el primer que es treu.
Operacions bàsiques: Les operacions principals que es poden realitzar en una pila són:
- Push: Afegir un element al cim de la pila.
- Pop: Treure l'element del cim de la pila.
- Peek/Top: Consultar l'element del cim sense treure'l.
- isEmpty: Comprovar si la pila està buida.
- Size: Obtenir el nombre d'elements a la pila.

Representació d'una Pila

Les piles es poden implementar utilitzant arrays o llistes enllaçades. A continuació, es mostra una comparació de les dues implementacions:

Característica	Array	Llista Enllaçada
Memòria	Espai fix, pot ser ineficient si no es coneix la mida màxima	Espai dinàmic, més eficient en ús de memòria
Temps d'accés	Accés ràpid a qualsevol element	Accés seqüencial, més lent
Complexitat	Push i Pop en O(1)	Push i Pop en O(1)
Flexibilitat	Mida fixa	Mida dinàmica

Exemples Pràctics

Implementació d'una Pila amb un Array

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

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

    def is_full(self):
        return self.cim == self.capacitat - 1

    def push(self, element):
        if self.is_full():
            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.cim -= 1
        return element

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

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

Implementació d'una Pila amb una Llista Enllaçada

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

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

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

    def push(self, element):
        nou_node = Node(element)
        nou_node.next = 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.data
        self.cim = self.cim.next
        self._size -= 1
        return element

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

    def size(self):
        return self._size

Aplicacions de les Piles

Les piles tenen múltiples aplicacions en informàtica, algunes de les quals són:

Gestió de la memòria: Les piles s'utilitzen per gestionar la memòria en la crida de funcions, on cada crida de funció afegeix un nou marc de pila.
Avaluació d'expressions: Les piles s'utilitzen per avaluar expressions aritmètiques i convertir expressions infixes a postfixes.
Navegació en navegadors web: Les piles s'utilitzen per implementar la funcionalitat de "endavant" i "enrere" en els navegadors web.

Conclusió

En aquesta secció, hem introduït el concepte de pila, les seves característiques principals, les operacions bàsiques i les seves implementacions utilitzant arrays i llistes enllaçades. També hem vist algunes de les aplicacions pràctiques de les piles. En la següent secció, explorarem les operacions bàsiques amb piles en més detall.

Introducció a les Piles

Què és una Pila?

Característiques Principals de les Piles

Representació d'una Pila

Exemples Pràctics

Implementació d'una Pila amb un Array

Implementació d'una Pila amb una Llista Enllaçada

Aplicacions de les Piles

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals