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 Pilha { 
  No Dados[TAM]; 
struct No {    int Topo; 
  char Chave;  }; 
  int Valor; 
}; 

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).