Tipo abstracto de datos Pila
Una pila (stack) es una colección ordenada de elementos a los que sólo se puede acceder por un único
lugar o extremo de la pila. Los elementos de la pila se añaden o quitan (borran) de la misma sólo por
su parte superior (cima) de la pila.
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.
Operaciones básicas de una pila.
Debido a su propiedad específica “último en entrar, primero en salir” se conoce a las pilas como
estructura de datos LIFO (last-in/first-out).
La pila se puede implementar guardando los elementos en un arreglo en cuyo caso su dimensión
o longitud es fija. También se puede utilizar un Vector para almacenar los elementos. Otra forma de
implementación consiste en construir una lista enlazada, cada elemento de la pila forma un nodo de la
lista; la lista crece o decrece según se añaden o se extraen, respectivamente, elementos de la pila; ésta
es una representación dinámica y no existe limitación en su tamaño excepto la memoria de la computadora.
Una pila puede estar vacía (no tiene elementos) o llena (en la representación con un arreglo, si se
ha llegado al último elemento). Si un programa intenta sacar un elemento de una pila vacía, se producirá
un error, una excepción, debido a que esa operación es imposible; esta situación se denomina desbordamiento
negativo (underflow). Por el contrario, si un programa intenta poner un elemento en
una pila llena se produce un error, o excepción, de desbordamiento (overflow) o rebosamiento.
Especificaciones de la pila.
Las operaciones que sirven para definir una pila y poder manipular su contenido son las siguientes. Tipo de dato Elemento que se almacena en la pila
Operaciones
CrearPila 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
CimaPila Obtiene el elemento cima de la pila
Tamaño de la pila Número de elementos máximo que puede contener la pila.
Ejemplo 36.2 muestra cómo declarar una pila con un arreglo lineal. El tipo de los elementos de
la pila es Object, lo que permite que pueda contener cualquier tipo de objeto.
- Pila dinámica implementada con el vector.
La clase Vector es un contenedor de objetos que puede ser manejado para que crezca y decrezca dinámicamente.
Los elementos de Vector son de tipo Object. Dispone de métodos para asignar un
elemento en una posición (insertElementAt), para añadir un elemento a continuación del último
(addElement), para obtener el elemento que se encuentra en una posición determinada (elementAt),
para eliminar un elemento (removeElementAt) ...
La posición del último elemento añadido a la pila se mantiene con la variable cima. Inicialmente
cima == −1, que es la condición de pila vacía.
Insertar un nuevo elemento supone aumentar cima y asignar el elemento a la posición cima del
Vector. La operación se realiza llamando al método addElement. No resulta necesario implementar
el método pilaLlena ya que la capacidad del Vector crece dinámicamente.
El método quitar( ) devuelve el elemento cima de la pila y lo elimina. Al utilizar un Vector,
llamando a removeElementAt(cima) se elimina el elemento cima; a continuación se decrementa
cima.
La implementación es:
- Pila implementada con una lista enlazada.
Guardar los elementos de la pila en una lista enlazada permite que la pila crezca o decrezca de manera
indefinida. El tamaño se ajusta exactamente a su número de elementos.
- Clase Pila y NodoPila.
Los elementos de la pila son los nodos de la lista, con un campo para guardar el elemento y otro de enlace.
La clase NodoPila representa un nodo de la lista enlazada. Tiene dos atributos: elemento guarda
el elemento de la pila y siguiente contiene la dirección del siguiente nodo de la lista. El constructor
pone el dato en elemento e inicializa siguiente a null. El tipo de dato de elemento se corresponde
con el tipo de los elementos de la pila, para que no dependa de un tipo concreto; para que sea más gené
rico se utiliza el tipo Object y de esa forma puede almacenar cualquier tipo de referencia.
La clase PilaLista implementa las operaciones del TAD pila. Además, dispone del atributo cima
que es la dirección del primer nodo de la lista. El constructor inicializa la pila vacía (cima == null),
realmente, a la condición de lista vacía.
Implementación de las operaciones.
Las operaciones insertar, quitar, cima acceden a la lista directamente con la referencia cima
(apunta al último nodo apilado). Entonces, como no necesitan recorrer los nodos de la lista, no dependen
del número de nodos, la eficiencia de cada operación es constante, O(1).
La clase PilaLista forma parte del mismo paquete que NodoLista, por ello tiene acceso a todos
sus miembros.
Verificación del estado de la pila:
Poner un elemento en la pila. Crea un nuevo nodo con el elemento que se pone en la pila y se enlaza
por la cima.
Eliminación del elemento cima. Retorna el elemento cima y lo quita de la pila.
Obtención del elemento cabeza o cima de la pila, sin modificar la pila:
Vaciado de la pila. Libera todos los nodos de que consta la pila. Recorre los n nodos de la lista enlazada,
entonces es una operación lineal, O(n).
Tutorial de Pilas.
Tipo abstracto de datos Cola.
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 (figura 36.18). 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 almacena, por ello una cola es una estructura de tipo FIFO
(first-in/first-out, primero en entra.
Especificaciones del tipo abstracto de datos 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 Comprobar si la cola no tiene elementos
Cola llena Comprobar 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
Las colas se implementan utilizando una estructura estática (arreglos), o una estructura dinámica
(listas enlazadas, Vector...). Utilizar un arreglo tiene el problema del avance lineal de frente y fin;
este avance deja huecos por la izquierda del arreglo. Llega a ocurrir que fin alcanza el índice más alto
del arreglo, sin poder añadir nuevos elementos y sin embargo haber posiciones libres a la izquierda de
frente.
- Cola con un arreglo circular .
La forma más eficiente de almacenar una cola en un array es modelar a éste de tal forma que se una
el extremo final con el extremo cabeza. Tal arreglo se denomina arreglo circular y permite que la totalidad
de sus posiciones se utilicen para almacenar elementos de la cola sin necesidad de desplazar
elementos. La figura 36.20 muestra un arreglo circular de n elementos.
El arreglo se almacena de modo natural en la memoria, como un bloque lineal de n elementos. Se
necesitan dos marcadores (apuntadores) frente y fin para indicar, respectivamente, la posición del elemento
cabeza y del último elemento puesto en la cola.
El frente siempre contiene la posición del primer elemento de la cola y avanza en el sentido de
las agujas del reloj; fin contiene la posición donde se puso el último elemento, también avanza en el
sentido del reloj (circularmente a la derecha). La implementación del movimiento circular se realiza
según la teoría de los restos, de tal forma que se generen índices de 0 a MAXTAMQ−1:
Mover fin adelante = (fin + 1) % MAXTAMQ
Mover frente adelante = (frente + 1) % MAXTAMQ
Los algoritmos que formalizan la gestión de colas en un arreglo circular han de incluir las operaciones
básicas del TAD cola; en concreto, las siguientes tareas básicas:
• Creación de una cola vacía, de tal forma que fin apunte a una posición inmediatamente anterior
a frente:
frente = 0; fin = MAXTAMQ−1.
• Comprobar si una cola está vacía:
frente == siguiente(fin)
• Comprobar si una cola está llena. Para diferenciar la condición entre cola llena y cola vacía se
sacrifica una posición del arreglo, de tal forma que la capacidad de la cola va a ser MAXTAMQ−1.
La condición de cola llena:
frente == siguiente(siguiente(fin))
• Poner un elemento a la cola, si la cola no está llena, avanzar fin a la siguiente posición: fin =
(fin + 1) % MAXTAMQ y asignar el elemento.
• Retirar un elemento de la cola, si la cola no está vacía, quitarlo de la posición frente y avanzar
frente a la siguiente posición:(frente + 1) % MAXTAMQ.
• Obtener el elemento primero de la cola, si la cola no está vacía, sin suprimirlo de la cola.
- Clase cola con array circular .
La clase declara los apuntadores frente, fin y el arreglo listaCola[ ]. El método siguiente( )
obtiene la posición siguiente de una dada, aplicando la teoría de los restos.
A continuación se codifica los métodos que implementan las operaciones del TAD cola. Ahora el
tipo de los elementos es Object, de tal forma que se pueda guardar cualquier tipo de elementos.
- Cola implementada con una lista enlazada .
La implementación del TAD Cola con una lista enlazada permite ajustar el tamaño exactamente al nú
mero de elementos de la cola; la lista enlazada crece y decrece según las necesidades, según se incorporen
elementos o se retiren. Utiliza dos apuntadores (referencias) para acceder a la lista, frente y
fin, que son los extremos por donde salen y por donde se ponen, respectivamente, los elementos de
la cola.
La referencia frente apunta al primer elemento de la lista y por tanto de la cola (el primero en
ser retirado). La referencia fin apunta al último elemento de la lista y también de la cola.
Declaración de nodo y cola
Se utilizan las clases Nodo y ColaLista. El Nodo representa al elemento y al enlace con el siguiente
nodo; al crear un Nodo se asigna el elemento y el enlace se pone null. Con el objetivo de generalizar,
el elemento se declara de tipo Object.
La clase ColaLista define las variables (atributos) de acceso: frente y fin, y las operaciones
básicas del TAD cola. El constructor de ColaLista inicializa frente y fin a null, es decir, a la
condición cola vacía.
Tutorial de Colas.
EJERCICIOS REPASO.
CÓDIGO PILA.
CÓDIGO COLA.
CÓDIGO MAIN.
Diferencia entre Pila y Cola
Diferencia entre Pila y Cola
