Estructuras dinámicas: Listas tipo Cola

Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out – primero en entrar primero en salir)
Confeccionaremos un programa que permita administrar una lista tipo cola. Desarrollaremos los métodos de insertar, extraer, vacia e imprimir.
Continuar leyendo “Estructuras dinámicas: Listas tipo Cola”

Listas tipo Pila

Una lista se comporta como una pila si las inserciones y extracciones las hacemos por un mismo lado de la lista. También se las llama listas LIFO (Last In First Out – último en entrar primero en salir)

Importante: Una pila al ser una lista puede almacenar en el campo de información cualquier tipo de valor (int, char, float, vector de caracteres, un objeto, etc)

Para estudiar el mecanismo de utilización de una pila supondremos que en el campo de información almacena un entero (para una fácil interpretación y codificación)

Inicialmente la PILA está vacía y decimos que el puntero raiz apunta a null (Si apunta a null decimos que no tiene una dirección de memoria):

pila vacía

Insertamos un valor entero en la pila: insertar(10)

pila

Luego de realizar la inserción la lista tipo pila queda de esta manera: un nodo con el valor 10 y raiz apunta a dicho nodo. El puntero del nodo apunta a null ya que no hay otro nodo después de este.

Insertamos luego el valor 4: insertar(4)

pila

Ahora el primer nodo de la pila es el que almacena el valor cuatro. raiz apunta a dicho nodo. Recordemos que raiz es el puntero externo a la lista que almacena la dirección del primer nodo. El nodo que acabamos de insertar en el campo puntero guarda la dirección del nodo que almacena el valor 10.

Ahora qué sucede si extraemos un nodo de la pila. ¿Cuál se extrae? Como sabemos en una pila se extrae el último en entrar.

Al extraer de la pila tenemos: extraer()

pila

La pila ha quedado con un nodo.
Hay que tener cuidado que si se extrae un nuevo nodo la pila quedará vacía y no se podrá extraer otros valores (avisar que la pila está vacía)

Problema 1:

Continuar leyendo “Listas tipo Pila”

Estructuras dinámicas, lista

Conocemos algunas estructuras de datos como son los vectores y matrices. No son las únicas. Hay muchas situaciones donde utilizar alguna de estas estructuras nos proporcionará una solución muy ineficiente (cantidad de espacio que ocupa en memoria, velocidad de acceso a la información, etc.)

Ejemplo 1. Imaginemos que debemos realizar un procesador de texto, debemos elegir la estructura de datos para almacenar en memoria las distintas líneas que el operador irá tipeando. Una solución factible es utilizar una matriz de caracteres. Pero como sabemos debemos especificar la cantidad de filas y columnas que ocupará de antemano. Podría ser por ejemplo 2000 filas y 200 columnas. Con esta definición estamos reservando de antemano 800000 bytes de la memoria, no importa si el operador después carga una línea con 20 caracteres, igualmente ya se ha reservado una cantidad de espacio que permanecerá ociosa. Continuar leyendo “Estructuras dinámicas, lista”