Lista, Pilas y Colas

Por:

Adan Fernández 10-

1005

Estructura de datos

Definición de lista

Una lista es una estructura de datos homogénea

y dinámica, que va a estar formada por una

secuencia de elementos, donde cada uno de

ellos va seguido de otro o de ninguno.

Homogénea: Todos los elementos que la forman tienen el mismo tipo base.

Dinámica: Puede crecer o decrecer en tiempo de ejecución según nuestras necesidades.

dos listas pueden ser diferentes si:

No tienen el mismo número de elementos:

L1: gato, perro.

L2: gato, canario, cerdo.

Cuando, aun teniendo el mismo número de elementos, estos son distintos:

L1: gato, perro.

L2: gato, cerdo.

Definición de pila y cola

Una pila es una estructura de datos a la cual sepuede acceder solo por un extremo de la misma. Lasoperaciones de inserción y extracción se realizan através del tope, por lo cual no se puede acceder acualquier elemento de la pila. Se la suele llamarestructura L.I.F.O. como acrónimo de las palabrasinglesas "last in, first out" (último en entrar, primeroen salir). La pila se considera un grupo ordenado deelementos, teniendo en cuenta que el orden de losmismos depende del tiempo que lleven "dentro" dela estructura.

Una cola es una colección de elementos

homogéneos (almacenados en dicha

estructura), en la misma se pueden insertar

elementos por uno de los extremos, llamado

frente, y retirar los mismos por el otro

extremo, denominado final.

Diferencias entre pila y cola

Se entiende por cola una estructura de datos en

la que se añaden nuevos ítems en un extremo y

se suprimen ítems viejos en el opuesto.

A diferencia de las colas, en las pilas los ítems

se añaden y se eliminan en el mismo extremo.

Operaciones básica de una

lista

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

•Añadir o insertar elementos.

•Buscar o localizar elementos.

•Borrar elementos.

•Moverse a través de la lista, siguiente.

Cada una de éstas operaciones podrá tener varios casos especiales, por ejemplo, tendremos que tener en cuenta cuando se inserte un nodo en una lista vacía, o cuando se elimina el único nodo de una lista.

Diferencia entre estructuras

estáticas y dinámicas

Estructura de Datos estáticas:Son aquellas en las que el espacio ocupado en memoria se define en tiempo de compilación y no puede ser modificado durante la ejecución del programa. Corresponden a este tipo los arrays y registros

Estructuras de Datos Dinámicas:Son aquellas en las que el espacio ocupado en memoria puede ser modificado en tiempo de ejecución. Corresponden a este tipo las listas, árboles y grafos . Estas estructuras no son soportadas en todos los lenguajes. La elección de la estructura de datos idónea dependerá de la naturaleza del problema a resolver y, en menor medida, del lenguaje.

Ejemplos de lenguaje de

ImplementaciónListavoid Insertar(Lista *lista, int v) { pNodo nodo;

// Creamos un nodo para el nuvo valor a insertar nodo = (pNodo)malloc(sizeof(tipoNodo));

nodo->valor = v;

// Si la lista está vacía, la lista será el nuevo nodo

// Si no lo está, insertamos el nuevo nodo a continuación del apuntado

// por lista

if(*lista == NULL) *lista = nodo; else nodo->siguiente = (*lista)->siguiente;

// En cualquier caso, cerramos la lista circular

(*lista)->siguiente = nodo; }

pilatypedef struct _nodo { int dato;

struct _nodo *siguiente; }

tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Pila;