Обычная очередь имеет несколько реализаций, среди них существует реализация на двух стеках. Эти два стека обычно называют либо LeftStack и RightStack, либо PushStack и PopStack. Мы будем использовать второй вариант.
Данную реализацию можно модифицировать, добавив два дополнительных стека PushAssociativeStack и PopAssociativeStack.
Значение AssociativeStack[i] (i-ый элемент стека, где AssociativeStack[0] - первый добавленый элемент) равняется f(Stack[i], AssociativeStack[i - 1]), где функция f обладает свойством ассоциативности. Первый элемент вычисляется как AssociativeStack[0] = Stack[0].
Таким образом, значение ассоциативной операции на множестве элементов очереди, то есть значение ассоциативной функции f(Queue[0], Queue[1], ..., Queue[n - 1]), будет равняться f(PushAssociativePeek, PopAssociativePeek), где аргументами функции являются последние элементы ассоциативных стеков.
Итого, мы получаем очередь, которая умеет вычислять значение ассоциативной операции (например, нахождение максимума или минимума) на множестве элементов очереди за O(1) при условии, что операция тоже совершается за константное время.
Приложение предназначено для взаимодействия с ассоциативной очередью, содержащую неотрицательные числа.
Приложение написано на WPF'е в соответствии c паттерном MVVM.
- VisualizationAssociativeQueue - WPF-приложение, основной проект.
- CollectionLibrary - библиотека коллекций, в ней реализованы ассоциативные и наблюдаемые (реализующие INotifyCollectionChanged) стеки и очереди.
- TestCollectionLibrary - юнит-тестирование библиотеки коллекций.
- AssociativeLibrary - библиотека, предоставляющая интерфейс IAssociativeOperation<T>.
- ForeignLibraries - библиотеки классов, реализующие IAssociativeOperation<int>.
- ArithmeticOperationLibrary - библиотека арифметических операций.
- BitwiseOperationLibrary - библиотека побитовых операций.
Основной проект заранее не знает об ForeignLibraries (в зависимостях их нет), поэтому они указаны как внешние.
VisualizationAssociativeQueue получает ассоциативные операции благодаря конфигу, в котором указаны пути до сборок, от которых ожидается содержание классов, реализующие интерфейс IAssociativeOperation<int>.
Таким образом, сторонний разработчик может добавить в приложение свои ассоциативные операции, не имея доступа к исходникам самого приложения, указав в конфиге пути до своих сборок.