using System;

//  פעולות שניתן להפעיל על תור מסוג שלמים
//  יצירת תור ריק
    // new Queue<int>()
// הכנסה לתור
    // Insert(int)
// הוצאה מהתור  
    // int Remove()
// האם התור ריק 
    // bool Isempty()
// בדיקה מה האיבר הראשון בתור  
    // int Head()
    
    // נסיון

class Program 
{
  public static void Main (string[] args) 
  {
    Queue<int> q1 = new Queue<int>();
    Console.WriteLine("Empty q /: " + q1); // הדפסת תור ריק
    Console.WriteLine("q1 is empty ? : " + q1.IsEmpty());
    q1.Insert(5);
    q1.Insert(6);
    Console.WriteLine(q1);
    Console.WriteLine("q1 is empty ? : " + q1.IsEmpty());
    q1.Remove();
    Console.WriteLine("after remove: " + q1);
    q1.Insert(7);
    Console.WriteLine(q1);
    
    Console.WriteLine("=============================");
    Console.WriteLine("Examples of methods on Queues:");
    Console.WriteLine("=============================");
    int[] arr = {5,-3,9,5,8,-1};
    Queue<int> q2 = ArrayToQ(arr);
    Console.WriteLine("q2: " + q2);
    Console.WriteLine("number of items in q2: " + Size(q2));
    Console.WriteLine("q2: " + q2);
    Queue<int> q4 = CopyQ(q2);
    Console.WriteLine("q4 - copy of q2: " + q4);
    RemoveItemFromQ(q4,5);
    Console.WriteLine("q4 after removing 5: " + q4);
    
    Queue<int> q3 = CopyPositiveQ(q2);
    Console.WriteLine("q3 copy postive numbers from q2: " + q3);
    Console.WriteLine("q2 : " + q2);
    Queue<int> q5 = CopyPositiveQ2(q2);
    Console.WriteLine("q5 copy postive numbers from q2 , implementation #2: " + q5);
    Console.WriteLine("q2 : " + q2);
    
    ReverseQ(q2);
    Console.WriteLine("q2 reversed (using recurssion): " + q2);
  }
  
  
  // פעולה שמחזירה את מספר האיברים בתור
  public static int Size(Queue<int> q)  
  {
    Queue<int> q1 = new Queue<int>(); // יצירת תור עזר חדש ריק  
    int count = 0;
    while(!q.IsEmpty())
    {
      count++;
      q1.Insert(q.Remove()); // העברה לתור עזר
    }
    while(!q1.IsEmpty()) // שחזור התור המקורי
    {
      q.Insert(q1.Remove());
    }
    return count;
  }
  
  // create queue of int from array of int
  static Queue<int> ArrayToQ(int[] arr)
  {
    Queue<int> q = new Queue<int>();
    for(int i=0;i<arr.Length;i++)
    {
      q.Insert(arr[i]);
    }
    return q;
  }
  
  
  // CopyQ 
  // העתקת תור
  static Queue<int> CopyQ(Queue<int> q)
  {
    Queue<int> retQ = new Queue<int>(); // התור המועתק החדש
    Queue<int> tempQ = new Queue<int>(); // תור לטובת שחזור התור המקורי
    
    while(!q.IsEmpty())
    {
      int n = q.Head();
      retQ.Insert(n);
      tempQ.Insert(n);
      q.Remove();
    }
    // שחזור התור
    while(!tempQ.IsEmpty())
    {
      q.Insert(tempQ.Remove());
    }
    
    return retQ ;
  }
  // CopyQ 
  // העתקת תור פעולה גנרית - מתאימה לכל סוג
  static Queue<T> CopyQ<T>(Queue<T> q)
  {
      Queue<T> q2 = new Queue<T>();
      Queue<T> q3 = new Queue<T>();
      while (!q.IsEmpty())
      {
          T x = q.Remove();
          q2.Insert(x);
          q3.Insert(x);
      }
      while (!q2.IsEmpty())
          q.Insert(q2.Remove());

      return q3;
  }
  
  static void RemoveItemFromQ(Queue<int> q, int x)
  {
    Queue<int> tempQ = new Queue<int>();
    while(!q.IsEmpty())
    {
      if(q.Head() != x)
      {
        tempQ.Insert(q.Head());
      }
      q.Remove();
    }
    while(!tempQ.IsEmpty()) // שחזור התור
    {
      q.Insert(tempQ.Remove());
    }
  }
  
  // מקבלים תור של שלמים
  // מחזירים תור אחר שמכיל רק את המספרים החיוביים
  static Queue<int> CopyPositiveQ(Queue<int> q)
  {
    Queue<int> retQ = new Queue<int>();
    Queue<int> tempQ = new Queue<int>();
    
    while(!q.IsEmpty())
    {
      int n = q.Head();
      if (n > 0)
      {
        retQ.Insert(n);
      }
      tempQ.Insert(q.Remove());
    }
    while(!tempQ.IsEmpty())
    {
      q.Insert(tempQ.Remove());
    }
    
    return retQ ;
  }
  
  // מקבלים תור של שלמים
  // מחזירים תור אחר שמכיל רק את המספרים החיוביים
  static Queue<int> CopyPositiveQ2(Queue<int> q)
  {
    Queue<int> retQ = new Queue<int>();
    Queue<int> tempQ = CopyQ(q);
    
    while(!tempQ.IsEmpty())
    {
      int n = tempQ.Remove();
      if (n > 0)
      {
        retQ.Insert(n);
      }
    }
    return retQ ;
  }
  
    // הופך את סדר האיברים בתור
  // מימוש רקורסיבי
  public static void ReverseQ(Queue<int> q)
  {
    if(!q.IsEmpty())
    {
      int x = q.Remove();
      ReverseQ(q);
      q.Insert(x);
    }
  }
  
  // שיטה נוספת למעבר על תור
  // (מעגלי) מעבר ציקלי 
  public static int CountQ2(Queue<int> q)  
  {
    
    int count = 0;
    q.Insert(-999); // הכנסת איבר "דמה" לתור. חשוב:איבר הדמה חייב להיות כזה שלא ייתכן שנכלל בתור המקורי
    while(q.Head() != -999)
    {
      count++;
      q.Insert(q.Remove()); // העברת האיבר הראשון בתור לסוף התור
    }
    q.Remove(); // הסרת איבר הדמה
    
    return count;
  }
  // מימוש רקורסיבי
  // התור המקורי לא נשמר
  public static int CountQ3(Queue<int> q)  
  {
    if(q.IsEmpty())
      return 0;
    q.Remove();
    return 1+CountQ3(q);
  }
  
}