Colas

COLAS

Una cola constituye una estructura lineal de datos en la que los nuevos elementos se introducen por un extremo y los ya existentes se eliminan por el otro. Es importante señalar que los componentes de la cola se eliminan en el mismo orden en el cual se insertaron. Es decir, el primer elemento que se introduce en la estructura será el que se eliminara en primer orden. Debido a esta característica, las colas también reciben el nombre de estructuras FIFO (First-In, First-Out: el primero en entrar es el primero en salir).

Implementación

Las colas, al igual que las pilas, no existen como estructuras de datos estándar en lenguajes de programación. Este tipo de estructura de datos se puede representar mediante el uso de:

• Arreglos 
• Listas 

Implementación Estática

Cuando se implementan con arreglos unidimensionales, es importante definir tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que almacene la posición del primer elemento de la cola —FRENTE— y otra para que guarde la posición del último elemento de la cola —FINAL—. 

Operaciones

Las operaciones básicas que pueden efectuarse son:

• Insertar un elemento en la cola 
• Eliminar un elemento de la cola 

Las inserciones se llevaran a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE —recuerde que el primero en entrar es el primero en salir—.

Y las operaciones auxiliares:

• Cola_vacía 
• Cola_llena 

Aplicaciones

Algunas aplicaciones de las colas son:

1. Para modelar 'colas reales' en el mundo de las computadoras: Colas de impresión, Colas de tareas, Colas de procesos.
2. Simulaciones.
3. Búsqueda en anchura.

Enlaces interesantes

http://es.wikipedia.org/wiki/Cola_(estructura_de_datos)

http://www.conclase.net/c/edd/?cap=003#inicio

Pilas

PILAS

Una pila representa una estructura lineal de datos en la que se puede agregar o quitar elementos únicamente por uno de los dos extremos.

Existen numerosos casos prácticos, p.e. una pila de platos, una pila de latas en un supermercado, una pila de libros que se exhiben en una librería, etcétera.

Definición Formal

Colección de datos a los cuales se puede acceder mediante un extremo, que se conoce generalmente como tope.

Las pilas no son estructuras fundamentales de datos. Para su representación requieren el uso de otras estructuras de datos, como:

Arreglos: representación estática

Listas: representación dinámica 

Operaciones

La definición de una estructura de datos queda completa al incluir las operaciones que se pueden realizar en ella. Para el caso de las pilas, las operaciones básicas que se pueden. Llevar a cabo son:

• Insertar un elemento —Push— en la pila 
• Eliminar un elemento —Pop— de la pila 

Y las operaciones auxiliares:

• Pila_vacía 
• Pila_llena 

Aplicaciones

Las pilas son una estructura de datos muy usada en la solución de diversos tipos de problemas, en el área de la computación:

• Llamadas a subprogramas
• Tratamiento de expresiones aritméticas
• Recursividad
• Ordenación

Ejemplo de Aplicación de Pilas:

Enlaces interesantes:
https://es.wikipedia.org/wiki/Pila_(inform%C3%A1tica
http://www.conclase.net/c/edd/?cap=002#inicio

Estructuras Lineales

ESTRUCTURAS LINEALES

Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro.
Cada elemento de la estructura puede estar conformado por uno o varios subelementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Definición Formal:

Sea la lista L. Cada elemento e de la lista L tiene asignado un tipo de dato T, entonces  e1, e2, · · · , en conforman la lista L cuyos elementos tienen asignado un mismo tipo.  

Las propiedades de las listas son:

• Si n = 0 entonces la lista está vacía
• Si n ≥ 1 entonces e1 es el primer elemento de la lista y en el último, ei es el predecesor de ei+1 y el sucesor de ei-1 con 1≤ i ≤ n

Ejemplo: 

Sea la lista L= (‘casa’, ‘perro’, ‘auto’, ‘árbol’) entonces 

• ‘casa’ es el primer elemento de L y no tiene predecesor.
• ‘árbol’ es el último elemento de L y no tiene sucesor
• ‘casa’ es el predecesor de ‘perro’
• ‘perro’ es el sucesor de ‘casa’

Clasificación:
Las listas se pueden clasificar por varios criterios: 

• Por el orden de sus elementos sobre la base de un subelemento: ordenadas  (ascendente o descendente), y desordenadas.
• Por el método de almacenamiento: secuencial y enlazada (simple, doble, simple circular y doble circular).