O objetivo dessa unidade é apresentar conteúdos relacionado às estruturas Pilha e Fila. Será feita uma abordagem focando na linguagem C.
As estruturas de dados do tipo pilha e fila podem ser consideradas listas especializadas por possuírem características particulares. Porém, possuem operações semelhantes, por exemplo, inserção de elemento, exclusão de elemento e impressão de elementos.
Podemos citar também que ambas representam conjuntos de dados organizados de maneira linear. Quando são representadas por vetores, tem-se o uso de endereços contíguos na memória e a ordem é determinada por seus índices. Neste caso, são chamadas de pilha e fila estáticas. Já quando são representadas por elementos alocados dinamicamente na memória e encadeados por ponteiros, têm-se representações denominadas pilhas e filas dinâmicas.
Aqui trataremos de pilhas e filas dinâmicas.
Pilha é uma estrutura do tipo FILO (First In Last Out), ou seja, o primeiro elemento inserido será o último a ser removido. Cada elemento da estrutura, pode armazenar um ou vários dados e um ponteiro para o próximo elemento, o que permite o encadeamento e mantêm uma estrutura linear.
Qualquer estrutura do tipo possui um ponteiro denominado TOPO, onde todas operações de inserção e remoção acontecem.
Serão abordadas as seguintes operações:
Para representarmos um elemento da pilha, será definido um registro da seguinte maneira:
/*registro que reprensentará cada elemento da pilha*/ struct Elemento{ int num; struct Elemento *prox; }; typedef struct Elemento Elemento;
Portanto, teremos uma pilha para o armazenamento de inteiros.
Para o controle da pilha utilizaremos uma estrutura do tipo Pilha. Ela contém um ponteiro do tipo No (topo), que irá armazenar o endereço de memória do elemento que estiver no topo da pilha (último elemento inserido).
/*registro do tipo Pilha contento um ponteiro "topo" do tipo Elemento para controlar a pilha*/ struct Pilha{ struct Elemento *topo; /*aponta para o elemento qu esta Elemento topo da pilha*/ }; typedef struct Pilha Pilha;
Para auxiliar em algumas funções, é necessário utilizar um ponteiro auxiliar do tipo No. Então definimos abaixo:
/*ponteiro auxiliar*/
Elemento *aux;
Nesse ponto definiremos também uma função cria_pilha( ). Ela será utilizada para criar uma pilha, ou seja, alocará dinamicamente o espaço necessário para armazenar seu ponteiro "topo" e irá inicializá-lo com NULL. Isso indica que inicialmente a pilha está vazia.
Pilha* cria_pilha(){
/*alocação do ponteiro pi para controlar a pilha*/
Pilha* pi = (Pilha*) malloc(sizeof(Pilha));
if(pi != NULL){
pi->topo = NULL; /*a pilha inicia-se vazia, portanto seu topo é igual a NULL*/
}
return pi;
}
Na função main, devemos definir um ponteiro do tipo Pilha. Ele irá receber o endereço do espaço alocado pela função cria_pilha( ) e também servirá de parâmetro para as demais funções seguintes.
int main(){ Pilha *pi = cria_pilha(); ...blocos de chamada de função... return 0; }
Esta é a implementação da função que utilizaremos para inserir um elemento na pilha.
/*todo elemento será inserido no topo da pilha*/ void insere_elemento(Pilha *pi){ /*a cada inserção alocamos dinamicamente um espaço para um novo elemento*/ Elemento *novo =(Elemento*) malloc(sizeof(Elemento)); printf("Digite o numero a ser inserido na pilha: "); scanf("%d",&novo->num); /*como o número inserido será o novo topo, ele apontará para o topo atual que será o segundo elemento da pilha*/ novo->prox = pi->topo; /*topo aponta para o endereço de novo*/ pi->topo = novo; printf("\nNumero inserido na pilha!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos o ponteiro topo apontado para null:
Agora inseriremos o número 8 na pilha.
Depois vamos inserir o número 3 na pilha.
Por fim, vamos inserir o número 6:
Para consultar os elementos da pilha e exibi-los, utilizaremos a seguinte função:
/*os elementos da pilha serão mostrados do último inserido(topo) ao primeiro*/ void consulta_pilha(Pilha *pi){ /*caso a pilha esteja vazia*/ if(pi->topo == NULL){ printf("\nPilha Vazia!!"); /*caso a pilha não esteja vazia*/ }else{ aux = pi->topo; do{ printf(" %d ", aux->num); aux = aux->prox; } while(aux != NULL); } getch(); }
A saída seria: 6 3 8.
Para removermos um elemento da pilha (este elemento será o último inserido), utilizaremos a seguinte função:
/*o elemento a ser removido será sempre o topo(último elemento inserido)*/ void remove_elemento_pilha(Pilha *pi){ if(pi->topo == NULL){ printf("\nPilha Vazia!!"); } else{ aux = pi->topo; printf("%d removido!", pi->topo->num); pi->topo = pi->topo->prox; free(aux); } getch(); }
Vamos então remover um elemento da pilha, como o último elemento inserido foi o 6, então será ele o removido:
Repetindo o processo, como 3 está no topo da pilha, então será ele o removido:
Nesta última operação esvaziaremos a nossa pilha, ou seja, removeremos todos os seus elementos restantes. Esta é a implementação utilizada:
/*a pilha será esvaziada e o espaço ocupado por ela será desalocado*/ void esvazia_pilha(Pilha *pi){ if(pi->topo == NULL){ printf("\nPilha Vazia!!"); }else{ aux = pi->topo; do{ pi->topo = pi->topo->prox; free(aux); aux = pi->topo; }while(aux != NULL); printf("\nPilha Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
Fila é uma estrutura do tipo FIFO (First In First Out), ou seja, o primeiro elemento inserido será o primeiro a ser removido. Cada elemento da estrutura pode armazenar um ou vários dados e um ponteiro para o próximo elemento, o que permite o encadeamento e mantêm uma estrutura linear.
A estrutura do tipo fila possui um ponteiro denominado INICIO, onde todas operações de remoção acontecem e outro denominado FIM, onde acontecem as inserções.
Serão abordadas as seguintes operações:
Para representarmos um elemento da Fila, será definido um registro da seguinte maneira:
/*registro que reprensentará cada elemento da pilha*/ struct Elemento{ int num; struct Elemento *prox; }; typedef struct Elemento Elemento;
Portanto, teremos uma fila para o armazenamento de inteiros.
Para o controle da fila utilizaremos uma estrutura do tipo Lista. Ela contém dois ponteiros do tipo No (inicio e fim), que irão armazenar os endereço de memória do primeiro e do último elemento da pilha respectivamente.
/*registro do tipo Fila contento dois ponteiros do tipo nó para controlar a fila*/ struct Fila{ struct Elemento *inicio; /*aponta para o elemento do início da fila*/ struct Elemento *fim; /*aponta para o elemento do fim da fila*/ }; typedef struct Fila Fila;
Para auxiliar em algumas funções, é necessário utilizar um ponteiro auxiliar do tipo No. Então definimos abaixo:
/*ponteiro auxiliar*/
Elemento *aux;
Nesse ponto definiremos também uma função cria_fila( ). Ela será utilizada para criar uma fila, ou seja, alocará dinamicamente o espaço necessário para armazenarseus ponteiros (inicio e fim) e irá inicializá-los com NULL. Isso indica que inicialmente a fila esta vazia.
Fila* cria_fila(){
/*alocação do ponteiro li para controlar a lista*/
Fila* fi = (Fila*) malloc(sizeof(Fila));
if(fi != NULL){
/*a fila inicia-se vazia, portanto inicio e fim são iguais a NULL*/
fi->fim = NULL;
fi->inicio = NULL;
}
return fi;
}
Na função main, devemos definir um ponteiro do tipo Fila. Ele irá receber o endereço do espaço alocado pela função cria_fila( ) e também servirá de parâmetro para as demais funções seguintes.
int main(){ Fila *fi = cria_fila(); ...blocos de chamada de função... return 0; }
Esta é a implementação da função que utilizaremos para inserir um elemento na fila.
void insere_elemento(Fila *fi){ /*a cada inserção alocamos dinamicamente um espaço para um novo elemento*/ Elemento*novo =(Elemento*) malloc(sizeof(Elemento)); printf("Digite o numero a ser inserido na fila: "); scanf("%d",&novo->num); novo->prox = NULL; /*caso a fila esteja vazia, o elemento inserido será o primeiro e o último */ if(fi->inicio == NULL){ fi->inicio = novo; fi->fim = novo; /*caso a pilha ja contenha algum elemento, o novo elemento será sempre inserido no fim da fila*/ }else{ fi->fim->prox = novo; fi->fim = novo; } printf("\nNumero inserido na fila!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos um ponteiro inicio e fim apontados para null:
Agora inseriremos o número 4 na fila.
Depois vamos inserir o número 9 na fila.
Por fim, vamos inserir o número 7:
Para consultar os elementos da fila e exibi-los (serão exibidos do ínicio para o fim), utilizaremos a seguinte função:
/*os elementos da fila serão mostrados do primeiro inserido(inicio) ao último (fim)*/ void consulta_fila(Fila *fi){ if(fi->inicio == NULL){ printf("\nFila Vazia!!"); }else{ aux = fi->inicio; do{ printf(" %d ", aux->num); aux = aux->prox; } while(aux != NULL); } getch(); }
A saída seria: 4 9 7.
Para removermos um elemento da pilha (este elemento será o primeiro inserido), utilizaremos a seguinte função:
/*o elemento a ser removido será sempre o primeiro elemento inserido(inicio)*/ void remove_elemento_fila(Fila *fi){ if(fi->inicio == NULL){ printf("\nFila Vazia!!"); }else{ aux = fi->inicio; printf("%d removido!", fi->inicio->num); fi->inicio = fi->inicio->prox; free(aux); } getch(); }
Vamos então remover um elemento da pilha, como o primeiro elemento inserido foi o 4, então será ele o removido:
Repetindo o processo, como 9 foi o penúltimo elemento a ser inserido, então será ele o removido:
Nesta última operação esvaziaremos a nossa fila, ou seja, removeremos todos os seus elementos restantes. Esta é a implementação utilizada:
/*a fila será esvaziada e o espaço ocupado por ela será desalocado*/ void esvazia_fila(Fila *fi){ if(fi->inicio == NULL){ printf("\nFila Vazia!!"); }else{ aux = fi->inicio; do{ fi->inicio = fi->inicio->prox; free(aux); aux = fi->inicio; }while(aux != NULL); printf("\nFila Esvaziada!!"); } getch(); }
O resultado final após essa operação seria esse:
