\Section{Очередь с минимумом}{14 февраля}{Горохов Никита}

\Subsection{Стек с поддержанием минимума}

Структура данных, реализующая возможности стека, но модифицированная для нахождения минимума среди всех элементов в стеке за $\O(1)$.

\down

Идея состоит в том, чтобы поддерживать сразу два стека. Первый стек содержит в себе элементы как они есть. Второй же содержит в себе <<частичные минимумы>>, то есть минимумы на отрезке от вершины стека до позиции элемента. Назовём эти два стека $a$ и $min$. 

\down

Рассмотрим пример. Пусть мы добавили поочередно элементы 1, 9, 3, 8, 9, 4, 5, 7. Тогда стеки будут выглядеть следующим образом:

\texttt{$a:\ \ $ 7 5 4 9 8 3 9 1}

\texttt{$min:$ 7 5 4 4 4 3 3 1}  

\down

\THE{Реализация методов}

\begin{code}
void push(T x) {
	a.push(x);
	min.push(min(min.top(), x));
}

T min() {
	return min.top();
}

T pop() {
	min.pop();
	return a.pop();
}

T top() {
	return a.top();
}
\end{code}

\pagebreak

\Subsection{Очередь с поддержанием минимума}

Структура данных, реализующая возможности очереди, но модифицированная для нахождения минимума среди всех элементов в очереди за амортизированное $\O(1)$.

\down

Идея состоит в том, чтобы научится реализовывать очередь с помощью двух стеков. Тогда если вместо обычных стеков взять стеки с поддержанием минимума, то очередь также сможет поддерживать минимум.

\down

\THE{Реализация очереди с помощью двух стеков}

Заведём два стека: $a$ и $b$. Добавлять новые элементы будем всегда в стек $b$, а извлекать элементы -- только из стека $a$. При этом, если при попытке извлечения элемента из стека $a$ он оказался пустым, просто перенесём все элементы из стека $b$ в стек $a$ (при этом элементы в стеке $a$ получатся уже в обратном порядке, что нам и нужно для извлечения элементов; стек $b$ же станет пустым).

\down

\THE{Реализация методов}

\begin{code}
void push(T x) {
	b.push(x);
}

T pop() {
	if (a.size() == 0)
		while(b.size() > 0)
			a.push(b.pop());
	return a.pop();
}
\end{code} 

\down

\THE{Время работы}

Все методы работают за амортизированное $\O(1)$. Объясняется это тем, что каждый элемент за время работы очереди один раз попадёт в стек $b$, один раз перейдёт в стек $a$ и один раз покинет его. Таким образом, если всего элементов $n$, то стек затратит на выполнение всех операций $\O(n)$ времени, то есть $\O(1)$ на каждую операцию в среднем.