Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar uma pilha com capacidade limitada inicializando-a com uma lista não vazia em Python?

+1 voto
21 visitas
perguntada Mai 2 em Ciência da Computação por Neuremberg de Matos (31 pontos)  

Na resposta desta pergunta, foi assumido que a lista subjacente está inicialmente vazia. Como implementar a mesma lista, mas desta vez pré-alocando uma lista subjacente com comprimento igual à capacidade máxima da pilha?

Compartilhe

1 Resposta

+1 voto
respondida Mai 2 por Neuremberg de Matos (31 pontos)  

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

# Definindo 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

# Definindo a pilha
class ArrayStackMaxLen:
    '''
    Implementando pilha com tamanho máximo e que inicia com lista com o
    tamanho máximo definido
    '''
    def __init__(self, max_len = None):
        '''Inicializa pilha'''
        self.__max_len = max_len

        if self.__max_len is None:
            self.__data = []
        else:
            self.__data = [None]*self.__max_len

        self.__index = 0

    def __len__(self):
        '''Retorna o número de elementos na pilha'''
        return self.__index

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

    def push(self, e):
        '''Adiciona um elemento ao topo da lista.'''
        if self.__max_len is None:
            self.__data.append(e)
            self.__index += 1 
        else:
            if self.__index == self.__max_len:
                raise Full('A pilha está cheia')                
            else:
                self.__data[self.__index] = e
                self.__index += 1

    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')
        s = self.__data[self.__index -1]
        self.__data[self.__index -1] = None
        self.__index -= 1
        return s

    def get_data(self):
        '''Retorna todos os elementos da pilha'''
        return self.__data

if __name__ == '__main__':
    s = ArrayStackMaxLen(3)

    s.push(1)
    s.push(2)
    s.push(3)
    print(len(s))
    s.push(4)

    s.get_data()
    s.top()    
    s.pop()
    s.get_data()
    len(s)

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.
Nessa implementação, todos o métodos deve mudar em relação ao caso de uma pilha sem limitação de capacidade.

...