Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Pilhas

Uma pilha é uma estrutura de dados que admite remoção de elementos e inserção de novos objetos.  Mais especificamente, uma  pilha (= stack)  é uma estrutura sujeita à seguinte regra de operação:  sempre que houver uma remoção,

o elemento removido é o que está na estrutura há menos tempo.

Em outras palavras, o primeiro objeto a ser inserido na pilha é o último a ser removido. Essa política é conhecida pela sigla LIFO (= Last-In-First-Out).

Implementação em um vetor

Suponha que nossa pilha está armazenada em um vetor  pilha[0..N-1].  (A natureza dos elementos do vetor é irrelevante: eles podem ser inteiros, bytes, ponteiros, etc.)  Digamos que a parte do vetor ocupada pela pilha é

pilha[0..t-1] .

O índice t indica a primeira posição vaga do vetor e t-1 é o índice do topo da pilha.  A pilha está vazia se t vale 0 e cheia se t vale N.  No exemplo da figura, os caracteres A, B, … , H foram inseridos na pilha nessa ordem:

Para remover, ou tirar, um elemento da pilha — essa operação é conhecida como desempilhar (= to pop) — faça

   x = pilha[--t];

Isso equivale ao par de instruções  t -= 1;  x = pilha[t];.  É claro que você só deve desempilhar se tiver certeza de que a pilha não está vazia.

Para inserir, ou colocar, um objeto y na pilha — a operação é conhecida como empilhar (= to push) — faça

   pilha[t++] = y;  

Isso equivale ao par de instruções  pilha[t] = y;  t += 1;.  Antes de empilhar, certifique-se de que a pilha não está cheia, para evitar um transbordamento (= overflow). 

Para facilitar a leitura do código, é conveniente embalar essas operações em duas pequenas funções. Se os objetos com que estamos lidando são do tipo char, podemos escrever

char desempilha (void) {
   return pilha[--t];
}

void empilha (char y) {
   pilha[t++] = y;
}

Estamos supondo aqui que as variáveis pilha e t são globais, ou seja, foram definidas fora do código das funções.  Para completar o pacote, precisaríamos de mais três funções: uma que crie uma pilha, uma que verifique se a pilha está vazia e uma que verifique se a pilha está cheia. (Veja exercício abaixo.)

Exercícios 1

Aplicação: parênteses e colchetes

Considere o problema de decidir se uma dada sequência de parênteses e colchetes está bem-formada (ou seja, parênteses e colchetes são fechados na ordem inversa àquela em que foram abertos).  Por exemplo, a sequência

está bem-formada, enquanto   ( [ ) ]   está malformada.  Suponha que a sequência de parênteses e colchetes está armazenada em uma string ASCII  s.  (Como é hábito em C, o último caractere da string é \0.)

Usaremos uma pilha para resolver o problema.  O algoritmo é simples: examine a string da esquerda para a direita e empilhe os parênteses e colchetes esquerdos à espera de que apareçam os correspondentes parênteses e colchetes direitos. (Veja pseudocódigo.)

Para simplificar, as variáveis pilha e t serão globais.  Suporemos também que o tamanho N do vetor que abriga a pilha é maior que o tamanho da string e portanto a pilha jamais transborda.

#define N 100
char pilha[N];
int t;

// Esta função devolve 1 se a string ASCII s 
// contém uma sequência bem-formada de 
// parênteses e colchetes; devolve 0 se 
// a sequência é malformada.

int bemFormada (char s[]) 
{
   criapilha ();
   for (int i = 0; s[i] != '\0'; ++i) {
      char c;
      switch (s[i]) {
         case ')': if (pilhavazia ()) return 0;
                   c = desempilha ();
                   if (c != '(') return 0;
                   break;
         case ']': if (pilhavazia ()) return 0;
                   c = desempilha ();
                   if (c != '[') return 0;
                   break;
         default:  empilha (s[i]);
      }
   }
   return pilhavazia ();
}

void criapilha (void) {
   t = 0;
}

void empilha (char y) {
   pilha[t++] = y;
}

char desempilha (void) {
   return pilha[--t];
} 

int pilhavazia (void) {
   return t <= 0;
}

