ESTRUCTURA DE DATOS
Abril 20 del 2020
TADs LINEALES: PILAS
Una pila (stack) es una colección ordenada
de elementos a los cuales sólo se puede
acceder por un único lugar o extremo de la
pila. Los elementos se añaden o se quitan
(borran) de la pila sólo por su parte superior
(cima). Este es el caso de una pila de platos,
una pila de libros, etc.
TADs LINEALES: PILAS
Cuando se dice que la pila está ordenada, lo que se
quiere decir es que hay un elemento al que se puede
acceder primero (el que está encima de la pila), otro
elemento al que se puede acceder en segundo lugar
(justo el elemento que está debajo de la cima), un
tercero, etc.
No se requiere que las entradas se puedan comparar
utilizando el operador “menor que” (<) y pueden ser
de cualquier tipo.
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.
TADs LINEALES: PILAS
Cuando se quitan los libros de la pila, primero debe
quitarse la novela, luego la enciclopedia y por último el
diccionario.
Debido a su propiedad específica último en entrar,
primero en salir se conoce a las pilas como estructuras
de datos LIFO (last-in, first-out).
Las operaciones usuales en la pila son Insertar y Quitar.
La operación Insertar (push) añade un elemento en la
cima de la pila, y la operación Quitar (pop) elimina o
saca un elemento de la pila.
TADs LINEALES: PILAS
Una secuencia de operaciones Insertar y
Quitar. El último elemento añadido a la pila es
el primero que se quita de ella
TADs LINEALES: PILAS
La operación Insertar (push) sitúa un elemento dato en la
cima de la pila, y Quitar (pop) elimina o quita el elemento
de la pila.
TADs LINEALES: PILAS
La pila se puede implementar guardando los elementos
en un array, en cuyo caso su dimensión o longitud es
fija.
Otra forma de implementación consiste en construir una
lista enlazada, de modo que 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 del computador.
TADs LINEALES: PILAS
Una pila puede estar vacía (no tiene elementos) o llena
(en la representación con un array —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, una
excepción, de desbordamiento (overflow) o
rebosamiento. Para evitar estas situaciones se diseñan
métodos que comprueban si la pila está llena o vacía.
Operaciones: PILAS
Crear Pila 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.
Cima Pila Obtiene el elemento cima de la pila.
Tamaño de la pila Número de elementos máximo
Con Array: PILAS
La implementación con un array (arreglo) es
estática ya que el array es de tamaño fijo.
La clase PilaLineal, con esta representación,
necesita un array y una variable numérica, cima,
que apunte al último elemento colocado en la
pila. Al utilizar un array es necesario tener en
cuenta que el tamaño de la pila no puede exceder
el número de elementos del array, y la condición
pila llena será significativa para el diseño.
Con Array: PILAS
El método usual de introducir elementos en
una pila es definir el fondo de la pila en la
posición 0 del array y sin ningún elemento en
su interior, es decir, definir una pila vacía; a
continuación, se van introduciendo elementos
en la pila (en el array), de modo que el primer
elemento añadido se introduce en una pila
vacía y en la posición 0, el segundo elemento
en la posición 1, el siguiente en la posición 2 y
así sucesivamente.
Con Array: PILAS
Con estas operaciones, el índice que apunta a la cima de la
pila se va incrementando en 1 cada vez que se añade un
nuevo elemento.
Los algoritmos de introducir, “insertar” (push) y “quitar”,
sacar, (pop) datos de la pila son:
Insertar (push)
1. Verificar si la pila no está llena.
2. Incrementar en 1 el puntero índice de la pila.
3. Almacenar elemento en la posición del
puntero de la pila.
Con Array: PILAS
Quitar (pop)
1. Verificar si la pila no está vacía.
2. Leer el elemento de la posición del puntero
de la pila.
3. Decrementar en 1 el puntero de la pila.
El rango de elementos que puede tener una pila varía de 0 a
TAMPILA-1 en el supuesto de que el array se defina de tamaño
TAMPILA elementos. De modo que, en una pila llena, el puntero
(índice del array) de la pila tiene el valor TAMPILA-1, y en una pila
vacía el puntero tendrá el valor -1 (el valor 0, teóricamente, es el
índice del primer elemento).
Con Array: PILAS
Una pila de 7 elementos se puede representar
gráficamente
Con Array: PILAS
Si se almacenan los datos A, B, C, ... en la pila se
puede representar gráficamente de alguna de estas
formas:
Con Array Operaciones: PILAS
Clase PilaLineal
1. Datos de la pila (TipoDato es cualquier tipo de dato primitivo o tipo
clase).
2. crearPila inicializa una pila. Es como crear una pila sin elementos,
por tanto, vacía.
3. Verificar que la pila no está llena antes de insertar o poner (“push”)
un elemento en la pila; verificar que una pila no está vacía antes de
quitar o sacar (“pop”) un elemento de la pila. Si estas precondiciones
no se cumplen, se debe visualizar un mensaje de error y el programa
debe terminar.
4. pilaVacia devuelve verdadero si la pila está vacía y falso en caso
contrario.
5. pilaLlena devuelve verdadero si la pila está llena y falso en caso
contrario. Estas dos últimas operaciones se utilizan para verificar las
precondiciones de insertar y quitar.
.
Clase PilaLineal
6. limpiarPila vacía la pila, dejándola sin elementos y
disponible para otras tareas.
7. cimaPila devuelve el valor situado en la cima de la pila,
pero no se decrementa su puntero, ya que la pila queda
intacta.
Clase PilaLineal
Implementación Operaciones
Las operaciones insertar() y quitar() añaden y eliminan,
respectivamente, un elemento de la pila.
La operación cimaPila permite a un cliente recuperar los datos de
la cima de la pila sin quitar realmente el elemento de la misma.
La operación de insertar un elemento en la pila incrementa el
puntero cima de la pila en 1 y asigna el nuevo elemento a la lista.
Cualquier intento de añadir un elemento en una pila llena genera
una excepción o error debido al desbordamiento de la pila.
Implementación Operaciones - Insertar
Implementación Operaciones - Quitar
La operación quitar elimina un elemento de la pila copiando, primero, el
valor de la cima de la pila en una variable local, aux y, a continuación,
decrementando el puntero de la pila en 1.
El método quitar devuelve la variable aux, es decir el elemento liminado
por la operación.
Si se intenta eliminar o borrar un elemento en una pila vacía se produce
error, se lanza una excepción general.
Implementación Operaciones - Quitar
Implementación Operaciones - cimaPila
La operación cimaPila devuelve el elemento que se encuentra en la
cima de la pila. No se modifica la pila, únicamente se accede al
elemento.
Implementación Operaciones – Verificación
estado de la pila
Se debe proteger la integridad de la pila, para lo cual el tipo
Pila ha de proporcionar operaciones que comprueben su
estado: pila vacía o pila llena. Asimismo, se ha de definir una
operación, LimpiarPila, que restaure la condición inicial de la
pila, que fue determinada por el constructor Pila (cima de la
pila a -1).
El método pilaVacia comprueba (verifica) si la cima de la pila
es -1. En ese caso, la pila está vacía y devuelve verdadero; en
caso contrario, devuelve falso.
Implementación Operaciones – Verificación
estado de la pila
El método pilaLlena comprueba (verifica) si la cima es
TAMPILA - 1. En ese caso, la pila está llena y devuelve
verdadero; en caso contrario, devuelve falso.
La operación limpiarPila pone la cima de la pila a su
valor inicial.
Clase PilaLineal. Ejemplo
Escribir un programa que utilice una Pila para comprobar si una
determinada frase/palabra (cadena de caracteres) es un palíndromo.
Nota: una palabra o frase es un palíndromo cuando la lectura directa
e indirecta de la misma tiene igual valor: alila, es un palíndromo; cara
(arac) no es un palíndromo.
La palabra se lee con el método readLine() y se almacena en un
String; cada carácter de la palabra leída se inserta en una pila de
caracteres. Una vez leída la palabra y construida la pila, se
compara el primer carácter del String con el carácter que se extrae
de la pila; si son iguales, sigue la comparación con el siguiente
carácter del String y de la pila; así sucesivamente hasta que la pila
se queda vacía o hay un carácter no coincidente. Al guardar los
caracteres de la palabra en la pila se garantiza que las
comparaciones de caracteres se realizan en orden inverso:
primero con último…
Clase PilaLineal
Tiempo Para practicar con la TAD PilaLineal a partir de un array
Clase PilaLineal – Lista Enlazada
