Inicio / Directorio / Informática y Telecomunicaciones /

Pilas en programación: implementación y ejercicios resueltos

Informática y TelecomunicacionesActualizado el 9,72 KB

Resumen

El documento recoge ejercicios resueltos sobre pilas en programación, con su implementación en pseudocódigo: una pila con carga desde la última posición, una pila de tamaño restringido distribuida en contenedores, dos pilas compartiendo un mismo vector y la conversión de expresiones infijas a postfijas con su posterior evaluación. Con él el estudiante verá cómo se definen las operaciones básicas (inicializar, cargar, sacar, consultar, comprobar si está vacía o llena) y cómo aplicar las pilas a problemas de expresiones.

Puntos clave

  • Una pila es una estructura LIFO: el último elemento en entrar es el primero en salir.
  • Las operaciones básicas son inicializar, verificar si está vacía o llena, cargar (apilar), sacar (desapilar) y consultar la cima.
  • En la pila con dos pilas en un mismo vector, una crece desde el inicio y otra desde el final, y está llena cuando los topes se encuentran.
  • La función Infija_A_Postfija usa una pila para los operadores y Prioridad define que * y / tienen prioridad 2, y + y - prioridad 1.
  • Resolver_Postfija usa una pila para los operandos: al encontrar un operador, saca dos operandos y guarda el resultado del cálculo.

Ponte a prueba

Ejercicio 1: Implementación de una Pila con Elementos Agregados desde la Última Posición

En este ejercicio, se implementa una pila donde los elementos se agregan desde la última posición hacia la primera. Se definen las operaciones básicas de inicializar, verificar si está vacía, sacar un elemento y cargar un elemento.

Definición de la Estructura

  
    Constante
      Max = 100
    Tipo
      t_pila = Registro
        Dato: array[1..MAX] de tipo_dato
        tope: entero
      Fin Registro
    Var
      pila: t_pila

Procedimiento Inicializar_Pila

Inicializa la pila estableciendo el tope en la posición máxima.

  
    Procedimiento Inicializar_Pila (E/S pila: t_pila)
    Inicio
      pila.tope <- Max
    Fin

Función Pila_Vacia

Verifica si la pila está vacía.

  
    Función Pila_Vacia (pila: t_pila): lógico
    Inicio
      Pila_Vacia <- (pila.tope = Max)
    Fin

Procedimiento Sacar_Pila

Saca un elemento de la pila si no está vacía.

  
    Procedimiento Sacar_Pila (Var pila: t_pila)
    Inicio
      Si No(Pila_Vacia(pila)) entonces
        pila.tope <- pila.tope + 1
      Sino
        Escribir "La pila está vacía"
      Fin si
    Fin

Procedimiento Cargar_Pila

Agrega un elemento a la pila si no está llena.

  
    Procedimiento Cargar_Pila (E/S pila: t_pila, E nuevo: tipo_dato)
    Inicio
      Si no(Pila_Llena(pila)) Entonces
        Pila.dato[pila.tope] <- nuevo
        Pila.tope <- pila.tope - 1
      Si no
        Escribir "La pila está llena"
      Fin si
    Fin

Función Pila_Llena

Verifica si la pila está llena.

  
    Función Pila_Llena (pila: t_pila): lógico
    Inicio
      Pila_Llena <- (pila.tope = 0)
    Fin

Función Consultar_Pila

Consulta el elemento en la cima de la pila sin sacarlo.

  
    Función Consultar_Pila (pila: t_pila): tipo_dato
    Var
      Consultado: tipo_dato
    Inicio
      Si no(Pila_Vacia(pila)) entonces
        Consultado <- pila.dato[pila.tope + 1]
      Sino
        Consultado <- NULL
      Fin si
      Consultar_Pila <- Consultado
    Fin

Ejercicio 2: Implementación de una Pila con Tamaño Restringido

En este ejercicio, se implementa una pila de 30 elementos con una restricción en el tamaño máximo de los contenedores (arreglos) a 10 elementos.

Definición de la Estructura

  
    Constante
      MAX = 10
    Tipo
      t_pila = Registro
        Contenedor1: array[1..MAX] de tipo_dato
        Contenedor2: array[1..MAX] de tipo_dato
        Contenedor3: array[1..MAX] de tipo_dato
        tope: entero
      Fin Registro
    Var
      pila: t_pila

