Estructura Y Organizacion De Datos

2. Estructuras lineales

2.1. Pilas estáticas y dinámicas.

Una pila (stack) es una colección ordenada de elementos en la cual se puede insertar elementos por un extremo y retirarlo por el mismo extremo; ese extremo se llama parte superior de la pila o cima de la pila.

Cuando se dice que una pila esta ordenada, lo que se quiere decir es que hay un elemento al que se puede accesar primero (el que está en la cima de la pila, elemento F de la siguiente figura), el segundo elemento al cual se puede accesar es el que esta después de la cima de la pila (es el elemento E).

Si deseamos inserta un nuevo elemento a la pila (elemento G), la pila quedara como se muestra en la figura 2.

Ahora si deseamos retirar un elemento de la pila, se retirara el que está en la cima.

La pila sigue la filosofía LIFO (last-in, first-out) o UEPS (último en entrar, primero en salir).

Las operaciones mas frecuentes en una pila son Insertar y Quitar. La operación Insertar (push) añade un elemento a la pila, colocándolo en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la cima de la pila.

La pila se puede implementar mediante arreglos, en cuyo caso su dimensión o longitud es fija; otra forma de implementarla es mediante listas enlazadas, en cuyo caso se utiliza memoria dinámica y el límite es la memoria RAM de la computadora.

Una pila puede estar vacía (no tiene elementos) o llena (en el caso de tener tamaño fijo y no caben más elementos en la pila). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error, debido a que esta 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 producirá un error llamado desbordamiento (overflow). Para evitar estas situaciones se diseña funciones, que comprueben si la pila está llena o vacía.

Operaciones.

Antes de poder utilizar una pila debemos estipulas que tipo de datos almacenara (int,

float, char, etc).

Operaciones básicas

Las operaciones básicas de una pila son:

 Tamaño de la pila Número de elementos máximos que puede contener

la pila.

 Crear Pila Crear una pila vacía.

 Inicializar la Pila Inicializar la pila en vacía.

 Insertar (push) Poner un elemento en la pila.

 Quitar (pop) Retirar un elemento en la pila.

 Pila vacía (stackempty) Comprobar si la pila no está vacía.

 Pila llena (stackfull) Comprobar si la pila está llena.

 Limpiar pila (stackclear) Eliminar todo lo elementos de la pila.

 Cima (stacktop) Obtener el elemento que está en la cima de la pila.

Al utilizar un arreglo para contener los elementos de una pila hay que tener en cuenta que

el tamaño de la pila no debe de exceder el número de elementos del arreglo, por lo que el

método pilallena() es importante en el diseño.

El método más común para introducir elementos en una pila nueva es definir el fondo de

la pila en la posición -1, es decir, crear una pila vacía. Posteriormente se van

introduciendo elementos en el arreglo, de modo que el primero se agregara en la posición

1, el siguiente en la posición 2 y así sucesivamente. Por tal motivo los algoritmos de

Insertar (push) y Quitar (pop) se define como sigue:

Insertar (push)

1. Verificar si la pila no está llena.

2. Incrementa en 1 el apuntador de la pila (cima).

3. Almacenar el elemento en la nueva posición del apuntador.

Quitar (pop)

1. Verificar si la pila no está vacía.

2. Leer el elemento que se encuentra en la cima de la pila.

3. Decremento en 1 el apuntador de la pila (cima).

Pila Vacía

  



falso si P tiene por lo menos un elemento

verdadero si P no tiene elementos

Pila.pilavacia()

Cima

La operación P.cima() devuelve el valor del elemento en la cima de la pila P. Para hacer esta operación escribiremos:

d=P.cima()

Al ejecutar esta sentencia en realidad se hacen dos operaciones, primero se hace d=P.quitar(), luego un P.insertar(d), porque después de la operación cima, la pila P queda sin cambios.

Supongamos ahora la expresión ((5+6)*4)/(17+9), una de las condiciones para que sea una expresión aritmética correcta en que tengas sus paréntesis balanceados, así que deseamos saber si el número de paréntesis que abres es el mismo número de paréntesis que cierran.

Para resolver este problema usaremos el concepto de pila. La idea es simple. Vamos a leer cada elemento de la expresión, si se trata de un paréntesis que abre, entonces lo insertaremos en una pila; si se trata de un paréntesis que cierra, entonces sacamos un elemento de la pila. Al terminar de leer la expresión revisaremos si la pila está vacía, en cuyo caso habremos concluido que el número de paréntesis que abre es el mismo que el número de paréntesis que cierra y la expresión tiene paréntesis balanceados.

La representación en Java las operaciones de una pila

Definir el tipo de dato de la pila

Se debe seleccionar que tipo de dato va a manejar la pila. Por ejemplo char.

Tamaño de la pila

final static int MAX_ELEMENTOS = 100;

99999998888888777777766666665555555444444433333332222222111(111100(0(0(00(0-1-1-1-1-1-1-1(((((5+6)((5+6)*4)((5+6)*4)/(((5+6)*4)/(17+9)

Crear la pila

TipoPila Pila = new TipoPila();

Inicializar la pila

public void inicializapila() {

cima = -1;

}

Función insertar (push)

public void insertar(char d) {

if (!pilallena())

elemento[++cima]= d;

else

System.out.println(“Pila llena”);

}

Función quitar (pop)

public char quitar() {

if (!pilavacia())

return elemento[cima--];

else {

System.out.println(“Pila llena”);

return ' ';

}

}

Función pilavacia (stackempty)

public boolean pilavacia() {

if (cima == -1)

return true;

else

return false;

}

Función

...