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

Como implementar em Python uma classe fila usando duas pilhas

0 votos
33 visitas
perguntada Out 30 em Ciência da Computação por Renata Oliveira (46 pontos)  

Exercício C-6.25 do livro "Data Structures and Algorithms in Python" - Goldrich, Tamassia e Goldwasser

Compartilhe

1 Resposta

0 votos
respondida Out 30 por Renata Oliveira (46 pontos)  

O exercício propõe que seja feita uma implementação de uma classe fila utilizando duas pilhas. Uma pilha é uma coleção de objetos que são adicionados e removidos de uma estrutura de acordo com o princípio "last-in, first-out" (LIFO). Isto significa que a qualquer momento um objeto pode ser adicionado à pilha, porém só é possível remover o objeto que, a cada momento, está no topo da pilha. Uma pilha é definida por dois métodos principais: o método \(push(e)\), que adiciona o elemento \(e\) ao topo da pilha, e o método \(pop()\), que remove o elemento que está no topo da pilha. Além destes, são usualmente definidas operações como \(top()\), que indica o elemento que está no topo da pilha, \(is\_ empty\), que indica se a pilha está vazia e \(len\), que retorna o tamanho da pilha.

Uma fila, por sua vez, é uma estrutura de dados em que os objetos são inseridos e removidos de acordo com o princípio "first-in, first-out" (FIFO). Segundo este princípio, elementos podem ser adicionados a qualquer momento à fila, porém só é possível remover de cada vez o elemento que está há mais tempo na fila. Os dois métodos que caracterizam as filas são: o método \(enqueue(e)\), que adiciona o elemento \(e\) ao final da fila, e o método \(dequeue()\), que remove o primeiro elemento da fila, ou seja, aquele que está há mais tempo na fila. Assim como nas pilhas, são definidas as operações \(first()\), que retorna o primeiro elemento da fila, \(is\_empty\) e \(len\).

A figura abaixo ilustra a diferença entre uma pilha S e uma fila Q. Os métodos \(push(e)\) e \(enqueue(e)\) que adicionam os objetos às estruturas são equivalentes. A diferença está na remoção dos elementos da estrutura. Dada uma pilha com os elementos 1, 2 e 3, o método \(pop()\) remove o elemento 3, o último a ser adicionado à pilha. Por outro lado, dada uma fila com os elementos 1, 2 e 3, o método \(dequeue()\) remove o elemento 1, o primeiro a ser colocado na fila.

A imagem será apresentada aqui.

Uma implementação simples de uma pilha em Python, adaptando os métodos que já existem para as listas, está no código 6.2 do livro, reproduzido abaixo. O método \(push(e)\) equivale ao método \(append(e)\) já implementado para a listas do Python. O método \(pop()\) também já existe para listas. O método \(top()\) apenas retorna o elemento que está no topo da pilha.

class Empty(Exception):
pass

class ArrayStack:
"""LIFO Stack implementation - Code Fragment 6.2"""
def __init__(self):
    self._data=[] #stack is stored in a python list

def __len__(self):
    return len(self._data)

def is_empty(self):
    return len(self._data)==0 #True if the stack is empty

def push(self, e):
    self._data.append(e) #adds element e to the top of the stack

def top(self):
    if self.is_empty():
        raise Empty('Stack is empty')
    return self._data[-1]

def pop(self):
    if self.is_empty():
        raise Empty('Stack is empty')
    return self._data.pop() #removes the element that is on top

A implementação de filas usando as listas do python não é tão simples. O método \(enqueue(e)\) pode ser adaptado a partir do método \(append(e)\), assim como na implementação da pilha. O método \(dequeue()\), que remove o primeiro elemento da fila, poderia ser caracterizado por \(pop(0)\), ou seja, remove o elemento de índice zero da lista. Esta abordagem, porém, é ineficiente pois os índices de todos os elementos da lista são alterados quando o primeiro elemento é removido. Isto envolve um alto custo pois são realizadas \(n\) operações, sendo \(n\) o número de elementos na lista. Uma alternativa seria substituir o elemento removido por "None" e guardar uma variável \(f\) que representa o índice do elemento que está na primeira posição a cada momento. O problema é que a lista poderia se tornar arbitrariamente grande à medida que elementos fossem adicionados e removidos, mesmo que a quantidade de elementos da fila seja relativamente pequena. Este problema é ilustadro na figura abaixo. Após adicionarmos três elementos à fila Q, chamamos o método \(dequeue()\) para remover o primeiro elemento adicionado. Note que o tamanho da lista que representa a fila não diminui quando este elemento é removido, apenas alteramos a variável \(f\) que indica o início da fila. O mesmo ocorre à medida que adicionamos e removemos elementos, conforme a figura. Na última linha, a fila tem apenas dois objetos, mas a lista que representa a fila tem tamanho 6.

A imagem será apresentada aqui.

Uma terceira abordagem seria a da circularidade, em que assumimos que a lista que representa a fila possui um tamanho fixo, maior que a quantidade de elementos da fila. Quando removemos um elemento, a variável \(f\), que representa o índice do elemento que está na primeira posição, é alterada. Novos elementos são adicionado ao "final" da fila, conforme a figura abaixo. O "final" da fila Q é a primeira posição disponível na lista que representa a fila.

