Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 5K vistas

    Pilas en C++

    Cargado por

    rikudouriis
    El documento proporciona una descripción detallada de las pilas, incluyendo sus definiciones, aplicaciones, operaciones básicas y diferentes formas de implementación. Explica que las pilas son estructuras de datos LIFO donde el último elemento insertado es el primero en extraerse, y cubre temas como la creación de pilas, agregar y eliminar elementos, y comprobar si una pila está vacía o acceder a su elemento superior. También analiza implementaciones de pilas mediante arrays y estructuras dinámicas enlazadas.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd

    Pilas en C++

    Cargado por

    rikudouriis
    5K vistas7 páginas
    El documento proporciona una descripción detallada de las pilas, incluyendo sus definiciones, aplicaciones, operaciones básicas y diferentes formas de implementación. Explica que las pilas son estructuras de datos LIFO donde el último elemento insertado es el primero en extraerse, y cubre temas como la creación de pilas, agregar y eliminar elementos, y comprobar si una pila está vacía o acceder a su elemento superior. También analiza implementaciones de pilas mediante arrays y estructuras dinámicas enlazadas.

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    DOC, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento proporciona una descripción detallada de las pilas, incluyendo sus definiciones, aplicaciones, operaciones básicas y diferentes formas de implementación. Explica que las pilas son estructuras de datos LIFO donde el último elemento insertado es el primero en extraerse, y cubre temas como la creación de pilas, agregar y eliminar elementos, y comprobar si una pila está vacía o acceder a su elemento superior. También analiza implementaciones de pilas mediante arrays y estructuras dinámicas enlazadas.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    5K vistas7 páginas

    Pilas en C++

    Cargado por

    rikudouriis
    El documento proporciona una descripción detallada de las pilas, incluyendo sus definiciones, aplicaciones, operaciones básicas y diferentes formas de implementación. Explica que las pilas son estructuras de datos LIFO donde el último elemento insertado es el primero en extraerse, y cubre temas como la creación de pilas, agregar y eliminar elementos, y comprobar si una pila está vacía o acceder a su elemento superior. También analiza implementaciones de pilas mediante arrays y estructuras dinámicas enlazadas.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    Está en la página 1de 7

    CONSIDERACIONES TEORICAS.

    • PILAS(1era definición)

    Son unas estructuras que son más utilizadas siempre que se quieran recuperar
    una serie de elementos en orden inverso a como se introdujeron.

    Tanto la extracción como la inserción de un elemento en la pila se realiza por la


    parte superior, por lo tanto, el único elemento al que podemos acceder es el
    ultimo, y como el ultimo elemento que se pone en la pila es el primero que se
    puede sacar, a estas estructuras dinámicas llamadas pilas se les conoce como
    LIFO (Last In First Off).

    Las pilas se deben implementar de forma dinámica utilizando punteros, pero si


    el lenguaje de programación que estamos utilizando no admite punteros,
    entonces tendremos que utilizar arrays, y además una variable que
    normalmente se le da el nombre de `cima' y es la que apunta al último
    elemento de la pila.

    Aplicaciones de las pilas: el uso más común que suele darse a las pilas es
    cuando hacemos una llamada desde un programa a otro subprograma.

    Se utiliza las pilas para guardar el lugar desde donde se hizo la llamada y para
    almacenar el estado de las variables en el momento en que se hace la llamada.
    También se utilizan en todos los algoritmos recursivos para almacenar el valor
    de las variables y los parámetros.
    Pilas-(2da definición)
    Las pilas son estructuras de datos que tienes dos operaciones básicas:

    o push (para insertar un elemento)

    ⇒ pop (para extraer un elemento). Su característica fundamental es que al


    extraer se obtiene siempre el último
    elemento que acaba de insertarse.

    Por esta razón también se conocen como estructuras de datos LIFO (del inglés
    Last In First Out). Una posible implementación mediante listas enlazadas sería
    insertando y extrayendo siempre por el principio de la lista. Gracias a las pilas
    es posible el uso de la recursividad (lo veremos en detalle en el tema
    siguiente).

    La variable que llama al mismo procedimiento en el q está, habrá que


    guardarla así como el resto de variables de la nueva llamada, para a la vuelta
    de la recursividad ir sacándolas, esto es posible a la implementación de pilas.
    Las pilas se utilizan en muchas aplicaciones que utilizamos con
    Frecuencia.

    Por ejemplo, la gestión de ventanas en Windows (cuando cerramos una


    ventana siempre recuperamos la que teníamos detrás). Otro ejemplo es la
    evaluación general de cualquier expresión matemática para evitar tener que
    calcular el número de variables temporales que hacen falta.

    Por ejemplo:
    3 + 4 * (8 – 2 * 5)
    Operaciones con Pila

    • Asociadas con la estructura pila • - Operaciones para comprobar


    existen una serie de operaciones tanto la información contenida
    necesarias para su manipulación. en la pila, como el propio estado
    Éstas son: de la cima:

    • Iniciación de la estructura: • - Comprobar si la pila está vacía


    (PilaVacia): Esta operación es
    • - Crear la pila (CrearPila): La necesaria para poder decidir si
    operación de creación de la pila es posible eliminar elementos de
    inicia la pila como vacía. la pila.

    • Operaciones para añadir y • - Acceder al elemento situado en


    eliminar información: la cima (CimaPila): Nos indica
    el valor del elemento situado en
    • - Añadir elementos en la cima la parte superior de la pila.
    (Apilar): pondrá un nuevo
    elemento en la parte superior de • La especificación correcta de
    la pila. todas estas operaciones
    permitirá definir adecuadamente
    • - Eliminar elementos de la cima una pila.
    (Desapilar): lo que hará será
    devolver el elemento superior de
    la cima y eliminarlo de la pila.

    Operaciones con Pila

    Una declaración más formal de las operaciones definidas sobre la estructura de


    datos pila, y los axiomas que las relacionan podrían ser las siguientes:

     estructura
     pila ( valor ) / * valor será el tipo de datos que podremos guardar en
    la pila */
     operaciones
     crear_pila ( ) -> pila
     apilar ( pila , valor ) -> pila
     desapilar ( pila ) -> pila
     cima_pila ( pila ) -> valor
     pila_vacia ( pila ) -> lógico
     axiomas
     ∀ stack ∈ pila, x ∈ valor se cumple que:
     pila_vacia ( crear_pila ( ) ) -> cierto
     pila_vacia ( apilar ( stack, x ) ) -> falso
     desapilar ( crear_pila ( ) ) -> error
     desapilar ( apilar ( stack, x ) ) -> stack
     cima_pila ( crear_pila ( ) ) -> error
     cima_pila ( apilar ( stack, x ) ) -> x
    ⇒ Implementación mediante estructuras estáticas
    • La forma más simple, y habitual, de representar una pila es mediante un
    vector unidimensional. Este tipo de datos permite definir una secuencia
    de elementos (de cualquier tipo) y posee un eficiente mecanismo de
    acceso a la información contenida en ella.

    • Al definir un array hay que determinar el número de índices válidos y,


    por lo tanto, el número de componentes definidos. Entonces, la
    estructura pila representada por un array tendrá limitado el número de
    posibles elementos.

    • La parte privada de la clase, será pues un vector donde guardaremos la


    información. El primer elemento de la pila se almacenará en info[0], será
    el fondo de la pila, el segundo elemento en info[1] y así sucesivamente.
    En general, el elemento i-ésimo estará almacenado en info[i - 1].

    • Como todas las operaciones se realizan sobre la cima de la pila, es


    necesario tener correctamente localizada en todo instante esta posición.
    Es necesaria una variable adicional, cima, que apunte al último elemento
    de la pila o nos diga cuantos elementos tenemos en ella.

    • Implementación mediante estructuras estáticas (Crear-Pila)

    Resumiendo, la clase Pila contendrá, en esta implementación, la Siguiente parte


    privada:

    class Pila

    public: ...

    private:

    Vector vect;

    int cima;

    };

    Donde Vector será:

    typedef Valor Vector[MAX];

    Suponiendo Valor, el tipo de dato que se puede almacenar en la pila, y MAX


    una constante que me limita el tamaño máximo de la pila.
    ⇒ Implementación pila vacía.

    Algoritmo Pila_Vacia

    Entrada

    stack: Pila

    Salida

    ( CIERTO, FALSO)

    Inicio

    Si ( stack.Cima = 0 ) entonces

    Devolver ( CIERTO )

    Sino

    Devolver ( FALSO )

    Fin_si

    Fin ‫٭‬

    bool Pila::PilaVacia (void) { return cima == 0; }

    • Implementación mediante estructuras dinámicas (Desapilar)

    Operación de eliminación de información (DESAPILAR)

    La único que hay que tener en cuenta a la hora de diseñar un algoritmo


    para esta operación es la utilización eficiente de la memoria, de forma que
    el espacio ocupado por el nodo borrado vuelva a estar disponible para el
    sistema. Recordar que si la pila está vacía no se puede desapilar.

    mplementación mediante estructuras dinámicas (Desapilar)

    ⇒ Algoritmo Desapilar
    ⇒ Entrada
    ⇒ stack: Pila de Valor
    ⇒ Salida
    ⇒ stack
    ⇒ x: Valor
    ⇒ Variable
    ⇒ p_aux: Puntero_a_Nodo_pila
    ⇒ Inicio
    ⇒ Si ( Pila_Vacia (stack) ) entonces
    ⇒ Error “ pila_vacia”
    ⇒ Sino
    ⇒ p_aux ← stack.Cima
    ⇒ stack.Cima ← p_aux^.Sig
    ⇒ Liberar_Espacio (p_aux)
    ⇒ Fin_si
    ⇒ Fin
    ⇒ bool Pila::Desapilar (void) { bool error; Puntero p_aux; if (cima == NULL)
    error = true; else { error = false; p_aux = cima; cima = cima->sig; delete
    p_aux; } return error;

    Implementación mediante estructuras dinámicas (Cima-Pila)

    Operación de consulta de información (CIMA_PILA)

    Al elemento "visible" de la pila se puede acceder fácilmente a través del


    puntero que le referencia, cima, que siempre debe existir y ser adecuadamente
    actualizado.

    Algoritmo Cima_Pila

    Entradas

    stack: Pila de Valor

    Salidas

    Valor

    Inicio

    {* comprobar si existe información en la pila *}

    {* esta operación no depende de la representación, siempre es necesaria *}

    Si ( Pila_Vacia ( stack ) ) entonces

    Error “ pila vacia”

    sino
    Devolver (Cima^.Info)

    Fin_si

    Fin

    bool Pila::CimaPila (Valor & x) { bool error; if (cima == NULL) error = true; else
    { error = false; x = cima->info; } return error; }

    También podría gustarte