Pilas y Colas
Pilas y Colas
Estructuras de datos compuestas: Pilas, colas, liastas ligadas, arboles.
Listas lineales
Conjunto ordenado de elementos cuyo tamaño puede variar. Ususalmente las operaciones de creación y destrucción son validas en una lista.
Pilas
Es una lista de elemntos donde las operaciones de creación y destrucción se realicen en uno de sus extremos.
Al realizar la insercción de un elemento este ha de ser colocado inmediatamente despues del ultimo se inserto y cuando se elimine un elemento este sera el ultimo que se introdujo.
Los ultimos son los mas dificiles a eliminar.
A este mecanismo se le llama LIFO (Last in-First out) UEPS (ultimo en entrar-primero en salir)
Se tiene una cola de 5 numeros:
1
2
3
4
5
El 1 es el ultimo en entrar.. pero cuando se pida quitar un dato.. tiene que ser forzosamente el primero que entro..quedaria
2
3
4
5
Si queremos sacar otro numero seria el 2, entonces quedaria :
3
4
5
Si agregamos el numero 6 quedaria de la siguiente forma:
6
3
4
5
Al numero mas reciente o el ultimo en entrar (en este caso el 6) se le llama TOPE.
Al numero mas viejo, o de los primeros en ingresar (en este caso el 5) se le llama BASE.
Para representar el algoritmo de las operaciones la pila se almacena en un arreglo.
La pila llega hasta donde lleda el arreglo.
Ejemplo: Si tenemos un arreglo de 10 numeros... la pila solo podra contener 10 numeros.. si se le ingresa otro numero habria un desbordamiento, osea que ya no pondria ese numero en la pantalla.
1
2
3
4
5
6
7
8
9
0
2
Podemos ver que aqui hay un arreglo de 11 numeros... pero el arreglo que queremos es de 10... entonces el ultimo numero (aqui es el 2) no saldria en pantalla.
TOPE: Indicador al ultimo elemento insertado.
BASE: Indicador al inicio de la pila.
Algoritmo:
NOTA: En algunos algoritmos tope apunta a la siguiente localidad disponible en lugar del ultimo elemento insertado.
Ejemplo: tenemos un arreglo de 3 numeros...
-
2
3
En algunos porgramas el tope seria 2 ya que es el ultimo insertado, pero en otros el tope seria - (esto quiere decir que no hay numero, es un lugar vacio).
Regresando al tema:
Manejo
1: Si usan arreglos para implementar la pila esta no puede crecer mas alla del limite del arreglo si utilizan listas igadas el limite sera la cantidad de memoria disponible.
2: Cuando una pila no tiene elementos tope = 0, cuando se inseta un elemento TOPE crece, cuando se elimina TOPE disminuye.
3: Si en un momento dado la pila tiene el mismo tamaño de vector, y se desea insertar un elemento ocurrira un OVERFLOW (Desbordamiento). Es como se explicaba arriba, cuando ya no hay lugares.. hay un OVERFLOW o el desbordamiento.
4: Si en un momento dado se quiere eliminar un elemento y la pila esta vacia ocurre un UNDERFLOW (no existe)..supongamos que tenemos un vector de 3 numeros
-
-
-
como se puede ver no hemos metido ningun dato, entonces TOPE y BASE son iguales, y si queremos borrar un dato.. como no lo hay, no existe.
5: La soperaciones de insercción y eliminación se les conoce como PUSH (insercción) y POP(eliminación).
Ahora hagamos el algoritmo de una pila:
Variables a usar:
s=Vetor de n elementos
tope=indicador a ultimo elemento
x= dato a insertar
Procedimiento Push(s,tope,x)
1:[Verificar que no ocurra overflow]
Si tope=n entonces
escribir('Overflow en la pila')
alto
fin si
2:[Perdir dato]
leer x
3:[Incrementar tope]
tope=tope+1
4:[Insertar dato]
s[tope]=x
5: Alto
Procedimiento PUSH (s,tope)
1:[Verificar que no ocurra UNDERFLOW]
si tope=0 entonces
escribimos('UNDERFLOW en la pila')
fin si
2:[Desplegar (mostrar) elemento a eliminar]
escribir('Se elimina:' s[tope]')
3:[Eliminar elemento]
tope=tope-1
4:alto
Hecho por Staff || miércoles, abril 13, 2005
4 Comentarios
