Terminología

LISTA LINEAL

Una lista lineal es un conjunto de elementos de un tipo dado que pueden variar en número y donde cada elemento tiene un único predecesor y  un único sucesor o siguiente, excepto el primero y el último de la lista.

Los elementos de una lista lineal se almacenan normalmente contiguos (un elemento detrás de otro) en posiciones consecutivas de la memoria.

Las operaciones que se pueden realizar con listas lineales contiguas son:

1. insertar, eliminar o localizar un elemento

2. Determinar el tamaño (número de elementos) de la lista

3. Recorrer la lista para localizar un determinado elemento

4. Clasificar los elementos de la lista en orden ascendente o descendente

5. Unir dos o más listas en una sola

6. Dividir una lista en varias sublistas

7. Copiar la lista

8. Borrar la lista

Las operaciones directas de añadir y eliminar se efectúan únicamente en los extremos de la lista. Esta limitación es una de las razones por las  que esta estructura es poco utilizada.

LISTAS ENLAZADAS

Los inconvenientes de las listas contiguas se eliminan con las listas enlazadas.

Una lista enlazada o encadenada es un conjunto de elementos en los que cada uno de ellos contiene la posición (o dirección) del siguiente  elemento de la lista. Cada elemento de la lista enlazada debe tener al menos dos campos: un campo que tiene el valor del elemento y un campo  enlace (link) que contiene la posición del siguiente elemento, es decir, su conexión, enlace o encadenamiento. Los elementos de una lista son  enlazados por medio de los campos enlaces.

PILAS

Una pila (stack) es una colección ordenada de elementos a los cuales sólo se puede acceder por un único lugar o extremo de la pila. Los elementos se añaden o se quitan (borran) de la pila sólo por su parte superior (cima). Este es el caso de una pila de platos, una pila de libros, etc.

Cuando se dice que la pila está ordenada, lo que se quiere decir es que hay un elemento al que se puede acceder primero (el que está encima de la pila), otro elemento al que se puede acceder en segundo lugar (justo el elemento que está debajo de la cima), un tercero, etc. No se requiere que las entradas se puedan comparar utilizando el operador “menor que” (<) y pueden ser de cualquier tipo.

Las entradas de la pila deben ser eliminadas en el orden inverso al que se situaron en la misma. Por ejemplo, se puede crear una pila de libros, situando primero un diccionario, encima de él una enciclopedia y encima de ambos una novela, de modo que la pila tendrá la novela en la parte superior.

Debido a su propiedad específica último en entrar, primero en salir se conoce a las pilas como estructuras de datos LIFO (last-in, first-out)

Las operaciones usuales en la pila son Insertar y Quitar. La operación Insertar (push) añade un elemento en la cima de la pila, y la operación Quitar (pop) elimina o saca un elemento de la pila.

Tipo de dato: Dato que se almacena en la pila.

Operaciones:

Crear. Pila Inicia.

Insertar (push). Pone un dato en la pila.

Quitar (pop). Retira (saca) un dato de la pila.

Pila vacía. Comprueba si la pila no tiene elementos.

Pila llena. Comprueba si la pila está llena de elementos.

Limpiar pila. Quita todos sus elementos y deja la pila vacía.

Cima Pila. Obtiene el elemento cima de la pila.

Tamaño de la pila. Número de elementos máximo que puede contener la pila.

Aplicaciones: Las pilas se utilizan en compiladores, sistemas operativos y programas de aplicaciones. Una aplicación interesante es la evaluación de expresiones aritméticas, también la organización de la memoria.

COLAS

Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por el frente (parte inicial, frente) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.

Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacenan y, por consiguiente, una cola es una estructura de tipo FIFO (first-in, firs-out, primero en entrar-primero en salir o bien primero en llegar-primero en ser servido). El servicio de atención a clientes en un almacén es un ejemplo típico de cola. La acción de gestión de memoria intermedia (buffering) de trabajos o tareas de impresora en un distribuidor de impresoras (spooler) es otro ejemplo típico de cola.

Las operaciones que sirven para definir una cola y poder manipular su contenido son las siguientes:

Tipo de dato: Elemento que se almacena en la cola.

Operaciones:

CrearCola. Inicia la cola como vacía.

Insertar. Añade un elemento por el final de la cola.

Quitar. Retira (extrae) el elemento frente de la cola.

Cola vacía. Comprueba si la cola no tiene elementos.

Cola llena. Comprueba si la cola está llena de elementos.

Frente. Obtiene el elemento frente o primero de la cola.

Tamaño de la cola. Número de elementos máximo que puede contener la cola.

En una cola, al igual que en una pila, los datos se almacenan de un modo lineal y el acceso a los datos sólo está permitido en los extremos de la cola.

Aplicaciones: Las colas tienen numerosas aplicaciones en el mundo de la computación: colas de mensajes, colas de tareas a realizar por una impresora, colas de prioridades, etc.

COLA DE PRIORIDAD

El término cola sugiere la forma en que ciertos objetos esperan la utilización de un determinado servicio. Por otro lado, el término prioridad sugiere que el servicio no se proporciona únicamente aplicando el concepto primero en llegar primero en ser atendido, sino que cada objeto tiene asociada una prioridad basada en un criterio objetivo. Las colas de prioridades son una estructura ordenada que se utiliza para guardar elementos en un orden establecido. El orden para extraer un elemento de la estructura sigue estas reglas:

• Se elige la cola no vacía que se corresponde con la mayor prioridad.

• En la cola de mayor prioridad, los elementos se procesan según el orden de llegada: primero en entrar-primero en salir.

Una organización formada por colas de prioridades es el sistema de tiempo compartido, necesario para mantener una serie de procesos que esperan ser ejecutados por el procesador; cada proceso lleva asociado una prioridad. También las simulaciones de sucesos que ocurren en un tiempo discreto, como la atención de una fila de clientes en un sistema de n ventanillas de despacho de billetes de transporte, se realizan con una estructura de colas de prioridades.

Implementación:

Una forma simple de implementar una cola de prioridades es con una lista enlazada y ordenada según la prioridad. Otra alternativa consiste en un array o tabla de tantos elementos como prioridades estén previstas; cada elemento de la tabla guarda los objetos con la misma prioridad. Por último, se puede utilizar la estructura del montículo para guardar los componentes. La característica del montículo permite recuperar el elemento de máxima prioridad con una simple operación.

Los elementos de una cola de prioridades son objetos con la propiedad de ordenación, de tal forma que se puedan realizar comparaciones. Esto equivale a que dispongan de un atributo, de tipo ordinal, representando la prioridad del objeto.