Pilhas

Pilhas

Uma pilha é um conjunto ordenado de itens, na qual novos item podem ser inseridos ou extraídos a partir de seu topo .

Uma pilha é um objeto dinâmico, constantemente mutável a partir da inserção ou extração de itens, sempre a partir de seu topo.

Quando um novo item é inserido na pilha, ele passa a ocupar seu topo. Neste caso, o topo é deslocado para cima de modo a corresponder ao novo primeiro elemento. Quando um item é removido, o topo da pilha é deslocado para baixo, para apontar ao novo primeiro elemento.

Operações primitivas com pilhas

As duas operações primitivas para lidar com pilhas são :

• push: Quando um elemento é inserido, ou empilhado, na pilha;
• pop: Quando um elemento é extraído, ou desempilhado, da pilha.

Funções para operar com pilhas

Considere uma pilha s e um item i, a função

push(s, i);

insere o item na pilha.

Por sua vez a função

i = pop(s);

extrai um item do topo da pilha.

Outra operação que pode ser utilizada é verificar o item do topo da pilha, sem extrai-lo

i = top(s);

Não existe um limite máximo para o número de item em uma pilha. Entretanto, se uma pilha tiver um só elemento e ele for extraído, teremos a pilha vazia. Portanto, antes de utilizar o operador pop, precisamos verificar se a pilha não está vazia.

A operação

empty(s);

verifica se a pilha está vazia ou não.

Imlementação de pilhas em linguagem C

Antes de programar a solução de um problema usando pilhas, é preciso definir como a pilha será representada na linguagem de programação que estamos utilizando.

Na linguagem C, uma das maneiras de implememtar uma pilha é utilizando vetores. Contudo, pilhas e vetores são tipos de dados diferentes:

• Uma pilha é um conjunto ordenado de itens de tamanho é variável e, a princípio, não tem limite de tamanho.
• Um vetor, por sua vez, é um conjunto ordenado de itens, cujo tamanho é fixado na declaração do vetor.

Entretando, podemos utilizar um vetor para implementar uma pilha, desde que este vetor seja declarado suficientemente grande para conter a pilha que pretendemos implementar. Uma extremidade do vetor será o final fixo da pilha, enquanto o topo da pilha se desloca constantemente a medida que elementos são inseridos ou extraídos da pilha.

Implementando pilhas com vetores

Uma implementação de uma pilha em C pode ser realizada a partir da declaração de uma estrutura com dois campos:

• Um vetor de items para armazenar os elementos da pilha;
• Um inteiro que aponta para o topo da pilha dentro do vetor.

Ver também

Uma pilha de inteiros pode ser declarada como

#define TAM 100
struct pilha {
  int topo;
  int itens[TAM];
};

No programa principal, depois de declarada a variável de pilha o topo deve ser inicializado com zero.

Operação push

Insere item no topo da pilha.

void push(struct pilha *p, int item)
{
   p->itens[p->topo++] = item;
}

Esta operação faz p->itens[p->topo] = item e depois incrementa topo.

Poderia também fazer um controle de erro para verificar se o tamanho da pilha são será ultrapassado:

void push(struct pilha *p, int item)
{
    if (p->topo == TAM) {
        fputs("Erro: overflow\n", stderr);
        abort();
    } else
        p->itens[p->topo++] = item;
}

Operação pop

Extrai item no topo da pilha.

void pop(struct pilha *p)
{
   return p->itens[--p->topo];
}

Esta operação decrementa topo e depois retorna p->itens[topo].

A operação pop() somente pode ser utilizada se a pilha não estiver vazia. Para isto, verificar antes com a função empty().

Operação top

Retorna o item do topo da pilha, sem extraí-lo.

void top(struct pilha *p)
{
   return p->itens[p->topo - 1];
}

Operação empty

Verifica se a pilha está vazia.

int empty(struct pilha *p)
{
    if (p->topo == 0) 
        return -1;
    else
        return 0;
}

Exemplo de aplicação de pilhas

Uma exemplo de aplicação de pilhas pode ser para verificar se uma expressão escrita com chaves, colchetes e parêntesis aninhados está bem escrita.

Por exemplo, a expressão:

{a * (b + c) * [d / (e + f)]} + g

está escrita corretamente, pois, para cada chave, colchete ou parêntesis abertos, há um correspondente que se fecha.

Para verificar se a expressão está correta, cada chave, colchete ou parêntesis que for aberto deve ser adicionado no topo da pilha. Quando encontrar um elemento que fecha, deve-se verificar a pilha. Se a pilha estiver vazia o elemento que fecha não terá um correspondente que abre e a expressão será inválida. Se a pilha não estiver vazia, deve-se extrair o elemento que está no topo e verificar se ele corresponde ao elemento que fecha. Se ocorrer coincidência, continua a análise, senão a expressão será inválida. Quando o final da expressão for alcançado, a pilha deve estar vazia. Senão, é sinal que foram abertos chaves, colchetes ou parêntesis sem correspondentes para fechar.

Referências

---

--Evandro.cantu (discussão) 16h49min de 17 de julho de 2014 (BRT)

---