Генеричке класе – задаци¶

1. Ред без дупликата

Написати генеричку класу QueueWNoDup<T>, која имплементира стек елемената типа T, који не прихвата елементе које већ садржи. Јавни метод public bool Enqueue(T x) треба да врати вредност true ако је убацивање елемента у ред успело, а false ако није, тј. ако такав елемент већ постоји у реду.

Поред метода Enqueue, треба још написати јавне методе bool Empty() и T Dequeue().

Сложеност свих операција треба да буде \(O(1)\).

Напомена: У овом задатку, референцирани типови се сматрају једнаким само ако су им исте адресе, тј. само ако се ради о истом објекту у меморији (без обзира на могуће једнак садржај).

Помоћ: у имплементацији користити обичан ред (класа Queue) и скуп (класа HashSet).

2. Стек са максимумом

Написати генеричку класу StackWithMax<T>, која имплементира стек елемената типа T. Поред уобичајених функционалности стека, ова класа треба да има и метод GetMax, која враћа вредност највећег елемента са стека.

Сложеност свих операција треба да буде \(O(1)\).

Напомена: У овом задатку, приликом дефинисања генеричке класе треба писати

…да би унутар дефиниције класе могао да се користи метод CompareTo за објекте генеричког типа T. Овим је употреба класе ограничена само на типове који имају дефинисан метод CompareTo. Ово ограничење је природно, јер да би могло да се одреди који елемент стека је највећи, свакако мора да постоји поређење елемената по величини.

Помоћ: у имплементацији користити два обична стека (класа Stack).

3. Фреквенцијски стек

Написати генеричку класу FreqStack<T>, која имплементира колекцију налик на стандардни стек елемената типа T.

Класа треба да има следеће јавне методе:

bool Empty() - враћа true ако је колекција празна, иначе враћа false,
void Clear() - уклања све елементе из колекције,
void Push(T x) - додаје елемент x у колекцију, и
T Pop() - уклања из колекције елемент који се најчешће појављује од свих елемената који су тренутно на стеку. Ако је више таквих елемената, уклања се онај који је последњи додат од њих. Нпр. ако су редом додавани елементи 1 2 2 1 3, уклања се елемент 1 и садржај колекције је исти као да су додати 1 2 2 3.

Помоћ: у имплементацији користити листу стекова (List<Stack<T>>) и речник који броји појављивања сваког елемента на стеку (Dictionary<T, int>).

Претходна лекција Следећа лекција

Слова