Operaciones Fundamentales de la Estructura de Datos Pila con Punteros

Implementación de una Estructura de Datos Pila

A continuación, se detalla la implementación de un Tipo Abstracto de Dato (TAD) Pila utilizando punteros y registros en pseudocódigo. Se definen los tipos de datos necesarios y las operaciones fundamentales.

Definición de Tipos

Se define la estructura de la pila y los nodos que la componen, utilizando punteros para enlazar los elementos.

tipos
    ptDato = ↑unDato;

    unDato = registro
        dato: elemento;
        sig: ptDato;
    fin registro

    pila = registro
        cim: ptDato;  // Puntero a la cima de la pila
        alt: natural; // Altura o número de elementos
        iter: ptDato; // Puntero para el iterador
    fin registro

Operaciones Básicas de la Pila

Procedimiento crearVacía

Devuelve una pila vacía, sin elementos.

procedimiento crearVacía(sal p: pila)
principio
    p.cim := nil;
    p.alt := 0;
fin

Procedimiento apilar

Añade un elemento 'e' a la pila 'p', convirtiéndolo en la nueva cima.

procedimiento apilar(e/s p: pila; ent e: elemento)
    variable aux: ptDato;
principio
    aux := p.cim;
    nuevoDato(p.cim);
    p.cim↑.dato := e;
    p.cim↑.sig := aux;
    p.alt := p.alt + 1;
fin

Procedimiento desapilar

Si la pila 'p' no es vacía, elimina el último elemento que fue apilado. Si es vacía, no realiza ninguna acción.

procedimiento desapilar(e/s p: pila)
    variable aux: ptDato;
principio
    si p.alt ≠ 0 entonces
        aux := p.cim;
        p.cim := p.cim↑.sig;
        disponer(aux);
        p.alt := p.alt - 1;
    fin si
fin

Función cima

Precondición: la pila 'p' no es vacía. Devuelve el último elemento apilado en 'p'.

función cima(p: pila) devuelve elemento
principio
    devuelve p.cim↑.dato;
fin

Función esVacía

Devuelve verdadero si y solo si la pila 'p' no tiene elementos.

función esVacía(p: pila) devuelve booleano
principio
    devuelve (p.alt = 0);
fin

Función altura

Devuelve el número de elementos de la pila 'p'. Devuelve 0 si está vacía.

función altura(p: pila) devuelve natural
principio
    devuelve p.alt;
fin

Operaciones Adicionales

Procedimiento duplicar

Crea una copia exacta de la pila de entrada (pilaEnt) en la pila de salida (pilaSal).

procedimiento duplicar(ent pilaEnt: pila; sal pilaSal: pila)
    variables ptSal, ptEnt: ptDato;
principio
    si esVacía(pilaEnt) entonces
        crearVacía(pilaSal);
    sino
        ptEnt := pilaEnt.cim;
        nuevoDato(pilaSal.cim);
        pilaSal.cim↑.dato := ptEnt↑.dato;
        ptSal := pilaSal.cim;
        ptEnt := ptEnt↑.sig;
        
        mientras ptEnt ≠ nil hacer
            nuevoDato(ptSal↑.sig);
            ptSal := ptSal↑.sig;
            ptSal↑.dato := ptEnt↑.dato;
            ptEnt := ptEnt↑.sig;
        fin mientras;
        
        ptSal↑.sig := nil;
        pilaSal.alt := pilaEnt.alt;
    fin si
fin

Función iguales

Devuelve verdadero si y solo si pila1 y pila2 almacenan la misma secuencia de elementos.

función iguales(pila1, pila2: pila) devuelve booleano
    variables 
        pt1, pt2: ptDato;
        iguales: booleano := verdad;
principio
    si pila1.alt ≠ pila2.alt entonces
        devuelve falso;
    sino
        pt1 := pila1.cim;
        pt2 := pila2.cim;
        
        mientras pt1 ≠ nil y iguales hacer
            iguales := (pt1↑.dato = pt2↑.dato);
            pt1 := pt1↑.sig;
            pt2 := pt2↑.sig;
        fin mientras;
        
        devuelve iguales;
    fin si
fin

Procedimiento liberar

Vacía la pila 'p', liberando toda la memoria ocupada por sus nodos.

procedimiento liberar(e/s p: pila)
    variable aux: ptDato;
principio
    aux := p.cim;
    mientras aux ≠ nil hacer
        p.cim := p.cim↑.sig;
        disponer(aux);
        aux := p.cim;
    fin mientras;
    p.alt := 0;
fin

Manejo de Iteradores

Procedimiento iniciarIterador

Prepara el iterador para que el siguiente elemento a visitar sea la cima de la pila 'p', si existe.

procedimiento iniciarIterador(e/s p: pila)
principio
    p.iter := p.cim;
fin

Función existeSiguiente

Devuelve verdadero si el iterador puede avanzar a un siguiente elemento.

función existeSiguiente(p: pila) devuelve booleano
principio
    devuelve (p.iter ≠ nil);
fin

Procedimiento siguiente

Obtiene el elemento actual del iterador y lo avanza a la siguiente posición.

procedimiento siguiente(e/s p: pila; sal e: elemento; sal error: booleano)
principio
    si existeSiguiente(p) entonces
        error := falso;
        e := p.iter↑.dato;
        p.iter := p.iter↑.sig;
    sino
        error := verdad;
    fin si
fin