1

Estrutura de Dados - Pilhas, Filas e Listas

Antônio Morais
Antônio Morais

O trabalho com pilhas, listas e filas pode ocorrer de forma estática ou dinâmica, contudo as listas ganham por sua versatilidade, fato que não ocorre com pilhas e listas que seguem princípios rígidos de entrada e saída de dados. Entre as operações realizadas, de maneira geral, nestas estruturas temos: inserção, exclusão, busca e recuperação.

A inserção/remoção de dados para pilhas e filas seguem princípios fixos de ordenamento. As filas têm como fundamento que o primeiro dado que entra é o primeiro que sai (FIFO – First In, First Out), já no caso das pilhas o último elemento que entra é o primeiro que sai (LIFO – Last In, First Out).

Segundo Forbellone e EberspäCher (2005, p. 166) “[...] pilhas, são listas na qual todas as inserções e remoções são feitas no final e possui a finalidade principal de tornar disponíveis primeiro os elementos mais recentes”. Percebe-se que apesar de serem chamadas de listas, as pilhas seguem um padrão fixo na entrada e saída de dados o que diferencia de outras estruturas.

Oliveira e Pereira (2019, p. 43) nos diz que “para se construir uma pilha, são necessários pelo menos três elementos: um vetor para armazenar os dados e dois números inteiros, um para marcar o início e outro para o final da pilha”. Para o empilhamento de dados devemos construir a estrutura e nesse quesito se faz necessário o uso de pelo menos um vetor e duas variáveis do tipo inteiro. Para as inserções e remoções usa-se uma variável que aponte para o topo da pilha.

Para Forbellone e EberspäCher (2005, p. 163) “[...] fila é uma lista em que as inserções são feitas no final e as remoções são feitas no início, e cuja finalidade principal é registrar a ordem de chegada de seus componentes.” A característica da fila está na ordem de chegada do dado, esta é que define a ordem das operações.

Schildt (1996, p. 540) afirma que

filas e pilhas compartilham duas características comuns: ambas têm regras muito rigoras para acessar os dados armazenados nelas e as operações de recuperação são, por natureza, destrutivas. Em outras palavras, acessar um item em pilha requer a sua remoção e, a menos que o item seja armazenado em outro lugar, ele é destruído. Além disso, tanto pilhas como filas usam uma região contígua de memória.

 

Percebe-se que a depender do problema a ser resolvido, deve-se optar por uma estrutura que melhor atenda a demanda. Quando se trata de estrutura fixa pode usar filas ou pilhas, caso queira mais versatilidade na manipulação dos dados, deve se optar por listas, que podem ser encadeadas, duplamente encadeadas ou circulares.

O autor ainda diz que

Diferentemente de uma pilha ou de uma fila, uma lista encadeada pode acessar seu armazenamento de forma randômica, porque cada porção de informação carrega consigo um elo ao próximo item de dado na corrente. Ou seja, uma lista encadeada exige uma estrutura complexa de dados – em oposição à pilha ou fila, que pode operar em itens de dados simples e complexos. Além disso, uma operação de recuperação em uma lista encadeada não remove e destrói um item da lista. Na verdade, você precisa acrescentar uma operação de exclusão específica para isso (SCHILDT, 1996, p. 540).

 

Entre as grandes vantagens no uso de listas encadeadas cita-se a busca aleatória por elementos que a compõe, como também o não destroímento do mesmo após sua remoção, fato que não ocorre nas estruturas de pilhas e filas. Isso ocorre porque cada item da lista possui ao menos dois elementos: sendo um o dado real e o outro um endereço que aponte para o próximo item. Além desses deve-se ter uma variável extra que aponte para o primeiro elemento da lista.

Para elucidar o exposto acima, segue um código em linguagem C com a realização dessas funções em uma pilha.

#include<stdio.h>

#include<stdlib.h>

#include<locale.h>

#define tamanho 8

 

typedef struct t_pilha{

   int dados[tamanho];

   int ini;

   int fim;

}tpilha;

 

tpilha pilha1;

tpilha pilha2;

int i;

 

void empilhar();

void desempilhar();

void mostrar();

 

 

int main() {

           setlocale(LC_ALL, "Portuguese");

   pilha1.ini= 0;

   pilha1.fim= 0;

   

   pilha2.ini= 0;

   pilha2.fim= 0;

  

   empilhar(1, &pilha1);

   empilhar(2, &pilha1);

   empilhar(3, &pilha1);

   empilhar(4, &pilha1);

   empilhar(5, &pilha1);

   empilhar(6, &pilha1);

   empilhar(7, &pilha1);

   empilhar(8, &pilha1);

   mostrar(&pilha1);

   desempilhar(&pilha2);

   empilhar(8, &pilha2);

   empilhar(7, &pilha2);

   empilhar(6, &pilha2);

   empilhar(5, &pilha2);

   empilhar(4, &pilha2);

   empilhar(3, &pilha2);

   empilhar(2, &pilha2);

   empilhar(1, &pilha2);

   mostrar(&pilha2);

       return 0;

}

void empilhar (int elemento, tpilha *p) {

                       if(p->fim == tamanho){

         printf("\nA pilha esta cheia, impossivel empilhar um novo elemento!\n\n");

       system("pause");       

   }

   else {

       p->dados[p->fim]= elemento;

         p->fim++;

   }

}

void mostrar(tpilha *p) {

   printf(" [ ");

   for(i= 0; i < tamanho; i++){

       printf("%d ", p->dados[i]);

   }

   printf("]\n\n");

}

void desempilhar(tpilha *p){

           int elemento;

           if (p->fim == p->ini) {

                       printf("*** Pilha vazia! ***\n\n");

                       //system("pause");

           }

           else {

                       elemento = p->dados[p->fim];

                       for(i=0; i<tamanho; i++){

                                   p->dados[i] = p->dados[i+1];

                       }

                       p->dados[i] = 0;

                       p->fim--;

           }

}


 

REFERÊNCIAS


FORBELLONE, André L. V.; EBERSPÄCHER, Henri F. Lógica de programação: a construção de algoritmos e estruturas de dados. 3. ed. São Paulo: Prentice Hall, 2005.


OLIVEIRA, Pietro M. de; PEREIRA, Rogério de L. Estrutura de dados I. Maringá: Unicesumar, 2019.


SCHILDT, Herbert. C, completo e total. 3. ed. São Paulo: Makron Books, 1996

 

 

 

0
11

Comentários (0)

Estudo sistemas para Internet. Sou pedagogo, escrevo de forma independente, já trabalhei como instrutor de informática em um projeto de cunho sócio digital. Trabalhei na educação por cerca de 10 anos.

Brasil