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.
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.
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.
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.
Adicionamos então os elementos 1, 2 e 3, nesta ordem. Estes elementos são armazenados na \(Enqueuing Stack\).
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.
Se quisermos adicionar outro elemento à fila, por exemplo o 4, ele será armazenado novamente na pilha \(Enqueuing Stack\), que agora está vazia.
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 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.
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