COLA

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

UTILIZACIÓN

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

TIPOS DE COLAS

Colas circulares (anillos): en las que el último elemento y el primero están unidos.

Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

OPERACIONES BÁSICAS

Crear: se crea la cola vacía.

Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.

Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.

Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

COLAS EN PASCAL

  Clase PscColas, Matriz[]:Cadena, Posición, Valor:Entero

  Privado:

        Proc Comenzar

                ReDim Matriz,1

                Posición = 0

                Valor = 0

        FinProc

        Proc Terminar

                Borrar Matriz

        FinProc

        Proc Longitud:Entero

                Devolver Límite(Matriz)

        FinProc

        Proc ReDimencionarLaCola

                ReDim Preservar Matriz, LongMat(Matriz) + 1

        FinProc

  Público:

        Proc Encolar(Contenido:Cadena)

                Si Posición = LongMat(Matriz) Entonces ReDimencionarLaCola

                Matriz[Posición] = Contenido

                Posición = Posición + 1

        FinProc

        Proc DesEncolar

                Si Neg(Valor >= Límite(Matriz)) Entonces Valor = Valor + 1

        FinProc

        Proc FrenteCola:Cadena

                Devolver Matriz[Valor]

        FinProc

        Proc FondoCola:Cadena

                Devolver Matriz[Límite(Matriz)]

        FinProc

        Prop ColaLongitud:Entero

                Lec:Longitud

        FinProp

  Privado:

        Constructor: Comenzar

        Destructor: Terminar

  FinClase

Nodos

En programación concretamente en estructura de datos, un nodo es uno de los elementos deuna lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro quedispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia aotro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoríatener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para laconstrucción de estructuras de datos dinámicas.

3. DEFINICION DE CLASE CONFORMANDO NODO


class NodosLista // se define la clase Nodo{ Object datos; // Campo Información NodosLista siguiente; //Campo Nodo // datos: que almacena la información // siguiente : Apuntador o enlace a otros nodosNodosLista(Object valor) // Se define un nodo{ datos=valor; siguiente=null;}

4. Como la lista es una consecución de muchos nodos es necesario establecer nombre a losnodos y colocarlos a apuntar a algún sitio, en el caso del único nodo debe apuntar a NULL.En este caso se crea un nodo llamado P, indicando que es el primero de la lista.P =new NodosLista;Nota:Ojo en este caso no se están utilizando parámetros para la creación del nodo ni parainsertar información en los campos del nodo, a manera de ejemplo se mostrará el proceso deforma manual, pero la idea es parametrizar todos los métodos para la realización yoperaciones de la lista simple

5. Para acceder al nodo y escribir valores en sus campos es necesario identificar al Nodo, que eneste caso es P y colocar un punto para poder acceder a los campos del nodo, como se muestraa continuación.P.dato= 25;P.siguiente = Null;La representación grafica del Nodo queda de la siguiente forma:

6. CAMPO APUNTADOR DE UN NODOP ESTE ES EL NODO COMPLETOEsto quiere decir que un nodo debe tener alguna dirección de memoria asignada ¿Cuál? nosabemos, pero se puede saber si se hace referencia a P, cuando se hace referencia a P, seindica todo el nodo tanto el campo info como el campo apuntador.Si se define un nodo, el nodo creado contiene el campo información y el campo siguiente Nodo P y Nodo QCuando se coloca el nombre del nodo haciendo referencia a otro realmente se apunta al nodoindicado P= Q;Nota: Este caso se realiza cuando se desea crear un nodo auxiliar que permita realizar elrecorrido de la lista, como se ha indicado en repetidas ocasiones no se debe perder lareferencia al el primero de la lista.

7. Se puede hacer referencia o apuntar un puntero con el campo siguiente P.siguiente= Q; P.siguiente = Null; P.siguiente= P;

8. CAMBIO DE APUNTADOR EN LOS NODOSEn la siguiente figura Tenemos 2 nodos en la lista, como se había indicado el Nodo P indica elPrimero de la lista y el campo siguiente del nodo apunta al siguiente nodo, dicho nodo indicael final de la lista.Necesitamos otro nodo , dicho nodo se llamará QSi lo quisiéramos crear se recurre a la siguiente línea de códigoQ =new NodosLista;Ya sabemos que contiene los dos campos uno para la información y otro para el apuntadorEn este momento el nodo no contiene ni dirección ni información.Si quisiéramos colocarlo al inicio de la lista debemos indicarle al nodo que apunte a PQ.siguiente= P;