A imagem será apresentada aqui.

O objetivo do exercício é implementar uma classe fila de forma diferente, utilizando duas pilhas. A ideia é que sobre uma das pilhas o método \(enqueue(e)\) será aplicado e sobre a outra pilha o método \(dequeue()\) será aplicado. À medida que elementos são adicionados à fila (enqueue), eles são armazenados na pilha \(Enqueuing Stack\). Para remover o primeiro elemento da fila (dequeue), todos os elementos da pilha \(Enqueuing Stack\) são alocados em ordem inversa na pilha \(Dequeuing Stack\), de modo que o último elemento desta pilha é o primeiro elemento que foi adicionado à fila. Para ilustrar, considere um exemplo. Suponha que a fila Q seja criada. Inicialmente temos duas pilhas vazias.

A imagem será apresentada aqui.

Adicionamos então os elementos 1, 2 e 3, nesta ordem. Estes elementos são armazenados na \(Enqueuing Stack\).

A imagem será apresentada aqui.

Quando chamamos o método \(dequeue()\), primeiramente alocamos os elementos da \(Enqueuing Stack\) para a \(Dequeuing Stack\) em ordem inversa. Isto é possível pegando o último elemento da pilha \(Enqueuing Stack\), usando o método \(pop()\), e colocando-o na pilha \(Dequeuing Stack\) usando o método \(push\). Feita a transferência dos elementos, podemos simplesmente usar o método \(pop()\) na pilha \(Dequeuing Stack\) para remover o primeiro elemento da fila.

A imagem será apresentada aqui.

Se quisermos adicionar outro elemento à fila, por exemplo o 4, ele será armazenado novamente na pilha \(Enqueuing Stack\), que agora está vazia.

A imagem será apresentada aqui.

Se chamarmos novamente o método \(dequeue()\), simplesmente removemos o útimo elemento da pilha \(Dequeuing Stack\) usando o método \(pop()\). A transferência de elementos da pilha \(Enqueuing Stack\) para a pilha \(Dequeuing Stack\) só é feita se a pilha \(Dequeuing Stack\) estiver vazia.

A imagem será apresentada aqui.

A implementação desta classe é feita conforme o código abaixo.

class Queue:
    def __init__(self):
    self.DequeuingStak=ArrayStack() #Dequeuing Stack starts as an empty stack
    self.EnqueuingStack=ArrayStack() #Enqueuing Stack starts as an empty stack


def is_empty(self):
    ''' 
    The queue is empty if there are zero elements in both stacks.
    Returns True if the queue is empty
    '''
    return (len(self.EnqueuingStack) + len(self.DequeuingStak))==0


def len(self):
    '''
    Returns the number of elements in both stacks
    ''' 
    return len(self.EnqueuingStack) + len(self.DequeuingStak)


def enqueue(self, e):
    '''
    Adds element e to the end of the queue
    ''' 
    self.EnqueuingStack.push(e) #element e is stored in the Enqueuing Stack


def dequeue(self):
    '''
    Removes the element that has been in the queue the longest
    '''
    if len(self.DequeuingStak)==0:
        if len(self.EnqueuingStack)==0:
            raise Empty('Stack is empty')
        else: #if the Dequeuing Stack is empty - transferring elements is necessary
            while len(self.EnqueuingStack)>0: #transfer elements until Enqueuing Stack is empty:
                i=self.EnqueuingStack.pop() #pop last element of Enqueuing Stack
                self.DequeuingStak.push(i) #add it to the Dequeuing Stack

    first=self.DequeuingStak.pop() #the first element of the queue is the last element of the Dequeuing Stack
    return first

def first(self):
    '''
    Displays the first element of the queue
    Similar to the dequeue method, except it does not remove the first element
    ''' 
    if len(self.DequeuingStak)==0:
        if len(self.EnqueuingStack)==0:
            raise Empty('Stack is empty')
        else:
            while len(self.EnqueuingStack)>0:
                i=self.EnqueuingStack.pop()
                self.DequeuingStak.push(i)

    first=self.DequeuingStak.top() #just shows which element is the first, without removing it
    return first

Para verificar se a classe funciona conforme o esperado, são realizadas as operações do exemplo 6.4 do livro.

A imagem será apresentada aqui.

if __name__ == '__main__': 

    my_queue=Queue()
    my_queue.enqueue(5)
    my_queue.enqueue(3)
    print(my_queue.len())
    print(my_queue.dequeue())
    print(my_queue.is_empty())
    print(my_queue.dequeue())
    print(my_queue.is_empty())
    print(my_queue.dequeue()) #error
    my_queue.enqueue(7)
    my_queue.enqueue(9)
    print(my_queue.first())
    my_queue.enqueue(4)
    print(my_queue.len())
    print(my_queue.dequeue())

Os resultados estão de acordo com o exemplo:

2
5
False
3
True
__main__.Empty: Stack is empty
7
3
7
...