Procedimiento Inicializar_Pila

Inicializa la pila estableciendo el tope en 0.

  
    Procedimiento Inicializar_Pila (Var pila: t_pila)
    Inicio
      pila.tope <- 0
    Fin

Función Pila_Vacia

Verifica si la pila está vacía.

  
    Función Pila_Vacia (pila: t_pila): lógico
    Inicio
      Pila_Vacia <- (pila.tope = 0)
    Fin

Función Pila_Llena

Verifica si la pila está llena.

  
    Función Pila_Llena (pila: t_pila): lógico
    Inicio
      Pila_Llena <- (pila.tope = 3 * MAX)
    Fin

Procedimiento Cargar_Pila

Agrega un elemento a la pila, distribuyéndolo en los contenedores según sea necesario.

  
    Procedimiento Cargar_Pila (Var Pila: t_pila, nuevo: tipo_dato)
    Inicio
      Si No(Pila_Llena(pila)) entonces
        Si pila.tope < MAX entonces
          pila.tope <- pila.tope + 1
          pila.Contenedor1[pila.tope] <- nuevo
        Sino
          Si pila.tope >= MAX y pila.tope < (2 * MAX) entonces
            pila.tope <- pila.tope + 1
            pila.Contenedor2[pila.tope - MAX] <- nuevo
          Sino
            pila.tope <- pila.tope + 1
            pila.Contenedor3[pila.tope - (2 * MAX)] <- nuevo
          Fin si
        Fin si
      Sino
        Escribir "Pila llena"
      Fin si
    Fin

Ejercicio 3: Implementación de Dos Pilas en un Mismo Vector

En este ejercicio, se implementan dos pilas en un mismo vector de 20 elementos. La primera pila almacena elementos desde la posición inicial hacia la última, y la segunda pila almacena datos desde la última posición hacia la primera.

Definición de la Estructura

  
    Constante
      MAX = 20
    Tipo
      t_pila = Registro
        dato: array[1..MAX] de tipo_dato
        tope1: entero
        tope2: entero
      Fin Registro
    Var
      pila: t_pila

Procedimiento Inicializar_Pila

Inicializa las dos pilas estableciendo los topes en los extremos opuestos del vector.

  
    Procedimiento Inicializar_Pila (Var pila: t_pila)
    Inicio
      pila.tope1 <- 0
      pila.tope2 <- MAX
    Fin

Función Pila_Vacia

Verifica si la pila seleccionada está vacía.

  
    Función Pila_Vacia (pila: t_pila, opcion: entero): lógico
    Inicio
      Según opcion hacer
        1: Pila_Vacia <- (pila.tope1 = 0)
        2: Pila_Vacia <- (pila.tope2 = MAX)
      Fin según
    Fin

Procedimiento Sacar

Saca un elemento de la pila seleccionada si no está vacía.

  
    Procedimiento Sacar (Var pila: t_pila, opcion: entero)
    Inicio
      Si NO(Pila_Vacia(pila, opcion)) entonces
        Según opcion hacer
          1: pila.tope1 <- pila.tope1 - 1
          2: pila.tope2 <- pila.tope2 + 1
        Fin según
      Sino
        Escribir "Pila vacía"
      Fin si
    Fin

Procedimiento Cargar

Agrega un elemento a la pila seleccionada si no está llena.

  
    Procedimiento Cargar (Var pila: t_pila, nuevo: tipo_dato, opcion: entero)
    Inicio
      Si No(Pila_Llena(pila)) entonces
        Según opcion hacer
          1: pila.tope1 <- pila.tope1 + 1
             pila.Dato[pila.tope1] <- nuevo
          2: pila.tope2 <- pila.tope2 - 1
             pila.dato[pila.tope2] <- nuevo
        Fin según
      Sino
        Escribir "Pila llena"
      Fin si
    Fin

Función Pila_Llena

Verifica si el vector está lleno, lo que indica que ambas pilas no pueden crecer más.

  
    Función Pila_Llena (pila: t_pila): lógico
    Inicio
      Pila_Llena <- ((pila.tope1 + 1) = pila.tope2)
    Fin

Ejercicio 4: Conversión y Resolución de Expresiones Infijas a Postfijas

