Pilhas

Uma Pilha (Stack) é um tipo abstrato de dados que funciona como uma coleção com duas operações principais, push, que insere um novo elemento, e pop, que remove o elemento mais recentemente adicionado a coleção que ainda não foi removido.

Devido ao seu comportamento com relação à ordem com que os dados são retirados da pilha, também são conhecidas como LIFO (Last In, First Out - último a entrar, primeiro a sair). O nome "pilha" deriva do fato deste comportamento se assemelhar a um conjunto de itens físicos, empilhados.

As operações push e pop ocorrem apenas no "topo" da pilha, por este motivo, as pilhas podem ser implementadas de forma eficiente com o uso de vetores, com as operações sendo executadas na posição final do vetor, ou de listas com encadeamento simples, com as operações sendo executadas no primeiro elemento da lista (head).

Operações em pilhas

Além das duas operações necessárias ao funcionmento das pilhas, algumas operações são comuns em suas implementações para facilitar a sua utilização. Operações como peek, que consulta o elemento no topo da pilha sem removê-lo, ou empty, que testa se a pilha está vazia.

push
Insere um novo elemento no topo da pilha. Em implementações com limite de armazenamento pode gerar um erro de overflow.
pop
Remove o elemento no topo da pilha, retornando-o. Em algumas implementações, pode gerar um erro de underflow, caso a pilha esteja vazia.
peek
Retorna o elemento no topo da pilha, sem removê-lo. Em algumas implementações, pode gerar um erro de underflow, caso a pilha esteja vazia.
empty
Testa se existem elementos na pilha.

Implementação

Para a implementação de uma pilha, é importante que as operações push e pop sejam muito eficientes, idealmente, com número de operações executadas independente do número de elementos armazenados (\(\Theta;(1)\)). Por esse motivo, a implementação de uma pilha pode utilizar como estrutura de armazenamento tanto arranjos dinâmicos, quanto listas com encadeamento simples.

No caso da implementação com vetores, as operações devem ser realizadas no último elemento, fazendo com que as operações tenham custo constante amortizado. Para a implementação com listas encadeadas, as operações de pilha devem ser realizadas no primeiro elemento da lista, fazendo com que o custo das operações seja sempre constante.

Quando o uso de memória deve ser controlado, como no caso de sistemas embarcados, o uso de um arranjo com tamanho estático, provê um uso otimizado da memória.

A implementação apresentada aqui, utiliza aranjos estáticos para a área de armazenamento. São utilizados os campos dados, que é um arranjo com tamanho definido pelo usuário, e topo, que armazena um valor inteiro que representa a posição onde o próximo elemento será inserido.

Inserção

A operação de inserção de um elemento no topo da pilha é uma das duas operações essenciais de uma pilha e deve ser implementada de forma a ser o mais eficiente possível. Na implementação com arranjos, o elemento é inserido como último elemento do arranjo, em uma implementação com listas encadeadas, o elemento deve ser inserido com o primeiro elemento da lista (head), o que é eficiente tanto com listas de encadeamento simples, como com as de encadeamento duplo.

No caso de pilhas que utilizam estruturas onde a capacidade de armazenamento não é alterada dinâmicamente, pode ocorrer um erro de "Pilha Cheia" ao tentar inserir um valor quando não há mais espaço disponível ("Stack overflow").

Inserção de um novo elemento

push ( value ):
    if topo == dados.length
        error StackOverflow
    dados[topo] = value
    topo = topo + 1

Remoção

A operação de remoção do elemento no topo da pilha é a segunda das duas operações essenciais de uma pilha e deve ser implementada de forma a ser o mais eficiente possível. Na implementação com arranjos, isso significa remover o último elemento de um vetor, em uma implementação com listas encadeadas, remove-se o primeiro elemento (head), sendo eficiente com listas de encadeamento duplo ou simples.

Tradicionalmente, esta operação retorna o valor armazenado no topo da pilha. Pode gerar um erro de "Pilha Vazia" ("Stack Underflow"), quando se tenta retirar um elemento de uma pilha vazia.

Retirada do elemento no topo pilha

pop ( ) -> Dado:
    if empty()
        error StackUnderflow
    topo = topo - 1
    return dados[topo]

Consulta

A consulta sem a remoção do elemento no topo da pilha não é uma operação essencial porém muito útil na utilização de uma pilha. Pode ser implementada de forma similar à operação pop(), e assim como essa operação, pode ocasionar o erro "Stack Underflow".

Consulta ao elemento no topo da pilha.

peek ( ) -> Dado:
    if empty()
        error StackUnderflow
    return dados[topo - 1]

