COLAS CIRCULARES Y DOBLES

Cola Circular: Represntación lógica de una cola simple en un arreglo.
Estas tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador A sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).
Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola.
La representación gráfica de esta estructura es la siguiente:

La condición de vacío en este tipo de cola es que el apuntador F sea igual a cero.
Las condiciones que debemos tener presentes al trabajar con este tipo de estructura son las siguientes:

• Over flow, cuando se realice una inserción.
• Under flow, cuando se requiera de una extracción en la cola.
• Vacio

***Algoritmo de inicialización:
F<=0
A<=0
***Algoritmo de insertar:
Si (F+1=A) ó (F=1 y A=máximo) entonces
        mensaje (overflow)
en caso contrario
        inicio
si A=máximo entonces
        A<=1
        cola[A]<= valor
en caso contrario
        A <=A+1
         cola[A]<=valor
si F=0 entonces
         F <=1
         fin
***Algoritmo a extraer:Si F=0 entonces
        mensaje (underflow)
en caso contrario
        x <= cola[F]
         si F=A entonces
F <= 0
A<= 0
         en caso contrario
si F=máximo entonces
        F <=1 en caso contrario F <= F+1



Colas Dobles (Bicolas): Estructura lineal en la que los elementos se pueden añadir o quitar por cualquier extremo  de la cola (cola bidireccional).
Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera:

Existen dos variantes de la doble cola:

• Doble cola de entrada restringida: sólo acepta inserciones al final de la cola
• Doble cola de salida restringida: acepta eliminaciones sólo al frente de la cola

**Algoritmos de entrada restringida**
***Algoritmos de inicialización:
f<=1
A<=0
***Algoritmo para insertar:
Si A=máximo entonces
         mensaje (overflow)
en caso contrario
         A <=A+1
         cola[A]<= valor
***Algoritmo para extraer:
Si F&gtA entonces
         mensaje (underflow)
en caso contrario
         mensaje (frente/atrás)
si frente entonces
       x <=cola[F]
       F <= F+1
en caso contrario
       x <= cola[A]
       A <=A-1
**Algoritmos de salida restringida**
***Algoritmo de inicialización:
f<=1
A<=0
**Algoritmo para insertar:
Si F&gtA entonces
         mensaje (overflow)
en caso contrario
         mensaje (Frente/Atrás)
          si Frente entonces
cola[F] <=valor
          en caso contrario
A <= A+1
cola[A] <=valor

***Algoritmo para extraer:
Si F=0 entonces
         mensaje (underflow)
en caso contrario
         x <=cola[F]
         F <= F+1

LABERINTO (PROGRAMA)

El laberinto se implementa como un arreglo de caracteres bidimensionales en el cual los pasajes se marcan con 0, las paredes con 1, la posición de salida con la letra e y la posición inicial del ratón con la letra m.

En este programa , el laberinto permite la salida esté en cualquier posición del laberinto  y permitir que los pasajes estén en los bordes. Para protegerse a sí mismo de deslizarse fuera del arreglo al tratar de continuar su ruta cuando llega a una celda abierta en uno de los bordes, el ratón también debe verificar constantemente si está en posición de borde o no.

El programa utiliza pone de manera automática un marco de 1 alrededor del laberinto introducido por el usuario.

El programa utiliza 2 pilas:

*Una pila para inicializar el laberinto.

*La segunda para implementar el retroceso.

El usuario introduce un laberinto, una línea a la vez puede tener cualquier número de filas y cualquier número de columnas.

El programa hace que todas las filas tienen la misma longitud y utiliza solo estos caracteres:

Cualquier número 1, cualquier número de 0, una e, y una m.

Las filas se insertan en la pila mazeRows en el orden en que se introducen después de añadir un 1 al principio y un 1 final.

Después de que todas se introducen, puede determinarse el tamaño del arreglo almacenado.

Las filas de la pila se transfieren al arreglo. La segunda pila mazeStack, utiliza el proceso de escapar del   laberinto con el propósito de recordar rutas no probadas para intentos subsecuentes.

Se almacena en una pila y siempre en un mismo orden el primer vecino superior, luego el inferior después a  la  izquierda y finalmente a la derecha.

Después de insertar las vías abiertas de la pila el ratón toma la posición superior y así sucesivamente hasta que llega a la salida agotando las posibilidades para evitar caer en un ciclo infinito de ruta de prueba visitada de laberinto se marca con un punto.

La pila almacena coordenadas de las posiciones de la celda utiliza dos pilas de enteros para las coordenadas  x, y. Otra forma de utilizar una pila de enteros con dos coordenadas almacenadas  con la ayuda de operación de desplazamiento con dos campos de datos x, y de modo que se usa mazeStack para almacenar los objetos MazeCell.

El programa imprime el laberinto después de que el ratón da cada paso.

DIAGRAMA DE FLUJO

PILAS

Definición  Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese estremos se llama ``la parte superior'' de la pila.

Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 9 el elemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.

De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debedos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo.

Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como:

Retira de la pila hasta que el elemento retirado sea C.

Ni siquiera es necesario decir: ``Retira un elemento de la pila...'' porque es sobreentendido que solamente se puede sacar un elemento a la vez.

                                                   

EJEMPLOS

Pila con 6 elementos

Operación de retirar de la pila P