//自定義隊列接口
namespace 隊列
{
  interface IQueue<T>
  {
    int Count { get; }
    int GetLength();
    bool IsEmpty();
    void Clear();
    void Enqueue(T item);
    T Dequeue();
    T Peek();
  }
}

//順序隊列的實現類
namespace 隊列
{
  class SeqQueue<T> : IQueue<T>
  {
    private T[] data;
    private int count; //表示當前有幾個元素
    private int front; //隊首  （隊首索引-1）
    private int rear;  //隊尾 （隊尾元素索引）
    public SeqQueue(int size)
    {
      data = new T[size];
      count = 0;
      front = -1;
      rear = -1;
    }
    public SeqQueue()
    {
      data = new T[10];
      count = 0;
      front = -1;
      rear = -1;
    }
    public int Count
    {
      get
      {
        return count;
      }
    }
    public void Clear()
    {
      count = 0;
      front = -1;
      rear = -1;
    }
    public T Dequeue()
    {
      if(count > 0)
      {
        T temp = data[front + 1];
        front++;
        count--;
        return temp;
      }
      else
      {
        Console.WriteLine("隊列中沒有數據，無法取得隊首數據");
        return default(T);
      }
    }
    public void Enqueue(T item)
    {
      if (count == data.Length)
      {
        Console.WriteLine("隊列元素已滿，不可添加");
      }
      else
      {
        if (rear == data.Length -1) //最后一個位置是否有值
        {
          data[0] = item;
          rear = 0;
          count++;
        }
        else
        {
          data[rear + 1] = item;
          rear += 1;
          count++;
        }
      }
    }
    public int GetLength()
    {
      return count;
    }
    public bool IsEmpty()
    {
      return count == 0;
    }
    public T Peek()
    {
      T temp = data[front + 1];
      return temp;
    }
  }
}

//鏈隊列的節點類
namespace 隊列
{
  class Node<T> {
    private T data;
    private Node<T> next;
    public Node(T data)
    {
      this.data = data;
    }
    public T Data
    {
      get { return data; }
      set { data = value; }
    }
    public Node<T> Next
    {
      get { return next; }
      set { next = value; }
    }
  }
}

//鏈隊列的實現類
namespace 隊列
{
  class LinkQueue<T> : IQueue<T>
  {
    private Node<T> front; //頭結點
    private Node<T> rear; //尾結點
    private int count; //表示元素個數
    public LinkQueue()
    {
      front = null;
      rear = null;
      count = 0;
    }
    public int Count
    {
      get
      {
        return count;
      }
    }
    public void Clear()
    {
      front = null;
      rear = null;
      count = 0;
    }
    public T Dequeue()
    {
      if (count == 0)
      {
        Console.WriteLine("隊列為空");
        return default(T);
      }else if(count == 1)
      {
        T temp = front.Data;
        front = rear = null;
        count = 0;
        return temp;
      }
      else
      {
        T temp = front.Data;
        front = front.Next;
        count--;
        return temp;
      }
    }
    public void Enqueue(T item)
    {
      Node<T> newNode = new Node<T>(item);
      if (count == 0)
      {
        front = newNode;
        rear = newNode;
        count = 1;
      }
      else
      {
        rear.Next = newNode;
        rear = newNode;
        count++;
      }
    }
    public int GetLength()
    {
      return count;
    }
    public bool IsEmpty()
    {
      return count == 0;
    }
    public T Peek()
    {
      if (front != null)
      {
        return front.Data;
      }
      else
      {
        return default(T);
      }
    }
  }
}

//以上兩個實現類的測試類
namespace 隊列
{
  class Program
  {
    static void Main(string[] args)
    {
      //CRL中的隊列
      //Queue<int> queue = new Queue<int>();
      //自己的寫的順序隊列
      //SeqQueue<int> queue = new SeqQueue<int>();
      //自己的鏈隊列
      LinkQueue<int> queue = new LinkQueue<int>();
      queue.Enqueue(12);
      queue.Enqueue(34);
      queue.Enqueue(56);
      queue.Enqueue(78);
      queue.Enqueue(90);
      Console.WriteLine("添加五個元素后的大小："+ queue.Count);
      int i = queue.Dequeue();  //出隊（取出并刪除）
      Console.WriteLine("取出的元素是： " + i);
      Console.WriteLine("出隊后隊列大小：" + queue.Count);
      int j = queue.Peek();
      Console.WriteLine("Peek取出的元素是： " + j);
      Console.WriteLine("PeeK后隊列大小：" + queue.Count);
      queue.Clear();
      Console.WriteLine("清空后的隊列大小：" + queue.Count);
      Console.ReadKey();
    }
  }
}