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:
#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;
}
}