9. Si quisiéramos colocarlo después del primer elemento de la lista debemos indicarle al nodoque apunte a la dirección que corresponde a ese nodo ¿Quién la Sabe? Q.siguiente= P.siguiente;

10. RECORRIDO EN UNA LISTAComo se indico anteriormente no se puede perder la referencia al primernodo, por lo cual se crea un nodo auxiliar llamado Q para recorrer la lista.Q =new NodosLista;Luego el nodo Q se le asigna la misma dirección que corresponde al nodoPP=Q;Ser comienza el recorrido de la siguiente formaQ= Q.siguiente; a) Se apunta a P. b) Q en estos momentos encabeza la lista. c) Q= Q.siguiente notese que el campo siguiente de Q apunta al siguiente nodo d) Cada vez que se realiza esta instrucción estamos cambiando de posición en la lista, nos vamos desplazando hacia delante de ella, cumpliendo con la filosofía de la estructura los recorridos se hacen hacia adelante.

Listas enlazadas

Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:

class NodoLista

{

  Object elemento;

  NodoLista siguiente;

}

La referencia contenida en el nodo de una lista se denomina siguiente, pues indica en dónde se encuentra el siguiente elemento de la lista. El último elemento de la lista no tiene nodo siguiente, por lo que se dice que la referencia siguiente del último elemento es null (nula).

La siguiente figura muestra un ejemplo de una lista enlazada cuyos elementos son strings:

La referencia lista indica la posición del primer elemento de la lista y permite acceder a todos los elementos de ésta: basta con seguir las referencias al nodo siguiente para recorrer la lista.

NodoLista aux=lista;

aux=aux.siguiente;

Siguiendo con el ejemplo anterior, para insertar un nuevo nodo justo delante del nodo referenciado por auxse deben modificar las referencias siguiente del nodo aux y del nodo a insertar.

NodoLista nuevo=new NodoLista(...);

//"nuevo" es la referencia del nodo a insertar en la lista

nuevo.siguiente=aux.siguiente;

aux.siguiente=nuevo;

//Notese que no es lo mismo realizar los cambios de referencia

//en un orden distinto al presentado, puesto que en ese caso

//se "pierde" la lista desde el nodo siguiente a aux

El procedimiento presentado a continuación es un ejemplo de cómo se programa el recorrido de una lista enlazada. Se supondrá que los objetos almacenados en cada nodo son strings:

void recorrido(NodoLista lista)

{

  NodoLista aux=lista;

  while (aux!=null)

  {

    System.out.println(aux.elemento);

    aux=aux.siguiente;

  }

}

Para invertir el orden de la lista, es decir, que el último elemento de la lista ahora sea el primero, que el penúltimo elemento de la lista ahora sea el segundo, etc..., modificando sólo las referencias y no el contenido de los nodos, es necesario realizar una sola pasada por la lista, y en cada nodo visitado se modifica la referencia siguiente para que apunte al nodo anterior. Es necesario mantener referencias auxiliares para acordarse en donde se encuentra el nodo anterior y el resto de la lista que aún no ha sido modificada:

void invertir(NodoLista lista)

{

  NodoLista siguiente=lista;

  NodoLista anterior=null;

  while(lista!=null)

  {

    siguiente=lista.siguiente;

    lista.siguiente=anterior;

    anterior=lista;

    lista=siguiente;

  }

}

La implementación vista de los nodos también se conoce como lista de enlace simple, dado que sólo contiene una referencia al nodo siguiente y por lo tanto sólo puede recorrerse en un solo sentido. En unalista de doble enlace se agrega una segunda referencia al nodo previo, lo que permite recorrer la lista en ambos sentidos, y en general se implementa con una referencia al primer elemento y otra referencia al último elemento.

Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.

En muchas aplicaciones que utilizan listas enlazadas es útil contar con un nodo cabecera, tambien conocido como dummy o header, que es un nodo "falso", ya que no contiene información relevante, y su referencia siguiente apunta al primer elemento de la lista. Al utilizar un nodo cabecera siempre es posible definir un nodo previo a cualquier nodo de la lista, definiendo que el previo al primer elemento es la cabecera.

