LIFO — Last In, First Out

Pilha: acesso restrito ao topo

A pilha é um tipo abstrato no qual o último elemento inserido é o primeiro que pode ser removido.

push · pop · peek

Contrato da pilha

  • push(valor) insere um elemento no topo.
  • pop() remove e retorna o elemento do topo.
  • peek()/top consulta o topo sem removê-lo.
  • is_empty() informa se não há elementos.

Regra, não formato de memória

LIFO descreve a ordem das operações. A pilha pode usar um array, um array redimensionável ou nós encadeados.

Invariante: push e pop acontecem sempre na mesma extremidade lógica, o topo.

Duas implementações possíveis

ImplementaçãoComo representa o topopush/pop
ArrayÚltimo índice ocupado; não há ponteiro next em cada posição.O(1), amortizado no array redimensionável.
Lista encadeadaUma referência top aponta para o primeiro nó; cada nó aponta para o nó abaixo.O(1).

Laboratório: pilha encadeada

Nesta representação específica, top aponta para a célula superior. O campo next de cada célula aponta para a célula imediatamente abaixo.

Push e pop no topo

Operação
Ordem da base ao topo

    Python: list como pilha

    A documentação do Python recomenda append() e pop() no final da lista para obter o comportamento LIFO.

    Pythonarray redimensionável
    pilha = []

pilha.append(2)  # push
pilha.append(3)
pilha.append(4)

topo = pilha[-1]  # peek: 4
saiu = pilha.pop() # pop: 4

print(pilha)       # [2, 3]

    Python: pilha encadeada

    Aqui o desenho do laboratório aparece diretamente no código: cada nó possui value e next.

    Pythonnós encadeados
    class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        # O novo nó aponta para o topo antigo e passa a ser o topo.
        self.top = Node(value, self.top)

    def pop(self):
        if self.top is None:
            raise IndexError("pilha vazia")

        # Guardamos o valor antes de descartar a referência do nó removido.
        value = self.top.value
        self.top = self.top.next
        return value

    Referências usadas