(Poderíamos operar a pilha diretamente, sem invocar as funções de manipulação da pilha. O resultado seria bem mais curto e compacto, mas um pouco menos legível.)

Exercícios 2

Outra aplicação: notação polonesa

Na notação usual de expressões aritméticas, os operadores são escritos entre os operandos;  por isso, a notação é chamada infixa.  Na notação posfixa, ou polonesa, os operadores são escritos depois dos operandos.  Eis alguns exemplos de expressões infixas e correspondentes expressões posfixas:

Note que os operandos (A, B, C, etc.) aparecem na mesma ordem na expressão infixa e na correspondente expressão posfixa.  Note também que a notação posfixa dispensa parênteses e regras de precedência entre operadores (como a precedência de * sobre + por exemplo), que são indispensáveis na notação infixa.

Nosso problema:  traduzir para notação posfixa a expressão infixa armazenada em uma string inf.  Para simplificar nossa vida, vamos supor que

• a expressão inf é válida e contém apenas letras ASCII, parênteses, e os símbolos das quatro operações aritméticas,
• os nomes das variáveis têm apenas uma letra cada,
• todas as operações (em particular - e +) têm dois operandos,
• a expressão inf está embrulhada em um par de parênteses (ou seja, o primeiro caractere da string é '(' e os dois últimos são ')' e '\0').

O algoritmo lê a expressão inf caractere-a-caractere e usa uma pilha para fazer a tradução.  Todo parêntese esquerdo é colocado na pilha. Ao encontrar um parêntese direito, o algoritmo desempilha tudo até encontrar um parêntese esquerdo, que também é desempilhado. Ao encontrar um + ou um - , o algoritmo desempilha tudo até encontrar um parêntese esquerdo, que não é desempilhado. Ao encontrar um * ou um / , o algoritmo desempilha tudo até encontrar um parêntese esquerdo ou um + ou um - .  Constantes e variáveis são transferidos diretamente de inf para a expressão posfixa.  (Veja um rascunho em pseudocódigo.)

As variáveis pilha e t são globais.  Vamos supor que N é maior que o tamanho da string inf, e portanto não precisamos nos preocupar com pilha cheia.  Como a expressão inf está embrulhada em parênteses, não precisamos nos preocupar com pilha vazia.

#define N 100
char pilha[N];
int t;

// Esta função recebe uma expressão infixa inf
// e devolve a correspondente expressão posfixa.

char *infixaParaPosfixa (char *inf) {
   int n = strlen (inf);
   char *posf; 
   posf = malloc ((n+1) * sizeof (char));
   criapilha ();
   empilha (inf[0]);       // empilha '('

   int j = 0;
   for (int i = 1; inf[i] != '\0'; ++i) {
      switch (inf[i]) {
         char x;
         case '(': empilha (inf[i]);
                   break;
         case ')': x = desempilha ();
                   while (x != '(') {
                      posf[j++] = x;
                      x = desempilha ();
                   }
                   break;
         case '+': 
         case '-': x = desempilha ();
                   while (x != '(') {
                      posf[j++] = x;
                      x = desempilha ();
                   }
                   empilha (x);
                   empilha (inf[i])
                   break;
         case '*':
         case '/': x = desempilha ();
                   while (x != '(' && x != '+' && x != '-') {
                      posf[j++] = x;
                      x = desempilha ();
                   }
                   empilha (x);
                   empilha (inf[i]);
                   break;
         default:  posf[j++] = inf[i];
      }
   }
   posf[j] = '\0';      
   return posf;
}  

(Poderíamos operar a pilha diretamente, sem invocar as funções de manipulação da pilha. O resultado seria mais curto e compacto, mas um pouco menos legível.)

Veja o resultado da aplicação da função infixaParaPosfixa à expressão infixa  (A*(B*C+D)). A tabela registra os valores das variáveis no início de cada iteração:

Exercícios 3

Implementação em vetor com redimensionamento

Nem sempre é possível prever a quantidade de espaço que uma pilha vai usar. Se a pilha residir num vetor, podemos recorrer ao redimensionamento sempre que a pilha ficar cheia, como já fizemos ao implementar uma fila.

Exercícios 4

