Exemplos de estruturas de dados lineares: Pilha, Fila e Lista

estruturas_lineares.py

# -*- coding: utf-8 -*-

class Elemento:

    def __init__(self, dado, proximo=None):
        self.dado = dado
        self.proximo = proximo

    def __iter__(self):
        elemento = self

        while elemento:
            yield elemento
            elemento = elemento.proximo

    def __str__(self):
        return '[%s]%s' % (str(self.dado), '->' if self.proximo else '¬')


class _EstruturaLinear:

    def __init__(self):
        self.inicio = None
        self.tamanho = 0

    def __len__(self):
        return self.tamanho

    def __str__(self):
        if not self.vazia():
            return ''.join([str(elemento) for elemento in self.inicio])

        return ''

    def __repr__(self):
        return str(self)

    def __iter__(self):
        if not self.vazia():
            for elemento in self.inicio:
                yield elemento.dado

    def __contains__(self, dado):
        return self.buscar(dado) >= 0

    def buscar(self, dado_procurado):
        posicao = 0

        for dado in self:
            if dado == dado_procurado:
                return posicao

            posicao += 1

        return -1

    def vazia(self):
        return self.inicio is None


class Pilha(_EstruturaLinear):

    def empilhar(self, dado):
        self.inicio = Elemento(dado, self.inicio)
        self.tamanho += 1

    def desempilhar(self):
        if self.vazia():
            raise IndexError("desempilhando pilha vazia")

        elemento = self.inicio

        self.inicio = elemento.proximo
        self.tamanho -= 1

        return elemento.dado


class Fila(_EstruturaLinear):

    def __init__(self):
        super().__init__()
        self.final = None

    def enfileirar(self, dado):
        elemento = Elemento(dado)

        if self.vazia():
            self.inicio = elemento
        else:
            self.final.proximo = elemento

        self.final = elemento
        self.tamanho += 1

    def desenfileirar(self):
        if self.vazia():
            raise IndexError("desenfileirando fila vazia")

        elemento = self.inicio

        self.inicio = elemento.proximo
        self.tamanho -= 1

        if self.vazia():
            self.final = None

        return elemento.dado


class Lista(_EstruturaLinear):

    def inserir(self, posicao, dado):
        if posicao < 0:
            posicao += self.tamanho

        posicao = max(0, min(posicao, self.tamanho))

        if posicao == 0:
            self.inicio = Elemento(dado, self.inicio)
        else:
            anterior = self.inicio
            while posicao > 1:
                anterior = anterior.proximo
                posicao -= 1

            anterior.proximo = Elemento(dado, anterior.proximo)

        self.tamanho += 1

    def remover(self, posicao):
        if self.vazia():
            raise IndexError('removendo de lista vazia')

        if posicao < 0:
            posicao += self.tamanho

        if posicao == 0:
            elemento = self.inicio

            self.inicio = elemento.proximo
        elif 0 < posicao < self.tamanho:
            anterior = self.inicio

            while posicao > 1:
                anterior = anterior.proximo
                posicao -= 1

            elemento = anterior.proximo
            anterior.proximo = elemento.proximo
        else:
            raise IndexError('removendo em indice fora do alcance')

        self.tamanho -= 1

        return elemento.dado