Pilha_e_Fila

Prévia do material em texto

Universidade Federal de Itajubá – UNIFEI
Campus Itabira
Capítulo 3
Pilhas e Filas
2º Semestre de 2016
Sandro Carvalho Izidoro
1 Considerações Iniciais
Existem determinadas estruturas de dados que não utilizam de ordem para 
organizar seus dados. Para determinadas aplicações é imposto um critério que restringe a 
inserção e retirada dos elementos que compõem um conjunto de dados, ou seja, são 
definidas disciplinas de acessos. 
Disciplina de acesso é a forma pela qual os elementos de uma determinada 
estrutura de dados serão inseridos e retirados desta estrutura. Os dois critérios mais 
usuais são: 
• LIFO (Last In First Out): dentre os elementos que ainda permanecem no conjunto, 
o primeiro a ser retirado é o ultimo que tiver sido inserido. Este critério é utilizado na 
estrutura de dados denominada Pilha. 
• FIFO (First In First Out): dentre os elementos que ainda permanecem no conjunto, 
o primeiro elemento a ser retirado é o primeiro que tiver sido inserido. Esse critério 
caracteriza a estrutura de dados Fila. 
2 Pilha 
Uma Pilha é uma estrutura linear de dados que pode ser acessada somente por 
uma de suas extremidades para armazenar e recuperar dados. Ela é como uma pilha de 
bandejas em uma lanchonete: bandejas são colocadas e retiradas do topo da pilha. A 
última bandeja colocada é a primeira bandeja removida da pilha [1]. 
Pode-se pegar uma bandeja somente se existirem bandejas na pilha, e uma 
bandeja pode ser adicionada à pilha somente se houver espaço suficiente, isto é, se a 
pilha não estiver muito alta. 
Assim, uma pilha é definida em termos das operações que modificam e das que 
verificam seus status. As operações são as seguintes: 
Estrutura de Dados – Capítulo 3 – 2
• IniciarPilha - Limpa a pilha; 
• PilhaVazia - Verifica se a pilha está vazia; 
• PilhaCheia - Verifica se há espaço para inserir novos elementos na pilha;
• Empilha - Insere um novo elemento na pilha; 
• Desempilha - Retira um elemento da pilha (o elemento mais alto da pilha); 
• TopoPilha - Retorna o elemento mais alto da pilha sem removê-lo. 
Da mesma forma que a estrutura de dados lista, pode-se implementar uma pilha 
usando dois recursos básicos das linguagens de programação: 
1. Vetor; 
2. Alocação dinâmica de memória.
2.1 Implementação de Pilha usando vetor 
Para implementar uma pilha através de uma estrutura estática, além do vetor onde 
serão armazenados os elementos da pilha, será necessário uma variável inteira que 
sinalize a posição do último elemento inserido, ou seja, o topo da pilha. A definição desta 
estrutura é semelhante àquela utilizada na lista estática sequencial, conforme declaração 
a seguir: 
#define TAM 10 
struct No { 
  char Chave; 
  int Valor; 
}; 
struct Pilha { 
  No Dados[TAM]; 
  int Topo; 
}; 
Para iniciar esta estrutura, basta atribuir o valor -1 para o campo Topo. Geralmente, 
a pilha é muito útil nas situações em que os dados tem que ser armazenados e então 
recuperados na ordem inversa. Uma aplicação da pilha é o casamento de delimitadores 
em um programa. Esse é um exemplo importante, porque o casamento de delimitadores é 
parte de qualquer compilador: nenhum programa é considerado correto se os 
delimitadores não estão casados. Outra característica desta estrutura é a simplicidade 
dos códigos utilizados para implementar as primitivas. Isto pode ser observado nas 
primtivas de inserção e remoção a seguir: 
Estrutura de Dados – Capítulo 3 – 3
bool Empilha (Pilha& P, No Novo) { 
  if (P.Topo == TAM ­ 1) 
     return false; 
   P.Dados[++P.Topo] = Novo; 
   return true; 
} 
bool Desempilha (Pilha& P, No& Novo) { 
   if (P.Topo == ­1) 
     return false; 
   Novo = P.Dados[P.Topo­­]; 
   return true; 
} 
2.2 Implementação de Pilha usando alocação dinâmica 
Neste tipo de implementação não há necessidade da primitiva PilhaCheia, uma vez 
que, teoricamente, toda memória está disponível para a alocação. 
As primitivas de inserção e remoção são descritas a seguir: 
typedef No * Pilha; 
void Empilha (Pilha& Topo, char Elemento) { 
   No *Aux = new No; 
   Aux­>Info = Elemento; 
   Aux­>Lig = Topo; 
   Topo = Aux; 
} 
bool Desempilha (Pilha& Topo, char& Elemento) { 
   if (Topo == NULL) 
       return false; 
   Elemento = Topo­>Info; 
   No *Aux = Topo; 
   Topo = Topo­>Lig; 
   delete Aux; 
   return true; 
} 
Estrutura de Dados – Capítulo 3 – 4
2.3 Exemplo de aplicação de Pilha: Notação Polonesa 
Uma representação para expressões aritméticas, que seja conveniente do ponto de 
vista computacional, é assunto de interesse, por exemplo, na área de compiladores. A 
notação tradicional é ambígua e, portanto, obriga ao preestabelecimento de regras de 
prioridade. Isso, naturalmente, torna a tarefa computacional menos simples. Outras 
representações são apresentadas a seguir, considerando-se somente operações binárias 
[2]. 
• Notação completamente parentizada: acrescenta-se sempre um par de 
parênteses a cada par de operandos e a seu operador. Exemplo: 
Notação tradicional: A B − C/D ∗
Notação parentizada: ((A B) − (C/D)) ∗
• Notação polonesa: os operadores aparecem imediatamente antes dos operandos. 
Esta notação explicita quais operadores, e em que ordem, devem ser calculados. Por 
esse motivo, dispensa o uso de parênteses, sem ambiguidades. Exemplo: 
Notação tradicional: A B − C/D ∗
Notação polonesa: − AB/CD ∗
• Notação polonesa reversa (ou pósfix): é semelhante a notação polonesa, porém 
os operadores aparecem após os operandos. Esta notação é tradicionalmente utilizada 
em máquinas de calcular. Exemplo: 
Notação tradicional: A B − C/D ∗
Notação polonesa: AB CD/− ∗
Tanto a expressão original quando a expressão transformada devem ser 
armazenadas em listas. Um método para efetuar a conversão da notação parentizada na 
notação polonesa reversa é apresentado a seguir [2]. Algumas observações auxiliam em 
tal conversão: 
• Os operandos aparecem na mesma ordem na notação tradicional e na notação 
polonesa reversa;
• Na notação polonesa reversa, os operadores aparecem na ordem em que devem 
ser calculados (da esquerda para a direita); 
• Os operadores aparecem imediatamente depois de seus operandos. 
Nota-se que, pela primeira observação, a ordem dos operandos não se modifica, 
podendo estes ser ignorados. A principal preocupação do algoritmo deve ser a ordem e a 
posição dos operadores. Na notação parentizada, essa ordem é indicada pelos 
parênteses; os mais internos significam operações prioritárias. 
Estrutura de Dados – Capítulo 3 – 5
Pressupõem-se que foi realizada uma análise sintática prévia na expressão. Para 
efetuar a conversão, devem-se remover os parênteses e estabelecer a ordem 
conveniente de operadores. Estes então devem ser armazenados até que um “)” seja 
encontrado, o que indica que a operação mais interna, e, por conseguinte, a primeira a 
ser executada, foi detectada. O último operador armazenado corresponde a essa 
operação. Portanto, a estrutura utilizada no armazenamento dos operadores deve ser 
uma pilha. 
No código a seguir, a expressão a ser convertida se encontra no vetor Expressão e 
o resultado da conversão, no vetor Polonesa. O parâmetro Tam indica a dimensão da 
expressão e o parâmetro Operandos contém os símbolos que representam operandos 
válidos. Na variável Expressao os caracteres que não forem símbolos representão 
necessariamente, variáveis da expressão. 
bool   Conversor(char   *Expressao,   char   *Polonesa,   int   Tam,   char 
*Operadores) { 
  Pilha P; 
  IniciaPilha (P); 
  char Operador; 
  int IndicePol = 0; 
  for (int i=0; i < Tam; i++)  { 
       if (!strchr(Operadores, Expressao[i])) 
           Polonesa[++IndicePol]= Expressao[i]; 
       else if ((Expressao[i] != ’(’) && (Expressao[i] != ’)’)) 
                   Empilha(P, Expressao[i]); 
               else if (Expressao[i] == ’)’) { 
                          if (Desempilha(P, Operador)) 
                              Polonesa[++IndicePol] = Operador; 
                          else 
                              return false; 
                       } 
  } 
  Polonesa[++IndicePol] = ’\0’; 
  return true; 
} 
3 Fila 
Uma Fila é simplesmente uma linha de espera que cresce somando elementos ao 
seu final e que diminui tomando elementos de sua frente. Diferente de uma pilha, uma fila 
é uma estrutura na qual ambas as extremidades são usadas: uma para adicionar novos 
elementos e outra para removê-los. Em consequência, o último elemento tem que esperar 
até que todos os elementos que o precedem na fila sejam removidos [1]. 
As operações das filas são similares às operações das pilhas. As seguintes 
operações são necessárias para gerenciar apropriadamente uma fila: 
Estrutura de Dados – Capítulo 3 – 6
• IniciarFila - Limpa a fila; 
• FilaVazia - Verifica se a fila está vazia; 
• FilaCheia - Verifica se há espaço para inserir novos elementos na fila; 
• InsereFila - Insere um novo elemento na fila; 
• RetiraFila - Retira um elemento da fila; 
• Primeiro - Retorna o primeiro elemento da fila sem removê-lo. 
3.1 Implementação de Fila usando vetor 
Da mesma forma que as estruturas anteriores, pode-se implementar uma fila 
usando vetor ou alocação dinâmica de memória. 
Como na implementação por vetor da estrutura pilha, os elementos são 
adicionados ao final da fila, mas, como as posições liberadas durante a operação de 
remoção devem ser reaproveitadas, o final da fila pode ocorrer antes da posição de início 
da fila dentro do vetor. Esta situação é mais bem visualizada como uma matriz circular, 
como ilustra a figura 1c. A fila está cheia se o primeiro elemento imediatamente precede 
na direção anti-horária o último elemento. 
No entanto, como uma matriz circular é implementada com um vetor “normal”, a fila 
está cheia tanto se o primeiro elemento está na primeira célula e o último elemento na 
ultima (figura 1a) como se o primeiro elemento está logo depois do último (figura 1b). 
Similarmente, InsereFila e RetiraFila tem que considerar a possibilidade de fechar a 
matriz quando se está adicionando ou removendo os elementos. 
Por exemplo, InsereFila pode ser vista como operando em uma matriz circular 
(figura 1c), mas na realidade está operando em um vetor unidimensional. Em 
consequência, se o ultimo elemento está na ultima célula e se quaisquer células estão 
disponíveis no início da matriz, um novo elemento é colocado lá (figura 1d). Se o último 
elemento está em qualquer outra posição, então o novo elemento é colocado depois do 
último, se houver espaço (figura 1e). Essas duas situações precisam ser reconhecidas 
quando se implementa uma fila vista como uma fila circular. 
Estrutura de Dados – Capítulo 3 – 7
Figura 1: Situações em uma implementação de fila circular 
O código a seguir descreve uma implementação de fila circular. Para facilitar o 
teste de fila vazia e fila cheia, um campo Tam foi adiconado à estrutura para armazenar a 
quantidade de elementos da fila. 
Estrutura de Dados – Capítulo 3 – 8
struct Fila { 
   No Dados[T]; 
   int Tam; 
   int Com; 
   int Fim; 
}; 
bool InsereFila (Fila& F, No Novo) { 
   if (F.Tam == T) 
      return false; 
   F.Tam++; 
   F.Fim = (F.Fim + 1) % T; 
   F.Dados[F.Fim] = Novo; 
   return true; 
} 
bool RetiraFila (Fila& F, No& Novo) { 
  if (F.Tam == 0) 
     return false; 
  F.Tam­­; 
  Novo = F.Dados[F.Com]; 
  F.Com = (F.Com + 1) % T; 
  return true; 
} 
3.2 Implementação de Fila usando alocação dinâmica 
A implementação utilizando alocação dinâmica de memória pode ser realizada com 
o uso de um descritor que indica o ponteiro para o início e o fim da fila. 
A seguir as primitivas de inserção e remoção em fila por alocação dinâmica de 
memória: 
struct Fila { 
   NoPtr Com; 
   int Nro; 
   NoPtr Fim; 
}; 
void InsereFila (Fila& D, char Novo) { 
   NoPtr P = new No; 
   P­>Info = Novo; 
   P­>Lig = NULL; 
   if (D.Nro == 0) 
        D.Com = D.Fim = P; 
    else { 
Estrutura de Dados – Capítulo 3 – 9
         D.Fim­>Lig = P; 
         D.Fim = P; 
    } 
    D.Nro++; 
} 
bool RetiraFila (Fila& D, char& Valor) { 
   if (D.Nro == 0) 
       return false; 
   else { 
       NoPtr P = D.Com; 
       Valor = P­>Info; 
       D.Com = P­>Lig; 
       D.Nro­­; 
       if (D.Nro == 0) 
           D.Fim = NULL; 
      delete P; 
      return true; 
  } 
} 
 
