Como implementar uma pilha com capacidade limitada?

Question

Como implementar uma pilha cuja capacidade seja limitada a maxlen elementos, em que maxlen é um parâmetro opcional para o construtor (o padrão é nenhum) de tal forma que se push for chamado quando a pilha estiver com capacidade total, lance uma exceção Full?

Answer 1

Usando uma lista em Python, a implementação pode ser feita pelo seguinte código:

# Criando as exceções
class Empty(Exception):
        """Erro ao tentar acessar uma lista vazia."""
        pass

class Full(Exception):
    '''Erro ao tentar adicionar um item a uma pilha cheia'''
    pass

# Implementando pilha
class ArrayStack:
    '''
    Implementação de uma pilha usando listas.
    '''
    def __init__(self, maxlen = None):
        '''Criando uma pilha vazia.'''
        self.__data = []
        self.__maxlen = maxlen

    def __len__(self):
        '''Retorna número de elementos da pilha.'''
        return len(self.__data)

    def is_empty(self):
        '''Checa se a pilha está vazia.'''
        return len(self.__data) == 0

    def push(self, e):
        '''Adiciona um elemento ao topo da lista.'''
        if self.__maxlen is None:
            self.__data.append(e)
        else:
            if len(self.__data) == self.__maxlen:
                raise Full('A pilha está cheia')                
            else:
                self.__data.append(e)

    def top(self):
        '''Retorna (mas, não remove) elemento no top da pilha'''
        if self.is_empty(): # Caso a pilha esteja vazia
            raise Empty('Pilha está vazia')
        return self.__data[-1]

    def pop(self):
        '''Remove e retorna elemento do topo da pilha'''
        if self.is_empty():
            raise Empty('Pilha vazia')
        return self.__data.pop()

    def get_data(self):
        return self.__data

if __name__ == '__main__':

    s = ArrayStack(3)

    s.push(1)
    s.push(2)
    s.push(3)

    s.get_data()
    s.push(4) # Exceção Full é chamada

Na primeira parte do código são criadas as exceções que serão usadas nos métodos push e top quando a pilha estiver vazia ou cheia. As principais diferenças em relação a uma pilha sem limitação de capacidade estão nas definições dos métodos __init__ e push.

Comments

Ótima a sua implementação, Neuremberg! Esta sua implementação é uma boa maneira de entender a construção de classes em Python.

Como alguns atributos da classe usam o underscore e outros não, acho interessante esclarecer este ponto em cada uma das situações que você os utilizou.

O método "__init__" é um método especial que é invocado toda vez que um objeto da classe é construído.

A sua definição de "__len__" para a classe foi necessária para subscrever o método "__len__" já presente na base do python. Se, ao invés de "__len__" você tivesse utilizado simplesmente "len" a chamada de len para a sua classe retornaria em erro. Outra alternativa seria usar um nome não utilizado para o método de sua classe, como "length", mas neste caso a chamada de uma instância x da classe deveria ser feita como x.length() ao invés de length(x).


O uso de underscores duplos antes de atributos, como em "__data" e "__maxlen" são para indicar que tais atributos não deveriam ser chamados diretamente pelo usuário, mas somente por outros métodos da classe. Assim, sendo x uma instância da classe, executar "x.__data()" ou "x.__data" retorna um erro. Entretanto, como o python substitui os atributos "__NomeDoAtributo" por "_NomeDaClasse__NomeDoAtributo" é possível recuperar os atributos escondidos, no caso de seu código, por meio das chamadas "x._ArrayStack__data" ou "x._ArrayStack__maxlen".