Si se utiliza un nodo cabecera en una lista de doble enlace ya no es necesario contar con las referenciasprimero y último, puesto que el nodo cabecera tiene ambas referencias: su referencia siguiente es el primer elemento de la lista, y su referencia anterior es el último elemento de la lista. De esta forma la lista de doble enlace queda circular de una manera natural.

Listas

Definición

Una lista es un conjunto ordenado de elementos homogéneos, en la que no hay restricciones de acceso, la introducción y borrado de elementos puede realizarse en cualquier posición de la misma. Esta es una estructura dinámica, por lo que no podemos saber con certeza los elementos (nodos) que puede contener, ya que su tamaño cambia a medida que se añaden y eliminan elementos de la misma.

Características

- Se accesa a toda la lista a partir de un apuntador externo llamado Lista contiene la dirección del primer nodo en la lista.

- Cada nodo tiene dos secciones: el contenido de datos (Info) y el campo del apuntador (sig).

- El campo Info (de información) contiene el elemento real en la lista.

 -El campo sig (dirección siguiente) contiene la dirección del siguiente nodo en la lista. Tal dirección se conoce como apuntador.

-El último nodo tiene un apuntador nulo.

-Cada nodo es una estructura de datos de tipo registro.

-Una lista vacía es aquella que no contiene nodos. Lista=NULL.

Operaciones básicas de una lista:

·         Recorrido de la lista: Visita todos los elementos de la lista.

Function largo (l: lista): integer;

Var

      Contador: integer;

      P: lista;

Begin

      Contador:=0;

      P:=l;

      While p <> vnil do

      Begin

           Contador:= contador + 1;

            P:=p .siguiente;         (Avanzar a la siguiente celda)

     End;

     Largo:=contador;

End;

·         Inserción de un elemento: Agrega un elemento a la lista.

Procedure agregar_al_principio (var l: Lista; elem: t);

Var p: Lista;

Begin

       New (p);                        (crear nueva celda)

       p. elemento:= elem;      (cargar el elemento)

       (Ajuste de punteros)

       p. siguiente:=L;

       L:=p;

End;

Procedure agregar_al_final (var L: Lista; elem: T);

Var p.q: Lista;

Begin

       New (p);                     (crear nueva celda)

       p.elemento:=elem;     (cargar el elemento)

       p. siguiente:= nil;       (es el ultimo)

       If l= nil then

           L:=p

       Else

       Begin

              (Buco el último de l)

              Q:=l;

              While q. siguiente <> nil do

                    Q:=q. siguiente;

             (Engancho p a continucion del último)

             q. siguiente:=p;

      End;

End;

·         Borrado de un elemento: Retira un elemento de la lista.

Procedure borrar_primero (var l: lista);

Var

       P: lista;

Begin

       P:=l;

       L:=l. siguiente;

       Dispose (p)

End;

Procedure borrar_lista (l: lista);

Var

      P: lista;

Begin

     While l <>nil do

     Begin

            P:= l;

            L:= l. siguiente;

            Dispose (p);

     End;

End;

·         Búsqueda de un elemento: Busca el elemento en la lista.

Function pertenece (elem: T; L Lista): boolean;

Var

      P: Lista;

Begin

      P:=L;

(Notar: evolución por circuito corto)

       Write (p <> nil) and (p. elemento <> elem) do

             P:= p. siguiente;

Pertenece:= (p <> nil);

End;

           

·         Vacía: Indica si la lista contiene o no elementos.

·         Tamaño: Indica el número de elementos de la lista. 

Estructura básica

Type

      Lista = celda;

      Celda = record

                 Elemento: T;

                 Siguiente: lista;

End;

Tipos de listas

·         Listas Simples: Se define como un conjunto de nodos uno detrás de otro, del cual siempre se puede conocer al nodo inicial y al final, de cada nodo de la lista, se conoce un contenido, que es la información que almacena dentro puede ser de cualquier tipo de dato un sucesor único excepto el ultimo nodo de la lista.

·         Listas Ordenadas: Son las que la posición de cada nodo viene determinada por el valor de uno o más campos obligatorios de información del nodo denominado clave. No se permite tener dos nodos con la misma clave.