Una cola doble es una estructuras en donde cada elemento puede ser insertado y
recuperado por la parte del frente (cabeza) o por la parte de atras (cola) de la
lista. A diferencia de una cola sencilla, en donde solo se necesitan un método para
leer y otro para escribir componentes en la lista, en una doble cola debe haber dos
métodos para leer ( uno para leer por el frente y uno para leer por atras ) y dos
métodos para escribir ( uno para escribir por el frente y uno para escribir por atras ).
En el programa que se verá en seguida, se simula el comportamiento de una estructura de cola doble en base a un arreglo estático. En dicho programa se declara e implementa la clase SDQueue con los siguientes métodos:
put_front(), poner un elemento en el frente de la cola
put_back(), poner un elemento en la parte tracera de la cola
get_front(), retirar un elemento de la parte frontal de la cola
get_back(), retirar un elemento de la parte tracera de la cola
empty(), regresa 1 (TRUE) si la cola est vacia
size(), número de elementos en la cola
Nota: observe que para los métodos put_front() y get_front() se hace uso de la función memmove(), esto es necesario debido al hecho de que put_front() tiene que mover una posición hacia atras todos los elementos en la lista antes de insertar el componente indicado; por otro lado, la función get_front() tiene que mover una posición hacia adelante a todos los elementos que le siguen al primer elemento.
Ejemplo: doble cola en un arreglo estático
/*------------------------------------------------------------------+
+ ejemplo de una cola doble (DQUEUE) basada en un arreglo est tico +
+ +
+ Autor: Oscar E. Palacios +
+ email: oscarpalacios1@yahoo.com.mx +
+ +
+ Manifiesto: +
+ Este programa puede distribuirse, copiarse y modificarse de +
+ forma libre. +
+------------------------------------------------------------------*/
#include <iostream.h>
#include <mem.h> // por memmove
// using namespace std;
#define MAX_SIZE 256
#define t_error -1;
typedefint DATA_TYPE;// máximo número de elementos
typedefint almacen[MAX_SIZE];
class SDQueue {
// atributos
int itemsize;// tamaño de cada elemento
int items;// número de elementos
int cola, cabeza;// punteros de lectura y escritura
almacen alma;// el almacen o arreglo
public:
// constructor
SDQueue(): cola(0), cabeza(0), items(0), itemsize(sizeof(DATA_TYPE)){}
// destructor
~SDQueue(){}
int empty(){return items ==0;}
int size(){return items;}
/* agregar componente en la parte tracera de la lista */
DATA_TYPE put_back(DATA_TYPE valor)
{
if(items == MAX_SIZE)return t_error;
alma[cola]= valor;
items++;
cola++;
return valor;
}
/* agregar componente en la parte delantera de la lista */
DATA_TYPE put_front(DATA_TYPE valor)
{
if(items == MAX_SIZE)return t_error;
memmove((void*)&alma[cabeza+1], (void*)&alma[cabeza], items*itemsize);
alma[cabeza]= valor;
items++;
cola++;
return valor;
}
/* retirar elemento de la parte frontal de la lista */
DATA_TYPE get_front()
{
DATA_TYPE d;
if( empty())return t_error;
items--;
cola--;
d =alma[cabeza];
memmove((void*)&alma[cabeza], (void*)&alma[cabeza+1], items*itemsize);
return d;
}
/* retirar elemento de la parte tracera de la lista */
DATA_TYPE get_back()
{
DATA_TYPE d;
if( empty())return t_error;
items--;
cola--;
d =alma[cola];
return d;
}
};// fin de la clase SDQueue
/* punto de prueba */
int main()
{
SDQueue s;
DATA_TYPE d;
for(d='A'; d<='Z'; d++) s.put_back(d);
while(! s.empty())
cout<<(char)s.get_front()<<" ";
cout<<"\nPara terminar presione <Enter>...";
cin.get();
return0;
}
Una cola doblemente encadenada es una estructuras en donde cada elemento puede ser insertado y recuperado por la parte del frente (cabeza) o por la parte de atras (cola) de la lista. A diferencia de una cola sencilla, en donde solo se necesita un puntero a un siguiente elemento, la estructura del nodo para una doble cola debe poseer un puntero a un posible siguiente elemento y un puntero a otro posible anterior elemento. Por ejemplo, para crear una estructura de nodo con doble enlace para coleccionar números enteros podemos usar la sintaxis:
struct nodo {
int data;
nodo *next, *prev;
};
Gráficamente podemos imaginar la estructura anterior como:
+------+------+------+
<--| prev | data | next |-->
+------+------+------+
En el programa que se verá en seguida, se simula el comportamiento de una estructura de cola de doble enlace. Para la implementación de la clase DDqueue en el programa se han elegido los métodos:
put_front(), poner un elemento en el frente de la cola
put_back(), poner un elemento en la parte tracera de la cola
get_front(), retirar un elemento de la parte frontal de la cola
get_back(), retirar un elemento de la parte tracera de la cola
empty(), regresa 1 (TRUE) si la cola est vacia
size(), n£mero de elementos en la cola
/*---------------------------------------------------------------+
+ ejemplo de una cola doblemente enlazada (Dqueue) basada en un +
+ arreglo dinámico +
+ +
+ Autor: Oscar E. Palacios +
+ email: oscarpalacios1@yahoo.com.mx +
+ +
+ Manifiesto: +
+ Este programa puede distribuirse, copiarse y modificarse de +
+ forma libre. +
+---------------------------------------------------------------*/
#include <iostream.h>
#include <conio.h>
// using namespace std;
typedefchar DATA_TYPE;
struct nodo {
DATA_TYPE data;
nodo*next, *prev;
};
class DDqueue {
int itemsize, items;
nodo*cola, *cabeza;
public:
// constructor
DDqueue(): cola(NULL), cabeza(NULL), items(0), itemsize(sizeof(DATA_TYPE)){}
// destructor
~DDqueue(){}
/* agregar componente en la parte tracera de la lista */
DATA_TYPE put_back(DATA_TYPE valor)
{
nodo*temp;
temp=new nodo;
if(temp ==NULL)return-1;
temp->data = valor;
items++;
if(cabeza ==NULL)
{
temp->next =NULL;
temp->prev =NULL;
cabeza= temp;
cola= temp;
}else
{
cola->next = temp;
temp->prev = cola;
cola= temp;
cola->next =NULL;
}
return valor;
}
/* agregar componente en la parte frontal de la lista */
DATA_TYPE put_front(DATA_TYPE valor)
{
nodo*temp;
temp=new nodo;
if(temp ==NULL)return-1;
temp->data = valor;
items++;
if(cabeza ==NULL)
{
temp->next =NULL;
temp->prev =NULL;
cabeza= temp;
cola= temp;
}else
{
cabeza->prev = temp;
temp->next = cabeza;
cabeza= temp;
cabeza->prev =NULL;
}
return valor;
}
// regresa true si la lista está vacia
int empty(){return items ==0;}
/* retirar elemento de la parte frontal lista */
DATA_TYPE get_front()
{
nodo*temp;
DATA_TYPE d;
if( empty())return-1;
items--;
d = cabeza->data;
temp= cabeza->next;
if(cabeza)delete cabeza;
cabeza= temp;
return d;
}
/* retirar elemento de la parte tracera de la lista */
DATA_TYPE get_back()
{
nodo*temp;
DATA_TYPE d;
if( empty())return-1;
items--;
d = cola->data;
temp= cola->prev;
if(cola)delete cola;
cola= temp;
return d;
}
};// fin de la clase DDqueue
/* punto de prueba */
int main()
{
clrscr();
DDqueue s;
DATA_TYPE d;
// insertando elementos en la parte tracera
for(d='A'; d<='Z'; d++) s.put_back(d);
// insertando en la parte delantera
for(d=9; d>=0; d--)s.put_front(d+'0');
// vaciando la lista
while(! s.empty())
cout<<(DATA_TYPE)s.get_front()<<" ";
cout<<"\nPara terminar presione <Enter>...";
cin.get();
return0;
}
Las Colas Dobles o DobleColas; ya no deben ser llamadas COLAS, porque ya no respetan el ser una estructura FIFO; es decir First In First Out; ya que al poder ingresar y eliminar elementos por un mismo
ResponderEliminarlado; ya sea el frente o el fina; esto provoca que un primero elemento entrado; no sea el primero en salir.
Saludos