Bags, Queues, and Stacks

Veja a página Bags, Queues, and Stacks (S&W).

Várias ADT fundamentais manipulam coleções de objetos (=collections). As operações sobre essas coleções são inserção, remoção ou examinar os seu objetos. Os nomes dessas ADT são devidas metáforas relacionados com as operações. As ADTs mais conhecidas são Bag (hmm), Queue e Stack.

A propósito, para que serve um objeto da classe Bag?

Para implementar essas classes usamos listas ligadas, vetores e vetores com redimensionamento. A operação de redimensionamento de um vetor usada nos EPs e em ADT como Stack, Queue e Bag tem consumo de tempo amortizado constante.

A propósito, quando dizemos que a operação o() consome tempo amortizado f, isso significa que, começando com um estrutura vazia, o custo de qualquer sequência de n operações o() é f.

Generics em Java nos fornece um mecanismo para definirmos uma ADT parametrizada.

Não deixem de ver:

• Exercises: todos os exercícios tem solução e você já devem ter visto vários em MAC0121. Vários tem a ver com notação polonesa. Olhem pelo menos o 3 e 13.
• Creative problems: 42, 45, e 46.
• Web exercises: 1 , 5, 7, 20 (hmm, tem a ver com MAC0210), 28, 31, 38, 40 (hmm, tem muita coisa legal).