ESTRUCTURAS DINÁMICAS DE DATOS
En función de la forma en que se relacionan existen varios tipos de estructuras de datos. Este tipo de estructuras son autorreferenciadas, es decir, contienen entre sus campos un puntero de su mismo tipo. Las más utilizadas son:
PILAS
COLAS
PILAS
La pila es una lista de elementos caracterizada porque las operaciones de inserción y eliminación se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente 'cima' (top en nomenclatura inglesa).
Dada una pila P=(a,b,c,...k), se dice que a, que es el elemento más inaccesible de la pila, está en el fondo de la pila (bottom) y que k, por el contrario, el más accesible, está en la cima.
Las restricciones definidas para la pila implican que si una serie de elementos A,B,C,D,E se añaden, en este orden a una pila, entonces el primer elemento que se borre de la estructura deberá ser el E. Por tanto, resulta que el último elemento que se inserta en una pila es el primero que se borra. Por esta razón, se dice que una pila es una lista LIFO (Last In First Out, es decir, el último que entra es el primero que sale).
Un ejemplo típico de pila lo constituye un montón de platos, cuando se quiere introducir un nuevo plato, éste se pone en la posición más accesible, encima del último plato. Cuando se coge un nuevo plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido.
Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc..) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado que está en la cima). De ahí que la estructura pila sea muy apropiada para este fin.
Como en cualquier estructura de datos, asociadas con la estructura pila existen una serie de operaciones necesarias para su manipulación, éstas son:
• Crear la pila.
• Comprobar si la pila está vacia. Es necesaria para saber si es posible eliminar elementos.
• Acceder al elemento situado en la cima.
• Añadir elementos a la cima.
• Eliminar elementos de la cima.
La especificación correcta de todas estas operaciones permitirá definir adecuadamente una pila. Este tipo de estructuras se caracteriza porque todas las operaciones se realizan en el mismo lado. Es de tipo LIFO ( Last In First Out ), el último elemento en entrar es el primero en salir.
REPRESENTACIÓN DE LAS PILAS
Los lenguajes de programación de alto nivel no suelen disponer de un tipo de datos pila. Aunque por el contrario, en lenguajes de bajo nivel (ensamblador) es posible manipular directamente alguna estructura pila propia del sistema. Por lo tanto, en general, es necesario representar la estructura pila a partir de otros tipos de datos existentes en el lenguaje.
La forma más simple, y habitual, de representar una pila es mediante un vector unidimensional. Este tipo de datos permite definir una secuencia de elementos (de cualquier tipo) y posee un eficiente mecanismo de acceso a la información contenida en él.
Al definir un array hay que determinar el número de índices válidos y, por lo tanto, el número de componentes definidos. Entonces, la estructura pila representada por un array tendrá limitado el número de posibles elementos.
Se puede definir una pila como una variable:
Pila: array [1..n] de T
donde T es el tipo que representa la información contenida en la pila (enteros, registros,etc.)
El primer elemento de la pila se almacenará en Pila[1], será el fondo de la pila, el segundo elemento en Pila[2] y así sucesivamente. En general, el elemento i-úsimo estará almacenado en Pila[i].
Como todas las operaciones se realizan sobre la cima de la pila, es necesario tener correctamente localizada en todo instante esta posición. Es necesaria una variable, cima, que apunte al último elemento (ocupado) de la pila.
Con estas consideraciones prácticas, se puede pasar a definir las operaciones que definen la pila.
CREAR PILA:
Es necesario definir el array que permitirá almacenar la información y la variable que indica la posición de la cima. Además tendremos que inicializar cima al valor 0, indicando que la creación implica que la pila está vacía.
(1) Variables
(2) Pila: array [1..n] de T
(3) cima: 0..n
(4) (2) Asignación de pila vacía
(5) cima <-- 0
COMPROBAR SI LA PILA ESTÁ VACÍA:
Esta operación permitirá determinar si es posible eliminar elementos.
ALGORITMO PILA_ VACIA
Entrada
cima: 0..n
Salida (cierto, falso)
Inicio
si cima=0 entonces devolver(cierto)
sino devolver(falso)
Fin
OPERACIÓN DE INSERCIÓN
La operación de inserción normalmente se conoce por su nombre inglés push. La operación aplicada sobre una pila y un valor x, inserta x en la cima de la pila. Esta operación está restringida por el tipo de representación escogido. En este caso, la utilización de un array implica que se tiene un numero máximo de posibles elementos en la pila, por lo tanto, es necesario comprobar, previamente a la inserción, que realmente hay espacio en la estructura para almacenar un nuevo elemento. Con esta consideración el algoritmo de inserción sería:
ALGORITMO APILAR
Entradas
x: T (* elemento que se desea insertar *)
Pila: array [1..n] de T
Salidas
Pila, cima
Inicio
si cima=n entonces "Pila llena"
sino
cima <-- cima+1
Pila[cima] <-- x
fin_sino
Fin
OPERACIÓN DE ELIMINACIÓN
La operación de borrado elimina de la estructura el elemento situado en la cima. Normalmente recibe el nombre de pop en la bibliografía inglesa. El algoritmo de borrado sería:
ALGORITMO DESAPILAR
Entradas
Pila: array [1..n] de T
Salidas
Pila, cima, x
Inicio
si NO(Pila_vacia) entonces
x <-- Pila[cima]
cima <-- cima-1
Fin
(recordemos que la función Pila_vacia nos devuelve un valor lógico (cierto o falso) que en este caso nos sirve como condición para el si)
En todos los algoritmos se podría suponer que las variables Pila y cima, lo mismo que n, son globales y, por lo tanto, no sería necesario declararlas como entradas o salidas.
Vamos a ver un ejemplo de utilización de pilas:
<?php
$dias = array ("lunes", "martes", "miercoles", "jueves", "viernes", "sabado", "doningo");
$dia_error = array_pop($dias);
array_push($dias,"domingo");
?>
En este ejemplo lo que hacemos es arreglar un array que tiene el último elemento equivocado, para eso, extraemos el último elemento "doningo" y lo guardamos como $error_dia, luego agregamos el elemento correcto y la pila queda corregida.
Este ejemplo no seria un buen ejemplo de funcionalidad de las pilas pues se podria realizar lo mismo sin nescesidad de pilas.
Pero vamos a ver un ejemplo que no podremos realizar tan facilmente sin pilas. imaginemos que tenemos un vector de dias de la semana y queremos imprimirlos en orden opuesto, como la pila extrae por detrás, los elementos salen en orden opuesto, y como se va vaciando, solo necesitaremos hacer un while(count($dias) != 0) o lo que es lo mismo while(count($dias)).
<? php
$dias = array ("lunes", "martes", "miercoles", "jueves", "viernes", "sabado", "domingo");
while(count($dias))echo array_pop($dias)."<br />";
?>
COLAS
Las colas son secuencias de elementos caracterizadas porque las operaciones de inserción y borrado se realizan sobre extremos opuestos de la secuencia. La inserción se produce en el "final" de la secuencia, mientras que el borrado se realiza en el otro extremo, el "inicio" de la secuencia.
Las restricciones definidas para una cola hacen que el primer elemento que se inserta en ella sea, igualmente, el primero en ser extraido de la estructura. Si una serie de elementos A, B, C, D, E se insertan en una cola en ese mismo orden, entonces los elementos irán saliendo de la cola en el orden en que entraron. Por esa razón, en ocasiones, las colas se conocen con el nombre de listas FIFO (First In First Out, el primero que entra es el primero que sale).
Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos. Quizás la aplicación más común de las colas es la organización de tareas de un ordenador. En general, los trabajos enviados a un ordenador son "encolados" por éste, para ir procesando secuencialmente todos los trabajos en el mismo orden en que se reciben. Cuando el ordenador recibe el encargo de realizar una tarea, ésta es almacenada al final de la cola de trabajos. En el momento que la tarea que estaba realizando el procesador acaba, éste selecciona la tarea situada al principio de la cola para ser ejecutada a continuación. Todo esto suponiendo la ausencia de prioridades en los trabajos. En caso contrario, existirá una cola para cada prioridad. Del mismo modo, es necesaria una cola, por ejemplo, a la hora de gestionar eficientemente los trabajos que deben ser enviados a una impresora (o a casi cualquier dispositivo conectado a un ordenador). De esta manera, el ordenador controla el envio de trabajos al dispositivo, no enviando un trabajo hasta que la impresora no termine con el anterior.
Análogamente a las pilas, es necesario definir el conjunto de operaciones básicas para especificar adecuadamente una estructura cola. Estas operaciones serían:
• Crear una cola vacía.
• Determinar si la cola está vacía, en cuyo caso no es posible eliminar elementos.
• Acceder al elemento inicial de la cola.
• Insertar elementos al final de la cola.
• Eliminar elementos al inicio de la cola.
Para determinar correctamente cada una de estas operaciones, es necesario especificar un tipo de representación para las colas.
Este tipo de estructuras se caracteriza porque insertamos los elementos por un lado y los extraemos por el otro lado. Es de tipo FIFO ( First In First Out ), el primer elemento en entrar es el primero en salir. Para gestionar la cola utilizaremos 3 punteros (para la pila solo eran necesarios 2)
REPRESENTACIÓN DE LAS COLAS
La representación de una cola finita en forma de vector es una tarea algo más compleja que la realizada para el caso de las pilas. Además de un array unidimensional, son necesarias un par de variables que indiquen dónde está el inicio de la cola y dónde el final. Hay diferentes formas de implementar las operaciones relacionadas con colas pero una de las más eficientes es representar el array Cola[1..n] como si fuese circular, es decir, cuando se dé la condición de cola llena se podrá continuar por el principio de la misma si esas posiciones no estan ocupadas. Con este esquema de representación, se puede pasar a especificar el conjunto de operaciones necesarias para definir una cola circular.
CREAR COLA:
Esta operación consistirá en definir la variable de tipo array que permitirá almacenar la información y las variables que apuntarán a los extremos de la estructura. Además, hay que indicar explícitamente que la cola, trás la creación, está vacía.
(1) Declaraciones:
Cola : array [1..n] de T
inicio, fin: 1..n
(2)Cola vacía:
inicio <-- 1
fin <-- 1
COMPROBAR SI LA COLA ESTÁ VACÍA:
Con las condiciones establecidas, basta comprobar si inicio = fin:
si Cola.inicio = Cola.fin entonces devolver(cierto)
sino devolver(falso)
FUNCIÓN SIGUIENTE:
Con esta función obtenemos el índice del siguiente elemento a i, se trata de calcular el resto de ese i entre el máximo índice de la cola, algo así: (Siguiente := i MOD n + 1).
Todo esto es necesario porque como hemos dicho antes Cola.inicio y Cola.fin son 1 cuando la Cola está vacia, por tanto el primer elemento nunca estará en el valor de Cola.inicio sino en el de Siguiente(Cola.inicio).
ACCEDER AL ELEMENTO INICIAL DE LA COLA:
Es importante poder acceder fácilmente al inicio de la cola; para ello se puede crear una función para tal propósito.
si Vacia(Cola) entonces "Error. Cola vacía."
sino devolver (Cola.info[Siguiente(Cola.inicio)])
INSERTAR UN ELEMENTO EN LA COLA:
Debido a la implementación estática de la estructura cola es necesario determinar si existen huecos libres donde poder insertar antes de hacerlo. Esto puede hacerse de varias formas:
si Cola.inicio = Siguiente(Cola.fin) entonces "Error. Cola llena."
sino
incrementar(Cola.fin)
Cola.info[Cola.fin] <-- x
Fin_sino
O incrementando antes y luego comparando que 'Cola.inicio' sea igual a 'Cola.fin'.
ELIMINAR UN ELEMENTO DE LA COLA:
Como puedes ver la eliminación no borra nada 'físicamente', sólo se encarga de actualizar el puntero 'Cola.inicio' en una posición y devolver el valor x como mucho, aunque esto último no sea estrictamente necesario. Aunque esa posición aun contenga datos será considerada como vacía a efectos del otro puntero 'Cola.final'.
si Vacia(Cola) entonces "Error. Cola vacía."
sino
x <-- Primero(Cola)
incrementar(Cola.inicio)
devolver(x)
fin_sino
Vamos a ver un ejemplo de utilización de colas:
<?php
// array_unshift insertar al inicio
$cola = array("A", "B", "C", "D");
echo "</br>Antes de insertar con unshift </br>";
print_r($cola);
array_unshift($cola,"AAAA");
echo "</br></br>Despues de insertar</br>";
print_r($cola);
?>
Aquí les dejo el enlace de un PDF espero que pueda servir es de estructuras Dinámicas de Datos
No hay comentarios:
Publicar un comentario