martes, 14 de febrero de 2012

Pilas y Colas


PILAS

Para los próximos algoritmos se cuenta con la siguiente estructura de datos

Const MAX = 100
Pila = arreglo[1..MAX] de enteros

PONER EN UNA PILA
Algoritmo que inserta el elemento DATO en la pila. TOPE marca el tope de elementos, MAX posee el tamaño de la pila
Push(PILA, MAX, TOPE,DATO)
Inicio
            Si (TOPE < MAX) entonces   /* verifica que haya espacio */
                        TOPE ß TOPE +1
                        PILA[TOPE] ß DATO
            Sino
                        Imprimir(“Subdesbordamiento”)
            Fin si
Fin

QUITAR DE UNA PILA
Algoritmo que saca el ùltimo elemento de una PILA, y lo guarda en Dato, TOPE guarda el tope de elementos de la pila.
Pop(PILA, TOPE, DATO)
Inicio
            Si (TOPE > 0) entonces                      /* verifica que la pila no este vacia */
                        DATO ß PILA[TOPE]
                        TOPE ß TOPE -1
            Sino
                        Imprimir(“Subdesbordamiento”)
            Fin si
Fin

CONVERSION POSTFIJA
Traducir una expresión infija EI a postfija EPOS, utilizando una pila.
Inapos(EI, EPOS)
Inicio
            Declarar Tope: entero
            Declarar símbolo: caracter
            Tope ß 0
            Mientras (EI<>vacio) haga
                        Símbolo ß izquierda(EI,1,1)  /* función que devuelve un número de caracteres a la izquierda de una cadena */
                        EI ß derecha(EI,2,largo(EI)) /* derecha devuelve un numero de caracteres a la derecha de una cadena, largo, devuelve la longitud de una cadena */
                        Selecciones símbolo
                        Caso “(“:          Tope ß Tope +1
                                               Pila[Tope] ß simbolo
                        Caso “)“:          Mientras Que (Pila[Tope] <> “)” ) haga
                                                           Concatenar(EPOS, Pila[Tope])
                                                           /* Concatenar dos cadenas */
                                                           Tope ß Tope -1
                                               Fin MQ
                      /* Se quita el paréntesis izquierdo de la pila y no se agrega a EPOS */
                                               Pila[Tope] ß “”
                                               Tope ß Tope – 1
                        Caso “A”,”B”,”C”,…,”Y”,”Z”:        /* El símbolo es un operando */
                                               Concatenar (EPOS, símbolo)
                        Caso “^”, “*”,”/”,”+”,”-“:  /* el símbolo es un operador */
                                   Mientras Que (Tope > 0 ) y
                                   (Prioridad(símbolo) <= prioridad(Pila(Tope)) haga
                                               Concatenar(EPOS, Pila[Tope])
                                               Tope ß Tope -1
                                   Fin MQ
                                   Tope ß Tope +1
                                   Pila[Tope] ß símbolo
                        Fin Seleccione
            Fin MQ
            Mientras Que (Tope>0) haga
                        Concatenar(EPOS,Pila[Tope])
                        Tope ß Tope -1
            Fin MQ
            Imprimir EPOS
Fin

COLAS

Para los próximos algoritmos se cuenta con la siguiente estructura de datos

Const MAX = 100
COLA = arreglo[1..MAX] de enteros

INSERTAR EN UNA COLA
Algoritmo que inserta el elemento DATO al final de la COLA. FRENTE y FINAL marcan el inicio y fin de la cola. MAX es el tamaño de la COLA
Insertacola(COLA, MAX, FRENTE, FINAL,DATO)
Inicio
            Si (FINAL < MAX) entonces  /* Verificar espacio libre */
                        FINAL ß FINAL +1
                        COLA[FINAL] ß DATO
                        Si (FINAL = 1) ENTONCES
                                   FRENTE ß 1
                        Fin si
            Sino
                        Imprimir(“Desbordamiento”)
            Fin si   
Fin

ELIMINAR EN UNA COLA
Algoritmo que elimina el primar elemento de la cola y lo almacena en DATO
Eliminacola(COLA, FRENTE,FINAL,DATO)
Inicio
            Si (FRENTE <> 0) entonces              /* verificar que la cola no este vacia */
                        DATO ß COLA[FRENTE]
                        Si (FRENTE = FINAL) entonces  /* hay un solo elemento */
                                   FRENTE ß 0
                                   FINAL ß 0
                        Sino
                                   FRENTE ß FRENTE +1
                        Fin si
            Sino
                        Imprimir(“Subdesbordamiento”)
            Fin si
Fin

MANEJO DE COLAS CIRCULARES
INSERTAR EN UNA COLA CIRCULAR
Algoritmo que sirve para insertar un dato DATO en una cola Circular COLACIR con MAX elementos y los marcadores de FRENTE y FINAL.
Insertacircular(COLACIR, MAX, FRENTE, FINAL, DATO)
Inicio
            Si ((FINAL=MAX) Y (FRENTE=1)) o ((FINAL+1)= FRENTE) entonces
                        Imprimir (“Desbordamiento”)   /* Cola Llena */
            Sino
                        Si (FINAL = MAX) entonces
                                   FINAL ß 1
                        Sino
                                   FINAL ß FINAL +1
                        Fin si
                        COLACIR[FINAL] ß DATO
                        Si (FRENTE = 0) entonces
                                   FRENTE ß 1
                        Fin si
            Fin si
Fin

ELIMINAR EN UNA COLA CIRCULAR
Algoritmo que elimina el primer elemento de una cola circular COLACIR y lo almacena en DATO. FRENTE Y FINAL marcan el inicio y fin de la cola. La cola tiene un tamaño de MAX elementos.
Elminacircular(COLACIR, MAX, FRENTE, FINAL, DATO)
Inicio
            Si (FRENTE = 0) entonces                 /* verifica si la cola esta vacía */
                        Imprimir(“Subdesbordamiento”)
            Sino
                        DATO ß COLACIR[FRENTE]
                        Si (FRENTE = FINAL) entonces  /* solo hay un elemento */
                                   FRENTE ß 0
                                   FINAL ß 0
                        Sino
                                   Si (FRENTE = MAX) entonces
                                               FRENTE ß 1
                                   Sino
                                               FRENTE ß FRENTE +1
                                   Fin si
                        Fin si
            Fin si
Fin

No hay comentarios:

Publicar un comentario en la entrada