Computing">
Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 15 vistas

    Eda1 Pila

    Cargado por

    yaelypy
    Este documento describe la estructura de datos de la pila, incluidas sus operaciones principales como push(), pop() y peek(). Una pila sigue el principio LIFO (último en entrar, primero en salir) y se puede implementar usando listas enlazadas o arreglos. Las pilas se usan comúnmente para llamadas de función, deshacer/rehacer y evaluación de expresiones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Eda1 Pila

    Cargado por

    yaelypy
    15 vistas9 páginas
    Este documento describe la estructura de datos de la pila, incluidas sus operaciones principales como push(), pop() y peek(). Una pila sigue el principio LIFO (último en entrar, primero en salir) y se puede implementar usando listas enlazadas o arreglos. Las pilas se usan comúnmente para llamadas de función, deshacer/rehacer y evaluación de expresiones.

    Descripción original:

    Título original

    EDA1_PILA

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe la estructura de datos de la pila, incluidas sus operaciones principales como push(), pop() y peek(). Una pila sigue el principio LIFO (último en entrar, primero en salir) y se puede implementar usando listas enlazadas o arreglos. Las pilas se usan comúnmente para llamadas de función, deshacer/rehacer y evaluación de expresiones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    15 vistas9 páginas

    Eda1 Pila

    Cargado por

    yaelypy
    Este documento describe la estructura de datos de la pila, incluidas sus operaciones principales como push(), pop() y peek(). Una pila sigue el principio LIFO (último en entrar, primero en salir) y se puede implementar usando listas enlazadas o arreglos. Las pilas se usan comúnmente para llamadas de función, deshacer/rehacer y evaluación de expresiones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 9

    UNIVERSIDAD NACIONAL AUTÓNOMA DE

    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    PILA.
    Prof. Gerardo Tovar Tapia.

    Pila.
    Se han estudiado estructuras de datos de tamaño fijo, como arreglos de un solo
    subíndice, doble subíndice y structs.
    Ahora se presentan estructuras dinámicas de datos, cuyo tamaño crece y se encoge
    en tiempo de ejecución (Listas enlazadas, Las Pilas, Colas, Árboles).
    La Pila es una versión restringida de una lista enlazada. A una Pila se le puede
    añadir y retirar nuevos nodos únicamente de su parte superior. Por esta razón, se
    conoce una pila estructura de datos como últimas entradas, primeras salidas (LIFO
    por last-in, first-out).
    Se referencia una pila mediante un apuntador al elemento superior de la misma. El
    miembro de enlace en el último nodo de la pila se define a NULL, para indicar que
    se trata de la parte inferior de la pila misma.

    1
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Las funciones primarias utilizadas para manipular una pila son push y pop.
    PUSH: agrega un elemento a la pila. Si la pila está llena, se dice que es una
    condición de desbordamiento.

    Pop: elimina un elemento de la pila. Los elementos aparecen en el orden inverso


    en el que se empujan. Si la pila está vacía, se dice que es una condición de
    desbordamiento.

    Peek or Top: devuelve el elemento superior de la pila.

    isEmpty: Devuelve verdadero si la pila está vacía, de lo contrario es falso.

    2
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    La función push crea un nuevo nodo y lo coloca en la parte superior de la pila.


    La función pop elimina un nodo de la parte superior de la pila, liberado la memoria
    que fue asignada al nodo retirado, y regresando el valor retirado

    ¿Cómo entender una pila de forma práctica?


    Hay muchos ejemplos reales de una pila. Considere el ejemplo simple de platos
    apilados uno sobre otro en una cantina. La placa que está en la parte superior es la
    primera que se retira, es decir, la placa que se ha colocado en la posición más baja
    permanece en la pila durante el mayor período de tiempo. Entonces, simplemente
    se puede ver que sigue el orden LIFO / FILO.

    Complejidades de tiempo de las operaciones en la pila:

    push (), pop (), isEmpty () y peek () toman O (1) tiempo. No ejecutamos ningún bucle
    en ninguna de estas operaciones.

    3
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Puede implementarse a través de una matriz o listas enlazadas. Algunas de sus


    principales operaciones son: push(), pop(), top(), isEmpty(), size(), etc. Para realizar
    manipulaciones en una pila, se nos proporcionan ciertas operaciones. Cuando
    queremos insertar un elemento en la pila, la operación se conoce como operación
    push, mientras que cuando queremos eliminar un elemento de la pila, la operación
    se conoce como operación pop. Si tratamos de extraer de una pila vacía, se conoce
    como desbordamiento y si intentamos empujar un elemento en una pila que ya está
    llena, se conoce como desbordamiento.

    Operaciones de pila primaria:

    void push(int data): cuando se realiza esta operación, se inserta un elemento en la


    pila.
    int pop(): cuando se realiza esta operación, se elimina un elemento de la parte
    superior de la pila y se devuelve.
    Operaciones de pila auxiliar:

    int top (): esta operación devolverá el último elemento insertado que está en la parte
    superior sin eliminarlo.
    int size(): Esta operación devolverá el tamaño de la pila, es decir, el número total de
    elementos presentes en la pila.
    int isEmpty(): Esta operación indica si la pila está vacía o no.
    int isFull(): Esta operación indica si la pila está llena o no.

    Tipos de Pila.
    Pila de registros: este tipo de pila también es un elemento de memoria presente
    en la unidad de memoria y solo puede manejar una pequeña cantidad de datos. La
    altura de la pila de registros siempre está limitada ya que el tamaño de la pila de
    registros es muy pequeño en comparación con la memoria.
    Pila de memoria: este tipo de pila puede manejar una gran cantidad de datos de
    memoria. La altura de la pila de memoria es flexible ya que ocupa una gran cantidad
    de datos de memoria.

    4
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    ¿Qué se entiende por Top of the Stack?

    Cuando se agrega un nuevo elemento a la pila, se coloca encima de los elementos


    existentes. De manera similar, cuando se elimina un elemento de la pila, el elemento
    superior se elimina primero. La parte superior de la pila es siempre el elemento al
    que se puede acceder actualmente para su visualización o manipulación.
    El puntero a través del cual se accede, inserta y elimina los elementos en la pila se
    llama la parte superior de la pila . Es el puntero al elemento superior de la pila.

    Aplicación de la estructura de datos de pila:

    Llamadas a funciones y recursividad: cuando se llama a una función, el estado


    actual del programa se coloca en la pila. Cuando la función regresa, el estado se
    extrae de la pila para reanudar la ejecución de la función anterior.
    Operaciones de deshacer/rehacer: la función de deshacer y rehacer en varias
    aplicaciones utiliza pilas para realizar un seguimiento de las acciones anteriores.
    Cada vez que se realiza una acción, se coloca en la pila. Para deshacer la acción,
    se extrae el elemento superior de la pila y se realiza la operación inversa.

    Evaluación de expresiones: la estructura de datos de pila se utiliza para evaluar


    expresiones en notaciones de infijo, posfijo y prefijo. Los operadores y operandos
    se insertan en la pila y las operaciones se realizan en función de los elementos
    superiores de la pila.

    Historial del navegador: los navegadores web usan pilas para realizar un
    seguimiento de las páginas web que visita. Cada vez que visita una página nueva,
    la URL se inserta en la pila, y cuando presiona el botón Atrás, la URL anterior se
    extrae de la pila.

    5
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Paréntesis equilibrados: la estructura de datos de pila se utiliza para comprobar


    si los paréntesis están equilibrados o no. Un paréntesis de apertura se inserta en la
    pila y un paréntesis de cierre se extrae de la pila. Si la pila está vacía al final de la
    expresión, los paréntesis están equilibrados.
    Algoritmos de retroceso: el algoritmo de retroceso utiliza pilas para realizar un
    seguimiento de los estados del proceso de resolución de problemas. El estado
    actual se coloca en la pila y, cuando el algoritmo retrocede, el estado anterior se
    extrae de la pila.

    Aplicación de Stack en la vida real:

     Soporte para CD/DVD.


     Pila de libros en una librería.
     Sistemas de centro de llamadas.
     Mecanismo de deshacer y rehacer en editores de texto.
     El historial de un navegador web se almacena en forma de pila.
     Los registros de llamadas, correos electrónicos y fotos de Google en cualquier
    galería también se almacenan en forma de pila.
     Las descargas y notificaciones de YouTube también se muestran en formato LIFO
    (la última aparece primero).
     Asignación de memoria por parte de un sistema operativo mientras se ejecuta un
    proceso.
    Ventajas de la pila:

    Fácil implementación: la estructura de datos de la pila es fácil de implementar


    utilizando matrices o listas vinculadas, y sus operaciones son fáciles de entender e
    implementar.

    Utilización eficiente de la memoria: Stack utiliza un bloque contiguo de memoria,


    lo que la hace más eficiente en la utilización de la memoria en comparación con
    otras estructuras de datos.

    Tiempo de acceso rápido: la estructura de datos de la pila proporciona un tiempo


    de acceso rápido para agregar y eliminar elementos a medida que los elementos se
    agregan y eliminan de la parte superior de la pila.

    6
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Ayuda en las llamadas a funciones: la estructura de datos de pila se utiliza para


    almacenar llamadas a funciones y sus estados, lo que ayuda en la implementación
    eficiente de llamadas a funciones recursivas.

    Admite el retroceso: la estructura de datos de la pila admite algoritmos de


    retroceso, que se utilizan en la resolución de problemas para explorar todas las
    soluciones posibles mediante el almacenamiento de los estados anteriores.

    Utilizado en el diseño del compilador: la estructura de datos de pila se utiliza en


    el diseño del compilador para analizar y analizar la sintaxis de los lenguajes de
    programación.

    Habilita las operaciones de deshacer/rehacer: la estructura de datos de pila se


    utiliza para habilitar las operaciones de deshacer y rehacer en varias aplicaciones,
    como editores de texto, herramientas de diseño gráfico y entornos de desarrollo de
    software.

    Desventajas de la pila:

    Capacidad limitada: la estructura de datos de la pila tiene una capacidad limitada,


    ya que solo puede contener una cantidad fija de elementos. Si la pila se llena, la
    adición de nuevos elementos puede provocar un desbordamiento de la pila, lo que
    provoca la pérdida de datos.

    Sin acceso aleatorio: la estructura de datos de la pila no permite el acceso


    aleatorio a sus elementos y solo permite agregar y eliminar elementos de la parte
    superior de la pila. Para acceder a un elemento en el medio de la pila, se deben
    eliminar todos los elementos por encima.

    Gestión de la memoria: la estructura de datos de la pila utiliza un bloque contiguo


    de memoria, lo que puede provocar la fragmentación de la memoria si se agregan
    y eliminan elementos con frecuencia.

    No apto para ciertas aplicaciones: la estructura de datos de la pila no es


    adecuada para aplicaciones que requieren acceder a elementos en el medio de la
    pila, como algoritmos de búsqueda o clasificación.

    7
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Desbordamiento y subdesbordamiento de la pila: la estructura de datos de la


    pila puede provocar un desbordamiento de la pila si se insertan demasiados
    elementos en la pila, y puede provocar un desbordamiento de la pila si se extraen
    demasiados elementos de la pila.

    Limitaciones de llamadas a funciones recursivas: si bien la estructura de datos


    de la pila admite llamadas a funciones recursivas, demasiadas llamadas a funciones
    recursivas pueden provocar un desbordamiento de la pila, lo que resulta en la
    terminación del programa.

    8
    UNIVERSIDAD NACIONAL AUTÓNOMA DE
    MÉXICO.

    FACULTAD DE INGENIERIA.

    ESTRUCTURAS DE DATOS Y ALGORITMOS I.

    Código de la Pila.

    También podría gustarte