En este ejercicio, se implementan funciones para convertir una expresión infija a postfija y resolver una expresión postfija.

Función Infija_A_Postfija

Convierte una expresión infija a postfija utilizando una pila para los operadores.

  
    Const
      MAX = 10
    Tipo
      t_cadena = array[1..MAX] de caracter
      t_pila = Registro
        contenedor: array[1..MAX] de caracter
        tope: entero
      Fin Registro
    Var
      infija: t_cadena

    Función Infija_A_Postfija (Infija: t_cadena): cadena
    Var
      i: entero
      Postfija: cadena
      pilaOperador: t_pila
      operando: Conjunto("0", "1", .. "9")
    Inicio
      i <- 1
      Mientras i <= Longitud(infija) hacer
        Si infija[i] in conjunto entonces
          Postfija <- Postfija + infija[i]
        Sino
          Si Pila_Vacia(pilaOperador) entonces
            Cargar(pilaOperador, Infija[i])
          Sino
            Mientras Prioridad(Consulta_Cima(pilaOperador)) >= Prioridad(infija[i]) y NO(Pila_Vacia(PilaOperador)) hacer
              Postfija <- Postfija + Sacar(pilaOperador)
            Fin mientras
            Cargar(pilaOperador, infija[i])
          Fin si
        Fin si
        i <- i + 1
      Fin mientras
      Mientras No(Pila_Vacia(PilaOperador)) hacer
        Postfija <- Postfija + Sacar(pilaOperador)
      Fin mientras
      Infija_A_Postfija <- Postfija
    Fin

Función Prioridad

Define la prioridad de los operadores.

  
    Función Prioridad (operador: caracter): entero
    Inicio
      Según operador hacer
        "*": Prioridad <- 2
        "/": Prioridad <- 2
        "+": Prioridad <- 1
        "-": Prioridad <- 1
      Fin según
    Fin

Función Resolver_Postfija

Resuelve una expresión postfija utilizando una pila para los operandos.

  
    Función Resolver_Postfija (postfija: tipo_cadena): real
    Var
      pilaOperando: t_pila
      operando: Conjunto("0", "1", .. "9")
      i: entero
      operando1, operando2, resultado: real
    Inicio
      i <- 1
      Mientras i <= Longitud(postfija) hacer
        Si postfija[i] in conjunto entonces
          Cargar(pilaOperando, Postfija[i])
        Sino
          operando2 <- Sacar(pilaOperando)
          operando1 <- Sacar(pilaOperando)
          resultado <- Calculo(postfija[i], operando1, operando2)
          Cargar(pilaOperando, resultado)
        Fin si
        i <- i + 1
      Fin mientras
      Resolver_Postfija <- Sacar(pilaOperando)
    Fin

Función Calculo

Realiza el cálculo entre dos operandos según el operador dado.

  
    Función Calculo(operador: caracter, op1, op2: real): real
    Inicio
      Según operador hacer
        "*": Calculo <- op1 * op2
        "/": Calculo <- op1 / op2
        "+": Calculo <- op1 + op2
        "-": Calculo <- op1 - op2
      Fin según
    Fin

Descargar

PDF Word HTML

Preguntas frecuentes

¿Qué es una pila en programación?

Una pila es una estructura de datos en la que los elementos se agregan y se retiran por el mismo extremo, siguiendo el orden último en entrar, primero en salir. Las operaciones principales son cargar y sacar elementos.

¿Cómo se convierte una expresión infija a postfija con una pila?

Los operandos se pasan directamente a la salida y los operadores se guardan en una pila. Antes de apilar un operador, se sacan de la pila los operadores de igual o mayor prioridad, y al final se vacía la pila en la salida.

Ponte a prueba

Tarjetas de repaso

Pulsa una tarjeta para ver la respuesta.

Test

1. ¿Qué orden de acceso sigue una pila?
2. En el ejercicio de dos pilas en un mismo vector, ¿cuándo está lleno el vector?
3. ¿Qué prioridad tiene el operador * en la función Prioridad?
4. ¿Qué hace Resolver_Postfija cuando encuentra un operador?
5. En la pila de tamaño restringido, ¿cuál es la capacidad total según Pila_Llena?
6. ¿Qué se devuelve al consultar una pila vacía con Consultar_Pila?

Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.