Pilhas

Uma pilha é uma das várias estruturas de dados que admitem remoção de elementos e inserção de novos elementos.  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).

Veja o verbete Stack (data structure) na Wikipedia.

Implementação em um vetor

Suponha que nossa pilha está armazenada em um vetor  pilha[0..n-1].  Vamos supor que os elementos de pilha são inteiros (isso é só um exemplo; os elementos de pilha poderiam ser quaisquer outros objetos). A parte do vetor ocupada pela pilha será

pilha[0..t-1] .

0							t			N-1

O índice t indica o topo (= top) da pilha.  Esta é a primeira posição vaga da pilha.  A pilha está vazia se t vale 0 e cheia se t vale n.

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

   x = pilha[--t];

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

Para inserir — ou seja, para empilhar (= to push) — um objeto y na pilha faça

   pilha[t++] = y;  

Isso equivale ao par de instruções  "pilha[t] = y; t += 1;"  nesta ordem.  Antes de empilhar, verifique se a pilha já está cheia para evitar que ela transborde (ou seja, para evitar um overflow).  Em geral, a tentativa de inserir em uma pilha cheia é uma situação excepcional, que indica um mau planejamento lógico do seu programa.

Aplicação: parênteses e colchetes

Suponha que queremos decidir se uma dada seqüência de parênteses e colchetes está bem formada. Por exemplo, a primeira das seqüências abaixo está bem formada enquanto a segunda não está.

( ( ) [ ( ) ] )

( [ ) ]

Suponha que a seqüência de parênteses e colchetes está armazenada em uma cadeia de caracteres (= string)  s.  Como é hábito em C, o último caracter da cadeia é o caracter nulo,  '\0'.

// A função devolve 1 se a cadeia s contém uma seqüência 
// bem formada de parênteses e colchetes e devolve 0 se
// a seqüência está mal formada.

int bemFormada (char s[])
{
   char *pilha; int t; 
   int n, i;
  
   n = strlen (s);
   pilha = mallocX (n * sizeof (char));
   t = 0;
   for (i = 0; s[i] != '\0'; ++i) {
      // a pilha está armazenada em pilha[0..t-1]
      switch (s[i]) {
         case ')': if (t != 0 && pilha[t-1] == '(') 
                      --t;
                   else return 0;
                   break;
         case ']': if (t != 0 && pilha[t-1] == '[') 
                      --t;
                   else return 0;
                   break;
         default:  pilha[t++] = s[i];
      }
   }
   free (pilha);
   if (t == 0) return 1;
   else return 0; 
}

Note que a pilha não transborda porque nunca terá mais elementos que o número de caracteres de s.

Exercícios

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 polonesa, ou posfixa, os operadores são escritos depois dos operandos. Exemplo:

infixa	posfixa
(A+B*C)	ABC*+
(A*(B+C)/D-E)	ABC+*D/E-
(A+B*(C-D*(E-F)-G*H)-I*3)	ABCDEF-*-GH*-*+I3*-
(A+B*C/D*E-F)	ABC*D/E*+F-
(A+(B-(C+(D-(E+F)))))	ABCDEF+-+-+
(A*(B+(C*(D+(E*(F+G))))))	ABCDEFG+*+*+*

A notação posfixa dispensa parênteses. A ordem dos operandos é a mesma nas expressões infixa e posfixa. Nosso problema:

Traduzir para notação posfixa a expressão infixa armazenada em uma cadeia de caracteres inf.

Para simplificar nossa vida, vamos supor que a expressão infixa está correta e consiste apenas de letras, abre-parêntese, fecha-parêntese e símbolos para as quatro operações aritméticas. Vamos supor também que cada nome de variável tem uma letra apenas. Finalmente, vamos supor que a expressão toda está embrulhada em um par de parênteses, isto é, inf[0] vale '(' e os dois últimos elementos de inf são ')' e '\0'.

Usaremos uma pilha para resolver o problema. Como a expressão infixa está embrulhada em um par de parênteses, não precisamos nos preocupar com pilha vazia!

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

