TIPOS ABSTRACTOS DE DATOS

TDA PILA

ESTRUCTURAS DE DATOS

LA PILA: UN TDA SIMPLE

Uno de los conceptos mas tiles en computacin es la pila o stack

Es un conjunto de elementos, en la que:

Los elementos se aaden y se remueven por un solo extremo

Este extremo es llamado tope de la pila

La ultima en llegar, sera la primera en salir: LIFO

Ejemplo:

Cuando un empleado se va de vacaciones, le llega correo a su escritorio y las cartas se van apilando.

Al regresar de vacaciones, la ultima carga en llegar, sera la primera que revisara

Al terminar de revisarla, la nueva carta del tope de la pila habr cambiado La ms reciente de la pila, sera la siguiente en ser revisada

TDA PILA: DEFINICION

Dada una Pila llamada S

Qu datos serian importantes conocer sobre la Pila?

Y que operaciones podramos efectuar a la misma?

Push(s,elemento1)

Elemento 1

Tope o CimaPush(s,elemento2)Elemento 2

Push(S,elemento3)Elemento 3

Pop(S)EstaVacia?SiAl revisar c/carta, se la sacaba de la pila

elemento = pop(s)

La operacin pop remueve el elemento Tope de la pila y lo retorna. La pila disminuye su tamao

Usemos el ejemplo del correo:

Al acumularse,

Cada carta(elemento), era metida a la pila: push(s,elemento)

La operacin push aumenta un elemento a la pila, y esta aumenta en su tamao

PILA: OPERACIONES

EliminarPila(Pila)Efecto: recibe una pila y la libera completamenteEstaVacia(Pila) retorna -> BooleanEfecto: Devuelve true si esta vacia y false en caso contrarioPush(pila, elemento) Efecto: Toma la pila y aumenta su tamao, poniendoel elemento en la cima de la pilaPop(Pila) retorna -> elementoEfecto: Recibe la pila, remueve el elemento tope y lo retornaExcepcion: Si la pila esta vacia, produce errorTopePila(Pila) retorna -> elementoEfecto: Devuelve el elemento cima de la pilaExcepcion: Si la pila esta vacia produce errorInicializarPila(Pila)Efecto: recibe una pila y la inicializa para su trabajo normal

TDA PILA: DEFINICION FORMAL

::= + {} ::= ::= (ReferenciaNodo | NULL) ::= + ::= {}En conclusin:

La pila es un conjunto de elementos

De los cuales solo conozco y puedo ver el TOPE

Cada elemento en la pila

Puede contener informacin de cualquier tipo, es decir, es genrico

OTRAS OPERACIONES

Al remover el ultimo elemento de una pila esta queda vaca

Una vez vaca, no se pueden sacar mas elementos de la pila

Antes de sacar un elemento de la pila

Debemos saber si la pila Esta Vaca?: EstaVacia(s)

El tope de la pila siempre esta cambiando

Deberamos poder revisar el elemento tope de la pila: TopePila(s)

Si la pila esta vaca, no debe existir un valor tope

El tratar de remover elementos o acceder a elementos de una pila vaca se llama

SUBDESBORDAMIENTO de la pila

TDA PILA: IMPLEMENTACION

Hay varias formas, analicemos la mas sencilla

La Pila es una Lista pero limitada

En la lista los nuevos nodos se pueden insertar y remover Al/Del Inicio, al final, dada una posicin, etc.

En la Pila los elementos solo se pueden insertar al final de la lista

Y solo se pueden remover del Final de la lista

Las implementaciones de la LSE

Esttica o Dinmica

Nos sirven perfectamente para la Pila

IMPLEMENTACION ESTATICA

La Pila seria una arregloclass Pila {

nodo my_pila[];Int tope;......}Y solo deberemos implementar las operaciones de

Push, llamando a InsertarNodoFinal

Pop, llamando a SacarNodoFinal

TopePila, llamando a ConsultarUltimo

es decir, cada operacin de la pila esconde dentroLas operaciones de la Lista Contigua

MAX_ELEM

Tope = -1

Tope = MAX_ELEM-1

Tope = 0

Y LAS OPERACIONES?

Pila_Crear

Pila_Vacia

public bool EstaVacia(){Return( my_pila.tope==-1);}

public ~Pila(int max) {Node my_pila=new Array(int max);tope=-1;}.......}Tope

public nodo Tope(){If tope > -1;Return( my_pila[tope]);elsereturn(NULL);}

OPERACIONES BASICAS DE LA PILA

Pop

Remueve el elemento tope de la pila, y lo devuelve.

Si la pila esta vaca, no se puede sacar nada