Verificação de elementos

Embora não seja uma função essencial, a verificação da existência de elementos em uma pilha pode facilitar ou acelerar a execução de algoritmos que as utilizem, de forma que não precisem tratar erros de "Pilha Vazia" ("Stack Underflow").

Verificação se a pilha está vazia.

empty ( valor ) -> Boolean :
    return topo == 0

A verificação de uma "pilha cheia" só é necessária quando a estrutura de armazenamento não aumenta dinamicamente sua capacidade, e por isso, nem sempre está disponível. Caso esteja disponível, pode ser utilizada para evitar a necessidade de tratar erros de "Pilha Cheia" ("Stack Overflow").

Verificação se a pilha está cheia.

empty ( valor ) -> Boolean :
    return topo == dados.length

Aplicações de Pilhas

Avaliação de expressões aritméticas

Uma forma eficiente de avaliar expressões aritméticas, descritas com a notação Polonesa reversa (RPN-Reverse Polish Notation), é utilizando uma pilha para armazenar os valores da expressão.

A partir de uma expressão descrita na forma RPN, sempre que um elemento da fórmula for um valor, ele é empilhado, sempre que um elemento for um operador, dois elementos são retirados da pilha, a operação equivalente é realizada nos dois elementos (sendo o primeiro elemento retirado o operando à direita e o segundo elemento o operando à esquerda), e o resultado da operação é novamente empilhado.

Ao terminar a avaliação da expressão, o resultado é encontrado no topo da pilha.

Algoritmo para avaliação de expressões aritméticas.

Dada uma entrada de dados divididas em seus componentes (tokens)

enquanto existem tokens na entrada
    se o token for um operando
        empilha-se o operando na pilha
    se o token for um operador
        retiram-se dois operandos da pilha,
        executa-se a operação com os operandos,
        empilha-se o resultado de volta na pilha

ao final, o resultado da operação estará armazenado no topo da pilha.

Inversão de Expressões Infixas para Pós-fixas

Expressões infixas (ex.: 1 + 2 * 3) ou pré-fixas (ex.: + 1 2) podem ser convertidas para a versão pós-fixa (ex.: 1 2 +) com o auxílio de pilhas que armazenam os operadores da expressão original (Algoritmo 6). Assim, é possível obter um algoritmo para a avaliação de expressões que não estão na forma RPN, pois basta converter da forma existente para RPN, e aplicar o algoritmo de avaliação de expressões RPN (Algoritmo 5).

Algoritmo para inversão de expressões infixas para pós-fixas.

Defina as prioridades dos operadores que serão analisados
    "+", "-" = 1
    "*", "/" = 2
    "^" = 3
    "(" = 0

Dada uma entrada de dados dividida em seus componentes (tokens),
enquanto existem dados na entrada
    se o token for um operando
        envia o token para a saída
    se o token for um operador
        se o operador for ")"
            equanto o operador retirado da pilha não for "("
                envia operador para a saída
        senão
            enquanto a prioridade do operador for menor que a do operador do topo da pilha
                retira operador da pilha
                envia operador para a saída
            empilhe o operador

equanto existirem operadores na pilha
    retira operador da pilha
    se não for "("
        envia operador para a saída
    senão retorna erro na formula

Backtracking

Outra aplicação importante no uso de pilhas é o backtracking, que consiste em marcar "pontos" onde se pode retornar depois. Por exemplo, para encontrar um caminho em um labirinto, podemos andar pelo labirinto até que se encontre uma divisão neste caminho. Neste ponto, adicionamos a posição onde a divisão ocorre, junto com o caminho escolhido na pilha, e seguimos pelo caminho escolhido. Se o caminho se mostrar sem saída, basta retirar o ponto anterior da pilha e recomeçar por um caminho ainda não escolhido no último ponto em que o labirinto se dividiu.

Outra aplicação semelhante no uso de backtracking é a operação desfazer, existentes em diversas aplicações que lidam com múltiplas ações de um usuário. Para implementar essa operação, as ações realizadas, ou o estado do sistema antes da realização destas ações, são armazenados em uma pilha, e caso a operação de desfazer deva ser executada, o estado anterior do sistema pode ser restaurado, ou ação contrária a realizada pode ser executada.

Gerenciamento de memória em runtime

Pilhas também são muito utilizadas em sistemas de programação e máquinas virtuais para a execução das operações básicas, como a máquina "p-code" ou a Java Virtual Machine.

Praticamente todos os sistemas de subrotinas são implementados utilizando pilhas para a passagem de parâmetros e para o retorno de funções, criando uma pilha de chamadas.