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.