public nodo Pop(){If PilaVacia()return(NULL);else{Nodo temp=my_pila[tope];tope=tope-1;Return (temp);}}public void Push(nodo elemento){If tope < my_pila.length()-1;{tope=tope+1; my_pila[tope]=elemento;}}Push

Inserta un elemento en la pila, cuando se puede.

Este elemento es el nuevo tope

El tope aumenta

IMPLEMENTACION DINAMICA

Una pila, o una cola, las dos son Listas realmente

Listas en las cuales las operaciones en Insertar y Remover estn limitadas

Una pila, se implemente exactamente igual que una Lista

Al hacer Pop, es SacarNodoFinal

Al hacer Push, es InsertarNodoFinal

Stack

La libreria implementa un TDA pila que se basa en LSE.typedef List Stack;

Stack * stackNew();

stackIsEmpty(Stack *S);

stackPush(Stack *S, NodeList *nuevo);

NodeList *stackPop(Stack *S);

NodeList *stackPeek(Stack *S);

EJERCICIO EN CLASE

Las pilas se usan para

Recuperar un conjunto de elementos en orden inverso a como se introdujeron

Un programa debe

Leer una secuencia de elementos enteros

Luego mostrarlos en orden inverso al ingresado

Ejemplo:

Si se ingresa: 1, 3, 5, 7

Se mostrara: 7, 5, 3, 1

ANALISIS

Cada elemento ingresado puede ser metido en la pila

Ejemplo:

1357

135

13

1

7531Una vez llenada la pila,

Solo hay que sacar, elemento tras elemento

Hasta que la pila quede vaca

SOLUCION

Begin{Pila S = new Stack();Int dato;while(TRUE){write(Ingrese elemento:);read(dato)if(dato == centinela) break;S.Push(dato);}while(!S.empty(S)){write(S.Pop());}}

UN APLICACIN MAS PRACTICA

El compilador siempre sabe cuando se ha escrito un parntesis, o una llave de mas

Como lo hace?

Con el uso de pilas, expresiones escritas:

(a+b))Mal

((a+b) * c / 4*g-h)OK

Se puede reconocer los parntesis que no coinciden

Como lograr esta aplicacin de la pila?

ANALISIS DEL PROBLEMA

Cuando los parntesis coinciden:

Al final de la expresinTotal parntesis izq = Total parntesis der y

En todo momento, en cualquier punto de la expresinCada parntesis der. esta precedido de uno izq

Acum. parntesis der. siempre es Total_izq){valida = false;break;}}if (Total_der != Total_izq)valida = false;

UN ENFOQUE MAS NATURAL

Otra forma, es la forma natural

Cuando revisamos una expresin de este tipo:

Revisamos los parntesis de la derecha, y buscamos si tienen match en la izquierda

Para seguir este enfoque podramos:

Recordar los parentesis de la izquierda ( a medida que aparecen:

El primero en aparecer, ser el ultimo en ser recordado

El ultimo en aparecer, ser el primero en ser recordado

La Pila se utiliza justamente para recordar de la forma abajo indicadaPop el parntesis ) encontrado7 - ((X* ((X+Y)/(J-3)) + Y) / (4-2.5))As, cuando aparece un )

El primer ( recordado, debe ser su match

En ese momento, este primero recordado, ya puede ser olvidado

Al llegar al final de la expresin, ningn ( debera ser recordado

Y AHORA, EL ALGORITMO

stack S = stackNew(); /*Se declara una pila s, para almacenar los ( */

while(no hayamos leido toda la cadena){//tomar el siguiente simbolo de la expresionif(simbolo = () /*Almacenarlo*/stackPush(S,simbolo);if(simbolo = )){ /*Buscar match*/if(stackIsEmpty(S)) { /*No hubo match!!*/return(FALSE)x=stackPop(S);}}if(stackIsEmpty()) return TRUE;else return FALSE; /*Algun simbolo se quedo dentro,

APLICANDO PILAS

Veamos, revisemos justo la expresin anterior

Todos los ), encontraron su (

7-((X*((X+Y)/(J-3))+Y)/(4-2))

(

(

(

(

Y AHORA, EL ALGORITMO

stack S = stackNew(); /*Se declara una pila s, para almacenar los ( */

while(no hayamos leido toda la cadena){//tomar el siguiente simbolo de la expresionif(simbolo = () /*Almacenarlo*/stackPush(S,simbolo);if(simbolo = )){ /*Buscar match*/if(stackIsEmpty(S)) { /*No hubo match!!*/return(FALSE)x=stackPop(S);}}if(stackIsEmpty()) return TRUE;else return FALSE; /*Algun simbolo se quedo dentro,