Listas

UNIVERSIDAD DE EL SALVADOR FACULTAD DE INGENIERIA Y ARQUITECTURA ESCUELA DE INGENIERIA DE SISTEMAS INFORMATICOS PROGRAMACION II ( SISTEMAS ) GUIA DE LABORATORIO No. 3 PILAS Introducción: Con esta guía se estudiara en detalle las formas de implementar las estructuras de datos pila en diferentes lenguajes de programación. La pila es una estructura de datos que almacena y recupera sus elementosatendiendo un estricto orden. Las pilas se conocen también 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 laestructura en sus dos implementaciones: estático y dinámico, resolviendo algunos ejercicios. I Pilas en el Lenguaje C 1. Pruebe el siguiente programa, en el cual se muestra el uso de pila implementada utilizando un arreglo de 100 elementos. La función main() es una función sencilla en la cual se le da al usuario la oportunidad de introducir/sacar 5 elementos de la pila. /* PILAS.C */ #include#include #include #define TRUE 1 #define FALSE 0 #define STACKSIZE 100 /* definicion de tipos de datos */ typedef char STACKELEMENT; typedef struct { int top; STACKELEMENT items[STACKSIZE]; } STACK; /*prototipos de funciones de la pila */ void Clear(STACK *); int Empty(STACK *); int Full(STACK *); STACKELEMENT Pop(STACK *); void Push(STACK *, STACKELEMENT); void main() { STACKELEMENT a; int p, i;STACK b; STACK *c=&b; b.top=-1; clrscr(); PROGRAMACION II (SISTEMAS) 1 CICLO I/2009

/*da la oportunidad de introducir o sacar elementos de la pila 5 veces*/ for (i=0; itop= -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 */ intFull(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 PROGRAMACION II (SISTEMAS) 2 CICLO I/2009

ps->items[++(ps->top)]=x; } /* quita un elemento de la pila y lo devuelve */ STACKELEMENT Pop(STACK * ps) { if (Empty(ps)) {printf("%s","Pila subdesbordada"); exit(1); } return(ps->items[(ps->top)--]); } 2. Modifique el programa anterior para que la función main() sea mas flexible: que le de la oportunidad al usuario de escoger cuantas operaciones de pila desea realizar. 3. A continuación se tiene un programa que origina una línea de texto y utiliza una pila para imprimir la línea invertida. /*Programa que origina unalínea de texto y utilice una pila para imprimir la línea invertida.*/ #include #include #include #define MAXCOLS 80 #define TRUE 1 #define FALSE 0 struct stack { int tope; char elementos[MAXCOLS]; }; int empty(struct stack *); char pop(struct stack *); void push(struct stack *, char); 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; ielementos[ps->tope--]); } void push(struct stack *ps, char a) { if (ps->tope == MAXCOLS - 1) { printf("Desbordamiento de pila\n"); exit(1); } ps->elementos[++ps->tope]=a; } 4. Modifique el programa anterior para que también cuente el número de vocales que tiene la línea de texto. 5. Pruebe elsiguiente programa (use extensión .cpp) que hace una conversión de interfija a postfija. Los operandos validos son las letras de la A a la Z y los dígitos 0 a 9. Las operaciones validas solo incluyen división ( / ), multiplicación ( * ), suma ( + ) y resta ( - ). # include // por cout # include // por malloc(), free() # include // por clrscr() # include // por getchar() #define MAXCOLS 80...