Pilha implementada em uma lista encadeada

Como implementar uma pilha em uma lista encadeada?  Digamos que os elementos da pilha são caracteres ASCII e que as células da lista são do tipo celula (veja Estrutura de uma list ligada):

typedef struct celula {
   char           conteudo; 
   struct celula *prox;
} celula;

Decisões de projeto: 1. Nossa lista terá uma célula-cabeça (e portanto a primeira célula da lista não fará parte da pilha).  2. O topo da pilha ficará na segunda célula e não na última (por quê?).  3. Uma variável global pi apontará a cabeça da lista.

As funções de criação e manipulação da pilha podem então ser escritas assim:

celula *pi;

void criapilha (void) {
   pi = malloc (sizeof (celula)); // cabeça
   pi->prox = NULL; 
}

void empilha (char y) { 
   celula *nova;
   nova = malloc (sizeof (celula));
   nova->conteudo = y;
   nova->prox  = pi->prox;
   pi->prox = nova; 
}

char desempilha (void) {
   celula *p;
   p = pi->prox;
   char x = p->conteudo;
   pi->prox = p->prox;
   free (p);
   return x; 
}

(Como de hábito, a função desempilha não deve ser invocada se a pilha estiver vazia.)

Exercícios 5

Apêndice: A pilha de execução de um programa

Todo programa C consiste em uma ou mais funções  (sendo main a primeira função a ser executada).  Para administrar as invocações das funções, o computador (ou melhor, o sistema operacional) usa uma pilha de execução.  (Veja o verbete Call stack na Wikipedia.)  A operação pode ser descrita conceitualmente da seguinte maneira.

Ao encontrar a invocação de uma função, o computador cria um novo espaço de trabalho, que contém todos os parâmetros e todas as variáveis locais da função.  Esse espaço de trabalho é colocado na pilha de execução (por cima do espaço de trabalho que invocou a função) e a execução da função começa (confinada ao seu espaço de trabalho).  Quando a execução da função termina, o seu espaço de trabalho é removido da pilha e descartado.  O espaço de trabalho que estiver agora no topo da pilha é reativado e a execução é retomada do ponto em que havia sido interrompida.  (Veja Julia's drawings: What's the stack?)

Considere o seguinte exemplo:

   int G (int a, int b) {
      int x;
      x = a + b;
      return x;
   }

   int F (int i, j, k) {
      int x; 
      x = /*2*/ G (i, j) /*3*/;
      x = x + k;
      return x;
   }

   int main (void) {
      int i, j, k, y;
      i = 111; j = 222; k = 444;
      y = /*1*/ F (i, j, k) /*4*/;
      printf ("%d\n", y);
      return EXIT_SUCCESS;
   }

A execução do programa prossegue da seguinte maneira:

• Um espaço de trabalho é criado para a função main e colocado na pilha de execução.  O espaço contém as variáveis locais i, j, k e y.  A execução de main começa.
• No ponto 1, a execução de main é temporariamente interrompida e um espaço de trabalho para a função F é colocado na pilha.  Esse espaço contém os parâmetros i, j, k da função (com valores 111, 222 e 444 respectivamente) e a variável local x.  Começa então a execução de F.
• No ponto 2, a execução de F é interrompida e um espaço de trabalho para a função G é colocado na pilha.  Esse espaço contém os parâmetros a e b da função (com valores 111 e 222 respectivamente) e a variável local x.  Em seguida, começa a execução de G.
• Quando a execução de G termina, a função devolve 333.  O espaço de trabalho de G é removido da pilha e descartado.  O espaço de trabalho de F (que agora está no topo da pilha de execução) é reativado e a execução é retomada no ponto 3.  A primeira instrução executada é x = 333;.
• Quando a execução de F termina, a função devolve 777. O espaço de trabalho de F é removido da pilha e descartado.  O espaço de trabalho de main (que agora está no topo da pilha) é reativado e a execução é retomada no ponto 4.  A primeira instrução executada é y = 777;.

No nosso exemplo, F e G são funções distintas. Mas tudo funcionaria da mesma maneira se F e G fossem idênticas, ou seja, se F fosse uma função recursiva.

Exercícios 6