双向队列以及单调队列

Edit: 逆天,用LinkedList不就行了嘛？🤣👉

算法要deque 搞单调队列，自己写一个记在这里

• DequeNode 双向队列节点

  public class DequeNode<T> 
  {
      public T val;
      public DequeNode<T> next;
      public DequeNode<T> pre;
      public DequeNode(T value = default(T), DequeNode<T> net = null, DequeNode<T> pr = null)
      {
          val = value;
          next = net;
          pre = pr;
      }
  
  }

• Deque 双向队列

  public class Deque<T> 
  {   
  
      public int Count;
      private DequeNode<T> Front;
      private DequeNode<T> Back;
      
      public Deque()
      {
          Count = 0;
          Front = new DequeNode<T>();
          Back = new DequeNode<T>();
          Front.next = Back;
          Back.pre = Front;
      }
      public T PeekFront
      {
          get
          {
              if (Count == 0)
                  throw new InvalidOperationException();
              return Front.next.val;
          }
      }
  
      public T PeekBack
      {
          get
          {
              if (Count == 0)
                  throw new InvalidOperationException();
              return Back.pre.val;
          }
      }
  
      public void PushFront(T value)
      {
          Count++;
          DequeNode<T> n = new DequeNode<T>(value, Front.next, Front);
          Front.next = n;
          n.next.pre = n;
      }
      public void  PushBack(T value)
      {
          Count++;
          DequeNode<T> n = new DequeNode<T>(value, Back, Back.pre);
          Back.pre = n;
          n.pre.next = n;
      }
      public T PopFront()
      {
          if (Count == 0) throw new InvalidOperationException();
          Count--;
          var node = Front.next;
          node.next.pre = Front;
          Front.next = node.next;
          return node.val;
      }
      public T PopBack()
      {
          if (Count == 0) throw new InvalidOperationException();
          Count--;
          var node = Back.pre;
          Back.pre = node.pre;
          node.pre.next = Back;
          return node.val;
          
      }
  }

• MonotoneQue 单调递增队列

  public class MonotoneQue<T> where T :IComparable
  {
      private Deque<T> deque=new Deque<T> ();
      public T Front => deque.PeekFront;
  
      public void Pop(T value)
      {
          if(deque.Count!=0&& value.Equals(deque.PeekFront))
          {
              deque.PopFront();
          }
      }
  
      public void Push(T value)
      {
  
          while (deque.Count != 0 && value.CompareTo(deque.PeekBack) > 0)
              deque.PopBack();
          deque.PushBack(value);
      }
  }

• 数组实现也可以

• 迭代器TOO LAZY TO EDIT