Exemplo de aplicação dos tipos abstratos de dados Pilha e Fila

Prévia do material em texto

Resolução da 10ª questão 10 da 9ª lista
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define TRUE 1
#define FALSE 0
typedef struct carro {
 char placa [8];
 int qtdManobras;
} TCarro;
typedef struct no {
 TCarro info;
 struct no * prox;
} TNo;
typedef struct descritor {
 TNo *inicio, *fim;
} TDescritor;
typedef struct descritorPark {
 TNo *inicio, *fim;
 int qtdCarros;
} TDescritorPark;
typedef TNo * Stack;
typedef TDescritor * Queue;
typedef TDescritorPark * Park;
// implementação do tipo de dados Stack para usar como espaço de manobra do estacionamento
int isEmptyStack (Stack p) { // teste se a pilha está vazia
 if (p == NULL)
 return TRUE;
 else
 return FALSE;
}
void push (Stack * p, TCarro c) { // empilhar um valor, ou seja, insere no topo da pilha
 TNo * novo;
 novo = (TNo *) malloc (sizeof (TNo));
 novo->info = c;
 if (isEmptyStack (*p) == TRUE) 
 novo->prox = NULL;
 else
 novo->prox = *p;
 *p = novo;
}
TCarro pop (Stack * p) { // desempilha, ou seja, retira o valor situado no topo da pilha
 TCarro c;
 TNo * aux;
 aux = *p;
 *p = (*p)->prox;
 c = aux->info;
 free (aux);
 return c;
}
TCarro top (Stack p) {
 return p->info;
}
void initializeStack (Stack *p) {
 *p = NULL;
}
// fim implementação de stack
// implementação do tipo de dados Queue para usar como fila de espera do estacionamento
int isEmptyQueue (Queue fila) {
 if (fila->inicio == NULL)
 return TRUE;
 else
 return FALSE;
}
void enqueue (Queue fila, TCarro c) {
 TNo * novo;
 novo = (TNo *) malloc (sizeof (TNo));
 novo->info = c;
 novo->prox = NULL;
 if (isEmptyQueue (fila) == TRUE)
 fila->inicio = novo;
 else 
 fila->fim->prox = novo;
 fila->fim = novo;
}
TCarro dequeue (Queue fila) {
 TNo * aux;
 TCarro c;
 aux = fila->inicio;
 fila->inicio = fila->inicio->prox;
 if (isEmptyQueue (fila) == TRUE)
 fila->fim = NULL;
 c = aux->info;
 free (aux);
 return c;
}
TCarro head (Queue fila) {
 return fila->inicio->info;
}
void initializeQueue (Queue * fila) {
 *fila = (TDescritor *) malloc (sizeof (TDescritor));
 (*fila)->inicio = NULL;
 (*fila)->fim = NULL;
}
// fim implementação de Queue
// implementação do estacionamento como uma lista com nó descritor
int isEmptyPark (Park e) {
 if (e->qtdCarros == 0)
 return TRUE;
 else
 return FALSE;
}
int isFullPark (Park e) {
 if (e->qtdCarros == 10)
 return TRUE;
 else
 return FALSE;
}
void retornar (Park e, TCarro c) { // inserir no inicio do estacionamento
 TNo * novo;
 novo = (TNo *) malloc (sizeof (TNo));
 novo->info = c;
 if (isEmptyPark (e) == TRUE) {
 e->inicio = novo;
 e->fim = novo;
 }
 else {
 novo->prox = e->inicio;
 e->inicio = novo;
 }
 (e->qtdCarros)++;
}
void estacionar (Park e, TCarro c) { // inserir no final 
 TNo * novo;
 novo = (TNo *) malloc (sizeof (TNo));
 novo->info = c;
 novo->prox = NULL;
 if (isEmptyPark (e) == TRUE)
 e->inicio = novo;
 else 
 e->fim->prox = novo;
 e->fim = novo;
 (e->qtdCarros)++;
}
TCarro retirar (Park e) { // retirar carro do estacionamento
 TNo * aux;
 TCarro c;
 aux = e->inicio;
 e->inicio = e->inicio->prox;
 if (isEmptyPark (e) == TRUE)
 e->fim = NULL;
 c = aux->info;
 c.qtdManobras++;
 free (aux);
 (e->qtdCarros)--;
 return c;
}
int manobrar (Park e, char pl[]) {
 TCarro c;
 Stack pilhaManobra;
 initializeStack (&pilhaManobra);
 while (isEmptyPark (e) == FALSE) {
 c = retirar (e);
 if (strcmp(c.placa,pl) == 0) {
 printf ("O carro de placa %s esta saindo. Foi manobrado %i vezes \n",c.placa, c.qtdManobras);
 while (isEmptyStack (pilhaManobra) != TRUE) {
 c = pop(&pilhaManobra);
 retornar (e,c);
 }
 return 1; // se saiu carro
 }
 else
 push (&pilhaManobra,c);
 }
 printf ("O carro de placa %s nao se encontra no estacionamento \n",pl);
 while (isEmptyStack (pilhaManobra) != TRUE) {
 c = pop(&pilhaManobra);
 retornar (e,c);
 } 
 return 0; // se nao saiu carro
}
TCarro primeiro (Park e) {
 return e->inicio->info;
}
void initializePark (Park * e) {
 *e = (TDescritorPark *) malloc (sizeof (TDescritorPark));
 (*e)->inicio = NULL;
 (*e)->fim = NULL;
 (*e)->qtdCarros = 0;
}
int main () {
 Park estacione;
 Queue filaEspera;
 char op, resp;
 TCarro car;
 int vaga;
 initializePark (&estacione);
 initializeQueue (&filaEspera);
 do {
 printf ("1 - Estacionar \n2 - Retirar carros \n3 - Sair do programa \n");
 printf ("Digite a opcao: ");
 op = getchar (); fflush (stdin);
 switch (op) {
 case '1': printf ("Informe a placa do carro: ");
 fgets(car.placa,7,stdin); fflush (stdin);
 if (isFullPark (estacione) == FALSE) {
 car. qtdManobras = 0;
 estacionar (estacione,car);
 }
 else {
 printf ("Deseja esperar uma vaga? (S/N) ");
 resp = toupper (getchar ()); fflush (stdin);
 while (resp != 'S' && resp != 'N') {
 printf ("Digite S ou N: ");
 resp = toupper (getchar ()); fflush (stdin);
 }
 if (resp == 'S') {
 car. qtdManobras = 0;
 enqueue (filaEspera,car);
 }
 }
 break;
 case '2': printf ("Informe a placa do carro: ");
 fgets(car.placa,7,stdin); fflush (stdin);
 if (isEmptyPark (estacione) == TRUE) 
 printf ("Estacionamento vazio \n");
 else {
 vaga = manobrar (estacione,car.placa);
 if (vaga == 1 && isEmptyQueue(filaEspera) == FALSE) {
 car = dequeue (filaEspera);estacionar (estacione,car);
 }
 }
 break;
 case '3': while (isEmptyQueue (filaEspera) == FALSE)
 dequeue (filaEspera);
 while (isEmptyPark (estacione) == FALSE)
 retirar (estacione);
 break;
 default: printf ("opcao invalida \n");
 }
 } while (op != '3');
 return 0;
}