P I L A S
Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese estremos se llama ``la parte superior'' de la pila.
Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 1 el elemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.
Figura 1
Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es la que se muestra en la figura 2
Figura 2
De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debemos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo.
Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como:
Retira de la pila hasta que el elemento retirado sea C.
Ni siquiera es necesario decir: ``Retira un elemento de la pila...'' porque es sobreentendido que solamente se puede sacar un elemento a la vez.
Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 3
Figura 3
La dinámica de la pila, es decir, la manera en cómo entran los datos a la estructura de datos y cómo salen, ultimo en entra, primero en salir.
Figura 4
En la figura 4 se muestran ``fotografías'' en distintos momentos de la pila, cuando se desea insertar H justo debajo de F. Para hacer esto se requiere, retirar tantos elementos como sean necesarios, aquí se han retirado de la cima G y F para luego insertar H, que quedará posteriormente debajo de F.
Lo que sucede es que, cuando se retira el elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en este caso el elemento objetivo es F, puesto que se desea insertar un elemento debajo de F.
Después de haber insertado F, insertamos de nuevo los elementos F y G en ese orden, además de insertar finalmente el elemento I que queda en la cima de la pila. Enseguida veremos con más detalle las operaciones básicas de las pilas.
C O L A S
Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo y se retiran elementos por el otro extremo. De hecho a este tipo de dispositivos se les conoce como dispositivos ``fifo'' (first in, first out) porque funcionan como una tubería, lo que entra primero por un extremo, sale primero por el otro extremo.
En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera.
Figura 6
Dinámica de una cola. a) estado actual con una cola con tres elementos a,b,c; b) estado de la cola cuando se agrega el elemento d; c) estado de la cola cuando se elimina el elemento a del frente de la cola
En la figura 6 se muestra una actividad típica de la cola, en donde se muestra que se agregan datos por la parte trasera de la cola y se eliminara datos por el frente de la cola.
Si Q es una cola y x es un elemento, se pueden hacer tres operaciones básicas con las colas:
-
insert(Q,x), que inserta el elemento x en la parte trasera de la cola Q.
-
x=remove(Q), que almacena en x el valor del elemento retirado de la parte frontal de la cola Q.
-
empty(Q), que es un predicado de valor booleano, y es verdadero cuando la cola Q tiene 0 elementos, y es falso cuando la cola Q tiene al menos un elemento, en cuyo caso, ese único elemento es la parte frontal y la parte trasera de la cola al mismo tiempo.
Teóricamente no hay límite para el tamaño de la cola, así que siempre se debería poder insertar elementos a una cola, sin embargo, al igual que las pilas, normalmente se deja un espacio de memoria para trabajar con esta estructura. Por el contrario, la operación remove sólamente se puede hacer si la cola no está vacía.
