Pilas y Colas

Lic. Alfredo Enrique Zelaya Mejía
Contador y Auditor
Visite la pagina web aqui




Pilas y Colas

• son estructuras de datos lineales
• tienen restricciones en cuanto a la insercion y eliminacion de componentes

Pilas

• se pueden insertar o eliminar elementos unicamente por uno de los dos extremos.
• los elementos son eliminados en orden inverso al que se insertaron
• es una estrutura tipo UEPS
• son estructura de datos lineales, como arreglos, donde los componentes ocupan lugares sucesivos
• es una coleccion de datos a los cuales se pueden acceder mediante un extremo o tope
• para la representacion de las pilas se hace uso de estructuras de datos tales como arreglos o listas
• las operaciones basicas de pilas son insertar o "Push" y eliminar "Pop", y las operaciones auxliares son "Pila_Llena" y "Pila_Vacía".
• las pilas tienen un valor maximo o "MAX" y un "TOPE".
• este es el algoritmo de una pila vacía:

           // Verifica si no hay elementos almacenados en la pila

          ┌ Si (TOPE=0) entonces 

                   Hacer BAND = Verdadero

              sino

                   // La pila esta vacia

                   Hacer BAND = Falso

                   // La pila no esta vacia

          └ Fin Si

• Este es el algoritmo para verificar si una pila esta llena

         ┌ Si (TOPE=MAX) entonces 

             // la pila esta llena

                  Hacer BAND = Verdadero

             sino

             // La pila esta vacia

                  Hacer BAND = Falso

             // La pila no esta llena

         └ Fin Si

• Este es el algoritmo para insertar un dato en una pila

              // Se llaman a la Pila_Llena

          ┌ Si (BAND = Verdadero) entonces

                   Escribir "Pila llena = Desbordamiento"

              sino

              // Entonces adiciona un elemento e ingresa el dato en el nuevo elemento

                  Hacer TOPE = TOPE + 1

                  Hacer PILA[TOPE] = DATO

          └ Fin Si

• Este es el algoritmo para quitar un dato en una pila

          // Se llaman a la Pila_Vacia

          ┌ Si (BAND = Verdadero) entonces

                   Escribir "Pila vacia = Subdesbordamiento"

              sino

              // Entonces elimina un elemento

                   Hacer DATO = PILA[TOPE]

                   Hacer TOPE = TOPE -1

          └ Fin Si

• La clase pila esta compuesta de la siguiente manera:

Pila	<-----Nombre de la clase
TOPE = entero DATOS = ARREGLO[1...MAX]	<-----Atributos
Pila_vacía() Pila_llena() Pone(argumento) Quita(argumento)	<---- Metodos

Colas

• es una estructura lineal de datos
• los datos se introducen en un extremo y se eliminan del otro
• los componentes se eliminan en el mismo orden en el cual se insertaron
• son estructuras tipo PEPS
• para la representacion de las colas se hace uso de estructuras de datos tales como arreglos o listas
• las operaciones con colas son insertar o eliminar
• se insertan datos al FINAL de la cola y se elimia en el FRENTE de la cola
• este es el algoritmo para insertar un dato en una cola:

          // Verifica si hay espacion libre 

          ┌ Si (FINAL <  MAX) entonces

                   // Actualiza el FINAL e ingresa el dato en el agregado

                   Hacer FINAL = FINAL + 1
                   Hacer COLA[FINAL] = DATO
                  ┌ Si (FINAL = 1) entonces // se inserto el primer elemento de COLA
                            Hacer FRENTE = 1
                  └ Fin Si
              Sino
                   Escribir "Desboramiento - Cola llena"  

          └ Fin si

• este es el algoritmo para eliminar un dato en una cola:

          // Verifica si la cola esta vacia

          ┌ Si (FRENTE < >  0) entonces

                   // Capta la posicion

                   Hacer DATO = COLA[FRENTE]
                   ┌ Si (FRENTE = FINAL) entonces
                            Hacer FRENTE = 0
                            Hacer FINAL = 0 // indica COLA vacia
                       Sino
                            Hacer FRENTE = FRENTE + 1
                   └ Fin Si
              Sino
                   Escribir "Subdesboramiento - Cola vacia"

          └ Fin si

• este es el algoritmo para ver si la cola esta vacia

          ┌ Si (FRENTE =  0) entonces

                   Hacer BAND = Verdadero

              Sino

                   Hacer BAND = Falso

          └ Fin si

• este es el algoritmo para ver si la cola esta llena

          ┌ Si (FINAL =  MAX) entonces

                   Hacer BAND = Verdadero

              Sino

                   Hacer BAND = Falso

          └ Fin si

• La clase pila esta compuesta de la siguiente manera:

Cola	<-----Nombre de la clase
FRENTE = entero FINAL = entero DATOS = ARREGLO[1...MAX]	<-----Atributos
Cola_vacía() Cola_llena() Insertar_cola(argumento) Eliminar_cola(argumento)	<---- Metodos

Colas Circulares

• estructura de dato lineal
• el siguiente elemento del ultimo es el primero
• este es el algoritmo para insertar en una cola circular

          ┌ Si ((FINAL = MAX) y (FRENTE = 1)) o ((FINAL +1) = FRENTE) entonces

                   Escribir "Desbordamiento - Cola llena"

              Sino

                   ┌ Si (FINAL = MAX) entonces

                            Hacer FINAL = 1

                       Sino

                            Hacer FINAL = FINAL + 1

                  └ Fin Si

                   Hacer COLACIR[FINAL] = DATO

                  ┌ Si (FRENTE = 0) entonces

                           Hacer FRENTE = 1

                  └ Fin Si

          └ Fin Si

• este es el algoritmo para eliminar un registro en una cola circular

          ┌ Si (FRENTE = 0) entonces

                   Escribir "Subdesbordamiento - Cola Vacia"

              Sino

                    Hacer DATO = COLACIR[FRENTE]

                   ┌ Si (FINAL = FINAL) entonces // si hay solo un elemento

                            Hacer FRENTE = 0 y FINAL = 0

                       Sino

                           ┌ Si (FRENTE = MAX)

                                    Hacer FRENTE = 1

                               Sino

                                    Hacer FRENTE = FRENTE + 1

                           └ Fin Si

                  └ Fin Si

          └ Fin Si


Colas Dobles

• generalizacion de una estructrua de datos tipo cola.
• los elementos se insertan y se eliminan por cualquiera de los extremos
• las variantes son: a) doble cola con entrada restringida, b) doble cola con salida restringida