Tad Pilha

Os tipos de dados que você viu até agora são todos concretos, no sentido que nós especificamos completamente como eles são implementados. Por exemplo, a classe Card(XXX ver como foi traduzido) representa uma carta utilizando dois inteiros. Como discutimos no momento, esta não é a única maneira de representar uma carta; existem muitas implementações alternativas.Um tipo abstrato de dado, ou TAD, especifica um conjunto de operações (ou métodos) e a semântica das operações (o que elas fazem), mas não especifica a implementação das operações. Isto é o que o faz abstrato.Por que isto é útil?Simplifica a tarefa dde especificar um algoritmo se você pode XXXdenotar(denote) as operações que você precisa sem ter que pensar, ao mesmo tempo, como as operações são executadas.Uma vez que existem geralmente muitas maneiras de implementar um TAD, pode ser útil escrever um algritmo que pode ser usado com qualquer das possíveis implementações.TADs bastante conhecidos, como o TAD Pilha deste capítulo, já estão implementados em bibliotecas padrão, então eles podem ser escritos uma vez e usado por muitos programadores.As operações em TADs provêm uma linguagem de alto nível comum para especificar e falar sobre algoritmos.Quando falamos sobre TADs, geralmente distinguimos o código que usa o TAD, chamado cliente, do código que implementa o TAD, chamado código fornecedor.

18.2 O TAD Pilha

Neste capítulo, iremos olhar um TAD comum, a pilha. Uma pilha é uma coleção, ou seja, é uma estrutura de dados que contei múltiplos elementos. Outras coleções que vimos incluem dicionários e listas.Um TAd é definido pelo conjunto de operações que podem ser executadas nele, que é chamadointerface. A interface para uma pilha consiste nestas operações:__init__ : Inicializa uma nova pilha vazia.push : Adiciona um novo item na pilhapop : Remove um ítem da pilha e o retorna, O ítem que é retornadao é sempre o último adicionado.isEmpty : Verifica se a pilha está vazia.Uma às vezes é chamada uma estrutura de dados “last in, first out” ou LIFO, porque o último ítem adicionad é o primeiro a ser removido.

18.3 Implementando pilhas com listas de Python

As operações de lista que Python oferecem são similares às operações que definem uma pilha. A interface não é exatamente o que se supõe ser, mas podemos escrever um código para traduzir do TAD Pilha para as operações nativas.Este código é chamado uma implementação do TAD Pilha. Geralmente, uma implementaçõa é um conjunto de métodos que satisfazem os requisitos sintáticos e semânticos de uma interface.