\Section{Очередь  минимумом}{20 сентября}{Илья Ольховский}
	Нам нужна структура данных, которая умеет делать следующие операции:
	\begin{enumerate}
		\item $push\_back(a)$ - добавить элемент $a$ в конец
		\item $front()$ - узнать, какой элемент стоит в начале
		\item $pop\_front()$ - удалить элемент, который стоит в начале, из структуры
		\item $get\_min()$ - узнать, минимум среди всех элементов в структуре
	\end{enumerate}
	Причём амортизированная сложность (время работы) всех операций должна быть $\mathcal{O}(1)$.

	\Subsection{Алгоритм}
	
	
	  Для того, чтобы решить эту задачу, пристроим к обычной очереди дек. В очереди мы честно будем хранить все элементы, а в деке мы будем хранить все элементы, которые когда-нибудь могут стать минимумами. Причём элементы в деке хранятся в порядке добавления в очередь и возрастают.
	  
	   В чём идея? Пусть в конец очереди добавился элемент, который меньше последнего. То есть произошло следующее:
	\begin{enumerate}
	   		\item $push\_back(a)$
	   		
	   		$ \cdots $
	   		\item $push\_back(b)$
	   		\item $a\ge b$
	 \end{enumerate}
	   	Тогда элемент $a$ больше не влияет на минимум. Действительно, так как $a$ ближе к началу очереди, чем $b$, то $a$ удалится из очереди раньше $b$, а пока $b$ находится в очереди, $min\le b \le a$. 
	   	
	 Теперь, кажется, понятно, как добавлять элементы в дек. Мы знаем, что элементы там отсортированы от начала к концу (база - один элемент). Поэтому можно просто удалить весь суффикс\footnote{отрезок  $i\ldots n-1$} дека, элементы которого меньше нового (они минимумами уже никогда не станут) и добавить новый в конец. Ясно, что после этой операции дек сохранит все нужные нам свойства.
	  
	   Итак, мы имеем очередь $Q$ и дек $M$. Как выглядят наши операции:
	\begin{itemize}
		\item $push\_back(a)$ - добавим $a$ в конец $Q$, удалим из $M$ суффикс, элементы которого меньше $a$ и добавим $a$ в конец $M$.
		\item $front()$ - $Q.front()$.
		\item $pop\_front()$ - сделать $Q.pop\_front()$ и проверить, надо ли удалить первый элемент $M$. Это можно сделать так: присвоим каждому элементу уникальный номер (например время добавления) и будем делать $M.pop\_front()$, если $M.front().ID == Q.front().ID$.
		\item $get\_min()$ - $M.front()$ 
	\end{itemize}
	\Subsection{Псевдокод}
	\begin{verbatim}
\\ Q - очередь, M - дек, Time - глобальная переменная "времени"
	  push_back(a){
		      while (!M.empty() && M.back().value > a) M.pop_front();
		      Q.push_back(a, Time);
		      M.push_back(a, Time);
		      Time++;
	  }
	  
	  front(){
		      return Q.front().value;
	  }
	  
	  get_min(){
		      return M.front().value;
	  }
	  
 pop_front(){
      if (Q.front().Time == M.front().Time) M.pop_front();
      Q.pop_front();
	  }
	  \end{verbatim}
	  \Subsection{Асимптотика}
	  
	  
	  Из кода видно, что всё, кроме $push\_back()$ работает за $\mathcal{O}(1)$. D цикле $while$ в $push\_back()$ мы удаляем элементы из дека. Ясно, что мы не сможем удалить более $N$ элементов, так как каждый элемент можно удалить не более одного раза. Поэтому $while$ в сумме отработает за $\mathcal{O}(N)$. На языке амортизации:
	  $$\varphi(n)=M.size()$$
	  C каждой итерацией $while$ $t(n)$ увеличивается на 1, а $\Delta \varphi$ - уменьшается на 1.
	  $$\alpha(n)=\Delta \varphi+t(n)=\mathcal{O}(1)$$
	  $$\sum\limits_{n=1}^N t(n)=\sum\limits_{n=1}^N\alpha(n)+\varphi_0-\varphi_N\le N\cdot\mathcal{O}(1)+N-0=\Theta(N)$$