4 Exercícios 
1. Implemente as primitivas PilhaVazia e TopoPilha (Utilizando vetor e ponteiro).
2. Implemente as rotinas Empilha, Desempilha, PilhaVazia e PilhaCheia para uma pilha de 
inteiros usando um vetor P[100], onde P[0] é usado como ponteiro de topo da pilha, 
ao invés do ponteiro Topo e P[1] até P[100] contém os elementos da pilha. Qual a 
desvantagem neste tipo de implementação?
3. Faça uma função para colocar os elementos de uma pilha S na ordem ascendente, 
usando uma pilha adicional. 
4. Faça funções para inverter a ordem dos elementos na pilha S: 
(a) usando duas pilhas adicionais; 
(b) usando uma fila adicional. 
Estrutura de Dados – Capítulo 3 – 10
5 Referências
[1] Adam Drozdek. Estrutura de Dados e Algoritmos em C++. Pioneira Thomson Learning, 
São Paulo, 2002. 
[2] Jayme Luiz Szwarcfiter and Lilian Markenzon. Estruturas de Dados e Seus Algoritmos. 
LTC Editora, Rio de Janeiro, 1994. 
Observações
Material elaborado a partir das notas de aula do professor Edmilson Marmo Moreira 
(UNIFEI).
	1 Considerações Iniciais
	2 Pilha
	2.1 Implementação de Pilha usando vetor
	2.2 Implementação de Pilha usando alocação dinâmica
	2.3 Exemplo de aplicação de Pilha: Notação Polonesa
	3 Fila
	3.1 Implementação de Fila usando vetor
	3.2 Implementação de Fila usando alocação dinâmica
	4 Exercícios
	5 Referências