GuiaLabPilas 2014
GuiaLabPilas 2014
GuiaLabPilas 2014
Introduccin: Con esta gua se estudiar en detalle las formas de implementar las estructuras
de datos pila en diferentes lenguajes de programacin. La pila es una estructura de datos que
almacena y recupera sus elementos atendiendo un estricto orden. Las pilas se conocen tambin
como estructuras LIFO (Last-In, First-Out; Ultimo en Entrar Primero en Salir), todas las
inserciones y extracciones de elementos se realizan por un mismo extremo denominado tope de
la pila.
Objetivo: Que el estudiante conozca como se pueden utilizar las pilas en algunos problemas,
comprenda mejor el concepto de pila y practique el uso de la estructura en sus dos
implementaciones: esttico y dinmico, resolviendo algunos ejercicios.
I Pilas en el Lenguaje C
/* PILAS.C */
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define STACKSIZE 100
void main() {
STACKELEMENT a;
int p, i;
STACK b;
STACK *c=&b;
b.top=-1;
clrscr();
/* limpia la pila */
void Clear(STACK * ps) {
ps->top= -1 ;
}
/* verifica si la pila esta vacia */
int Empty(STACK * ps) {
if (ps->top == -1)
return(TRUE);
else
return(FALSE);
}
/* verifica si la pila esta llena, si ya no se pueden introducir mas elementos en el arreglo */
int Full(STACK * ps) {
if (ps->top == STACKSIZE - 1)
return(TRUE);
else
return(FALSE);
}
/* introduce un elemento en la pila */
void Push(STACK * ps, STACKELEMENT x) {
if (Full(ps)) {
printf("%s","Pila desbordada");
exit(1); }
else
2. Modifique el programa anterior para que la funcin main() sea mas flexible: que le
de la oportunidad al usuario de escoger cuantas operaciones de pila desea
realizar.
3. A continuacin se tiene un programa que origina una lnea de texto y utiliza una
pila para imprimir la lnea invertida.
#define MAXCOLS 80
#define TRUE 1
#define FALSE 0
struct stack {
int tope;
char elementos[MAXCOLS];
};
void main() {
char linea[MAXCOLS];
char invert[MAXCOLS];
int pos=0, i;
struct stack pila;
pila.tope=-1;
while ((linea[pos++]=getchar()) != '\n');
linea[--pos]= '\0';
printf("La linea original es:\n %s", linea);
for (i=0; i<pos; i++)
push(&pila, linea[i]);
for (i=0; i<pos; i++)
invert[i]=pop(&pila);
invert[i] = '\0';
printf("\nLa linea invertida es: \n %s", invert);
getch();
}
4. Modifique el programa anterior para que tambin cuente el nmero de vocales que tiene
la lnea de texto.
5. Pruebe el siguiente programa (use extensin .cpp) que hace una conversin de interfija
a postfija. Los operandos validos son las letras de la A a la Z y los dgitos 0 a 9. Las
operaciones validas solo incluyen divisin ( / ), multiplicacin ( * ), suma ( + ) y resta ( - ).
#define MAXCOLS 80
#define TRUE 1
#define FALSE 0
struct stackNode {
int data;
stackNode *nextPtr;
};
void main()
{
char infix[MAXCOLS];
int pos = 0;
clrscr();
while ((infix[pos++] = getchar()) !='\n');
infix[--pos] = '\0';
cout<<"La expression original infija es "<< infix;
postfix(infix, postr);
cout<<postr<<endl;
getch();
} //fin de main
tempPtr = *ps;
a = (*ps)->data;
*ps = (*ps)->nextPtr;
free(tempPtr);
return a;
6. Programa que origina una lnea de texto y utiliza una pila para imprimir la lnea
invertida. Esta es la versin utilizando memoria dinmica.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAXCOLS 80
void main() {
char linea[MAXCOLS];
char invert[MAXCOLS];
int pos=0, i;
Pila p1=NULL;
temp = *ps;
popvalue = (*ps)->dato;
*ps = (*ps)->siguiente;
free(temp);
return popvalue;
}
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void VaciaP(Pila** P) {
*P = NULL ;
} // VaciaP
void BorrarP(Pila** P) {
Pila *NuevoNodo ;
if (EsVaciaP(*P)) {
puts ("Se intenta extraer un elemento de una pila vacia") ;
exit(1) ;
}
NuevoNodo=(*P) ;
(*P) = NuevoNodo->sig ;
free(NuevoNodo) ;
} // BorrarP
Ejercicios Propuestos en C:
1. Escriba un programa que utilice una pila para determinar si una cadena es un
palndromo (es decir, si la cadena se deletrea en forma idntica hacia delante y hacia
atrs). El programa deber ignorar espacios y puntuaciones.
2. Escriba un programa en C para convertir una cadena prefija a posfija.
3. Escriba una rutina prefix que acepte una cadena interfija y cree la forma prefija de esta
cadena, suponiendo que la cadena se lee de derecha a izquierda y que la cadena prefija
se crea de derecha a izquierda.
4. Escriba la rutina reduce en C y que acepte una cadena interfija y forme una cadena
interfija equivalente quitando todos los parntesis superfluos.
5. Repita los ejercicios del 1 al 4 utilizando memoria dinmica.
6. Modifique el programa que aparece en el ejercicio 7, escribiendo una funcin que reciba
una expresin en notacin postfija y la evalu. Utilice el siguiente cdigo.
Edite el siguiente programa (El nombre del archivo deber ser Pila.java), tal como se muestra en
la siguiente figura.
// Constructor de la Clase
public Pila(int max) {
vec=new int [max];
}
// Metodos de la Clase
public boolean llena() {
if (tope==vec.length-1)
return true;
else
return false;
}
import javax.swing.JOptionPane ;
Stack.Imprime_Datos();
}
} // UsaPila
El nombre del archivo deber ser UsaPila.java, ahora procesa a Compilar el programa
utilizando el icono
Preguntas