Colas Dobles y Circulares

Universidad de Estudios Superiores de La Paz
Carrera: Licenciatura en Informática
Asignatura: Estructura de datos
Tema: Colas circulares y dobles

Nombre del alumno: Hernández Mejía Brayan Alfredo
Grupo: LI-131
Fecha de entrega: Viernes 5 de noviembre del 2010

Colas circulares:
Una cola circular o anillo es una estructura de datos en la que los elementos están
de forma circular y cada elemento tiene un sucesor y un predecesor. Los
elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza
del anillo que es una posición distinguida. Existen dos operaciones de rotaciones,
una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento
sucesor, o el predecesor, respectivamente, de la cabeza actual.
Las colas lineales 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:
Ejemplos:
2
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
Este tipo de cola no tiene mucha diferencia a la cola doble, lo único que tiene de
diferente es que las conexiones en los apuntadores internos "prev" y "next" nunca
apuntan a nulo, solo cuando no existe ningún valor en la pila, sino, es como o
veremos a continuación:
Y su código seria:
Para el primer valor y la cola vacia:
Para el resto de los valores que entren con la cola con mas de una valor;
ALGORITMO DE INICIALIZACIÓN
F < -- 0
A<-- 0
ALGORITMO PARA 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 PARA 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 (Bicola):
La bicola o doble cola es un tipo de cola especial que permiten la inserción y
eliminación de elementos de ambos extremos de la cola.
La doble cola ó bicola es una cola bidimensional en la que las inserciones y

eliminaciones se pueden realizar en cualquiera de los dos extremos de la lista
pero no por la mitad.
Una bicola es un conjunto de elementos al que se pueden añadir o quitar

elementos en cualquier extremo del mismo. Se puede decir que es una cola
bidireccional. Si a los dos extremos de una bicola los llamamos izquierdo y
derecho respectivamente. Las operaciones básicas que definen una bicola son:
VaciaBi. Inicializa una bicola sin elementos.

EsVaciaBi. Devuelve (verdad) si la bicola no tiene elementos
AñadeBiP. Añade un elemento por el extremo izquierdo.
AñadeBiF. Añade un elemento por el extremo derecho.
PrimeroBiP. Devuelve el elemento izquierdo.
PrimeroBiF. Devuelve el elemento derecho.
BorrarBiP. Retira el elemento izquierdo de la bicola.
BorrarBiF. Retira el elemento derecho de la bicola.
Para representar una bicola se puede elegir una representación estática, con
arrays, o una representación dinámica con punteros.
Es posible establecer restricciones en una bicola con respecto al tipo de entrada o

el tipo de salida. Una bicola con entrada restringida es aquella que solo permite
inserciones por uno de los extremos pero acepta las eliminaciones por los dos
extremos. Una bicola con restricción en la salida es aquella que permite
inserciones por los dos extremos, pero solo permite retirar elementos por uno de
ellos.
Puede representarse a partir de un vector y dos índices, siendo su representación

más frecuente una lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.
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:
Ejemplos
Existen dos variantes de la doble cola:
 Doble cola de entrada restringida.

 Doble cola de salida restringida.
La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta

eliminaciones sólo al frente de la cola
Esta se trata de que cada valor tenga doble conexión o dos apuntadores internos
"next" y "prev", que ayudara a este valor a tener comunicación con el valor que
entro antes que el y el valor que entro después que el.
Variantes de las Bicolas
Existen dos variantes de la doble cola:
Doble cola de entrada restringida.-

Este tipo de doble cola acepta solamente la inserción de elementos por un
extremo; mientras que puede eliminar por ambos.
Doble cola de salida restringida.-

Este tipo de doble cola acepta solamente la eliminación de elementos por un
extremo; mientras que puede insertar por ambos.

Y se lleva acabo de la misma manera en la acción in pero agregando el apuntador

interno "prev", puedes comparar con el código que se ve a continuación:
Cuando se trata del primer valor y la cola está vacía:
Cuando se trata de más de un valor:
ALGORITMOS DE ENTRADA RESTRINGIDA
Algoritmo 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
Especificación de colas dobles en java

// ArrayCircularQueue.java
package com.javajeff.cds;
public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object [] queue;
public ArrayCircularQueue (int maxElements) {

queue = new Object [maxElements];
}
public void insert (Object o) {

int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear) {
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}
public boolean isEmpty () {

return front == rear;
}
public boolean isFull () {

return ((rear + 1) % queue.length) == front;
}
public Object remove () {

if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}
Bibliografía:
http://es.wikipedia.org/wiki/Colas_circulares_(anillos)
http://es.wikipedia.org/wiki/Bicola
http://sistemas.itlp.edu.mx/tutoriales/estru1/24.htm
http://sistemas.itlp.edu.mx/tutoriales/estru1/25.htm
http://www.monografias.com/trabajos32/estructura-de-datos/estructura-de-
datos.shtml#cola
http://www.conclase.net/c/edd/index.php?cap=000#inicio

Colas Dobles y Circulares

Cargado por

Copyright:

Formatos disponibles

Colas Dobles y Circulares

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Colas Dobles y Circulares

Cargado por

Copyright:

Formatos disponibles

Universidad de Estudios Superiores de La Paz

Carrera: Licenciatura en Informática

Asignatura: Estructura de datos

Tema: Colas circulares y dobles

Nombre del alumno: Hernández Mejía Brayan Alfredo

Fecha de entrega: Viernes 5 de noviembre del 2010

Para solucionar el problema de desperdicio de memoria se implementaron las

La representación gráfica de esta estructura es la siguiente:

Over flow, cuando se realice una inserción.

Under flow, cuando se requiera de una extracción en la cola.

Para el primer valor y la cola vacia:

ALGORITMO PARA INSERTAR

Si (F+1=A) ó (F=1 y A=máximo) entonces

ALGORITMO PARA EXTRAER

La doble cola ó bicola es una cola bidimensional en la que las inserciones y

Una bicola es un conjunto de elementos al que se pueden añadir o quitar

VaciaBi. Inicializa una bicola sin elementos.

Es posible establecer restricciones en una bicola con respecto al tipo de entrada o

Puede representarse a partir de un vector y dos índices, siendo su representación

Todas las operaciones de este tipo de datos tienen coste constante.

Esta estructura es una cola bidimensional en que las inserciones y eliminaciones

Existen dos variantes de la doble cola:

 Doble cola de entrada restringida.

La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta

Variantes de las Bicolas

Existen dos variantes de la doble cola:

Doble cola de entrada restringida.-

Doble cola de salida restringida.-

Y se lleva acabo de la misma manera en la acción in pero agregando el apuntador

Cuando se trata de más de un valor:

ALGORITMOS DE ENTRADA RESTRINGIDA

Algoritmo para Insertar

Algoritmo para Extraer

ALGORITMOS DE SALIDA RESTRINGIDA

Algoritmo para Insertar

Algoritmo para Extraer

Especificación de colas dobles en java

public ArrayCircularQueue (int maxElements) {

public void insert (Object o) {

public boolean isEmpty () {

public boolean isFull () {

public Object remove () {

También podría gustarte