3.5. Implementando uma Pilha em Python¶

Agora que definimos claramente a pilha como um tipo de dados abstrato, vamos voltar nossa atenção para o uso do Python para implementar uma pilha. Lembre-se que quando damos uma implementação particular a um tipo de dados abstrato nós chamamos esta implementação de uma estrutura de dados.

Como descrevemos no capítulo 1, em Python, como em qualquer linguagem de programação orientada a objetos, a implementação de um tipo abstrato de dados como uma pilha é feita através da criação de uma nova classe. As operações sobre uma pilha são implementadas como métodos. Além disso, para implementar uma pilha, que é uma coleção de elementos, faz sentido utilizar o poder e simplicidade das coleções primitivas fornecidas pelo Python. Nós usaremos uma lista (list).

Lembre-se de que a classe de lista no Python fornece mecanismo para mantermos coleção ordenada de itens e um conjunto de métodos para manipularmos essa coleção. Por exemplo, se tivermos a lista [2, 5, 3, 6, 7, 4], precisamos apenas decidir qual extremidade da lista será considerado o topo da pilha e qual será a base. Uma vez que essa decisão é tomada, as operações podem ser implementadas usando uma lista e métodos como append() e pop().

A seguinte implementação de pilha (ActiveCode 1) supõe que o final da lista mantém o elemento do topo. Como a pilha cresce (como ocorrem as operações push()), novos itens serão inseridos no final da lista. As operações pop() atuarão na mesma extremidade.

Lembre-se que quando clicamos no botão run nada acontece além da definição da classe. Nós devemos criar um objeto Stack e então usá-lo. ActiveCode 2 mostra a classe Stack em ação ao executarmos a seqüência de operações na Tabela 1. Observe que a definição da classe Stack é importada do módulo pythond.

É importante notar que poderíamos ter escolhido implementar a pilha usando uma lista em que o topo estaria no início e não no final. Neste caso, os métodos pop() e append() não seriam apropriados pois deveríamos indexar a posição 0 (o primeiro item da lista) explicitamente usando pop(0) e insert(0, item). A implementação é mostrada em CodeLens 1.

Essa capacidade de alterar a implementação de um tipo abstrato de dados mantendo as características lógicas é um exemplo de abstração. No entanto, mesmo que a pilha funcione da mesma forma, se considerarmos o desempenho das duas implementações, há definitivamente uma diferença. Lembre-se que o append() e pop() são operações que consomem tempo constante, ou seja O(1). Isso significa que na primeira implementação cada executação de push() e pop() consome tempo constante, independentemente do número de itens na pilha. Na segunda implementação, o consumo de tempo de push() e pop() é proporcional ao número n de itens na pilha já que as operações insert(0) e pop(0) requererem tempo O(n). Claramente, mesmo que as implementações sejam logicamente equivalentes, tenham o mesmo comportamento, elas apresentarão desempenhos diferentes ao serem executadas.