Pilas
Definición
¿Qué es una pila?
Una pila (stack) es una estructura de datos, que consta de una serie de datos, en la cual las inserciones y eliminaciones se hacen por un extremo, llamado cima (top), de la pila. La estructura pila se conoce como LIFO (last-in, first-out, último en entrar, primero en salir), que significa “último elemento introducido, primero sacado”.
Operaciones fundamentales
Las operaciones fundamentales introducir y eliminar se hacen por un extremo de la pila llamado cima (top).
Veamos algunos ejemplos de pilas en la vida cotidiana:
Ejemplos en Computación
l Llamado a funciones.
– El programa principal llama a una función.
– La función llama a otra función.
– La pila indica dónde debe regresar la función una vez que se termina la misma – lo indica la pila à última función que hizo el llamado, primera en volver – .
– Aplicación principal ]FUNCIONES RECURSIVAS.
l Bucles anidados.
– Último bucle en abrirse, primero en cerrarse.
l Condiciones anidadas.
– Última condición en abrirse, primera en cerrarse.
Evolución de la PILA
Operaciones básicas de la PILA
l Crear o inicializar inicializar una pila (p) vacía.
l Pila vacía (empty) determinar si una pila esta vacía.
l Pila llena determina si la pila se ha llenado.
l Meter (push) inserta un elemento en la cima de la pila.
l Sacar (pop) recupera y elimina el último elemento en la cima de la pila.
Implementación de las funciones con punteros
//Declaraciones generales
Estructura tipo_nombre
…………..
…………..
Tipo_nombre anterior
Fin de estructura
tipo_nombre à cima, elemento
tipo cantidad à tope
función inicializar
cima = nulo
fin función
lógico función vacío
si cima = nulo
devolver (verdadero)
si_no
devolver (falso)
fin_si
fin función
lógico función llena
si cima = tope
devolver (verdadero)
si_no
devolver (falso)
fin_si
fin función
función meter
tipo nombre auxi
reservar (auxi)
auxiàelemento = elemento
auxi àanterior = cima
cima = auxi
fin función
función sacar
tipo nombre auxi
auxi = cima
elemento = auxiàelemento
cima = auxiàanterior
liberar (auxi) // Procedimiento para la eliminación de variables dinámicas
fin función
Ejemplo de Pila:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <iostream.h>#include <conio.h>#include <string.h>#include <stdlib.h>#include <stdio.h>struct pilas{int d;pilas *a;}*c,*e;void menu(void);void ingresar(void);void sacar (void);void actualizar_pila(void);main(){menu();}void menu(void){int y,opc; for(;;) { cout<<"\n1. Ingresar datos"; cout<<"\t2. Sacar datos"; cout<<"\t0. Terminar"; cout<<"\n Ingrese opcion: ";cin>>opc; switch(opc) { case 1: ingresar(); break; case 2: sacar(); break; case 0: exit(1); default: cout<<"\n Opcion no valida!!"; break; }actualizar_pila();cout<<"\n\nOprima una tecla para continuar";getch(); }}void ingresar (void){ if(!c) { c=new(pilas); cout<<"Ingrese elemento: "; cin>>c->d; c->a=NULL; return; } e=new(pilas); cout<<"\nIngrese elemento: "; cin>>e->d; e->a=c; c=e;}void sacar(void){ if(!c) { cout<<"\n\nNo hay elementos!!"; return; } e=new(pilas); e=c; cout<<"\n\nElemento eliminado: " <<e->d; c=e->a; delete(e);}void actualizar_pila(void){ int y=2,i,ca=0; e=c; while(e) { ca++; e=e->a; }for(i=0;i<=ca;i++) { cout<<" "; } //muestro lo que tiene la pila!! i=0; e=c; while(e) { cout<<"\n"; cout<<++i<<" - "<<e->d; e=e->a; }} |