char *infixaParaPosfixa (char inf[]) {
   char *posf; 
   char *pi; int t; // pilha
   int n, i, j;

   n = strlen (inf);
   posf = mallocX (n * sizeof (char));
   pi = mallocX (n * sizeof (char));
   t = 0;
   pi[t++] = inf[0];                          // empilha '('
   for (j = 0, i = 1; /*X*/ inf[i] != '\0'; ++i) {
      // a pilha está em pi[0..t-1]
      switch (inf[i]) {
         char x;
         case '(': pi[t++] = inf[i];          // empilha
                   break;
         case ')': while (1) {                // desempilha
                      x = pi[--t];
                      if (x == '(') break;
                      posf[j++] = x;
                   }
                   break;
         case '+': 
         case '-': while (1) {
                      x = pi[t-1];
                      if (x == '(') break;
                      --t;                    // desempilha
                      posf[j++] = x;
                   }
                   pi[t++] = inf[i];          // empilha
                   break;
         case '*':
         case '/': while (1) {
                      x = pi[t-1];
                      if (x == '(' || x == '+' || x == '-') 
                         break;
                      --t;
                      posf[j++] = x;
                   }
                   pi[t++] = inf[i];
                   break;
         default:  posf[j++] = inf[i];
      }
   }
   free (pi);
   posf[j] = '\0';      
   return posf;
}  

[Veja outra maneira de escrever a função.]   Constantes e variáveis vão diretamente de inf para posf. Abre-parêntese vai para a pilha. Ao encontrar um fecha-parêntese, a função remove tudo da pilha até o abre-parêntese inclusive. Ao encontrar um + ou - a função desempilha tudo até um abre-parêntes exclusive. Ao encontrar um * ou / desempilha tudo até um abre-parêntese ou um + ou um -.

Eis o resultado da aplicação da função à expressão infixa  ( A * ( B * C + D ) ) . A tabela abaixo registra os valores das variáveis a cada passagem pelo ponto X:

inf[0..i-1]	pi[0..t-1]	posf[0..j-1]
(	(
(A	(	A
(A*	(*	A
(A*(	(*(	A
(A*(B	(*(	AB
(A*(B*	(*(*	AB
(A*(B*C	(*(*	ABC
(A*(B*C+	(*(+	ABC*
(A*(B*C+D	(*(+	ABC*D
(A*(B+C*D)	(*	ABC*D+
(A*(B+C*D))		ABC*D+*

Exercícios

Exercícios

Pilha implementada em uma lista encadeada

Como implementar uma pilha em uma lista encadeada?  Digamos que as células da lista são do tipo celula:

typedef struct cel {
   int         conteudo; 
   struct cel *prox;
} celula;

Decisões de projeto: Vamos supor que nossa lista tem uma célula-cabeça (ou seja, vamos supor que a primeira célula da lista não faz parte da pilha). Vamos supor que o topo da pilha está na segunda célula e não na última (por que?). A pilha pode ser criada e inicializada assim:

celula cabeca; 
celula *tp;
tp = &cabeça;
tp->prox = NULL; 

Para ter acesso à pilha, só preciso do ponteiro tp. De acordo com nossa decisão de projeto, teremos sempre tp == &cabeca. A pilha está vazia se tp->prox == NULL.

// Insere um elemento y na pilha tp.

void empilha (int y, celula *tp) { 
   celula *nova;
   nova = mallocX (sizeof (celula));
   nova->conteudo = y;
   nova->prox  = tp->prox;
   tp->prox = nova; 
}

// Remove um elemento da pilha tp.
// Supõe que a pilha não está vazia. 
// Devolve o elemento removido.

int desempilha (celula *tp) {
   int x;
   celula *p;
   p = tp->prox;
   x = p->conteudo;
   tp->prox = p->prox;
   free (p);
   return x; 
}

Exercícios

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

Para executar um programa que contém chamadas a funções, o computador usa uma pilha. Durante a execução do programa, toda vez que o computador encontra uma chamada a uma função F, o "estado atual das coisas" é colocado em uma pilha e a execução de F começa. Quando a execução de F terminar, o computador tira da pilha o "estado" em que as coisas estavam antes da chamada de F e retoma a execução do programa do ponto em que ela foi interrompida.

Agora suponha que durante a execução de F o computador encontra uma chamada a uma função G, e que durante a execução de G encontra uma chamada a uma função H. Você já percebeu o que acontece? Exemplo:

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

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

   int main (void) {
      int x = 32, y = 12, z = 10;
      int w;
      w = /*1*/ F (x, y, z); 
      ............
   }

• No ponto /*1*/ a execução de main é temporariamente interrompida e os valores x, y e z são guardados na pilha de execução (juntamente com a informação de que parei no ponto /*1*/).
• Começa a execução de F. No ponto /*2*/ a execução de F é temporariamente interrompida e os valores i, j e k são guardados na pilha de execução (juntamente com a informação de que parei no ponto /*2*/).
• Quando a execução G termina (com G (i,j) igual a 44), tiro as informações da pilha e retomo a execução de F do ponto onde parei. A primeira instrução que executo é c = 44.
• Quando a execução de F termina (com F (x,y,z) igual a 54), tiro as informações da pilha e retomo a execução de main do ponto onde parei. A primeira instrução executada será w = 54.

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.