队列

队列又称为“先进先出”(FIFO)线性表
限定插入操作只能在队尾进行，而删除操作只能在队首进行，Front对头指针指向第一元素；Rear队尾指针指向下一个入队的元素。
队列也可以采用顺序存储结构或链表结构来实现，分别称为顺序队列和链队列
空队列：front == rear;

 

顺序队列

用一组连续的存储单元依次存放从队首到队尾的元素，附设两个指针head和tail分别指向队首元素和队尾元素的位置，
(有的地方用front 和 rear 表示)

Front是处于队头的数据元素的下标 简称对头下标，rear 不是当前队尾元素的下标，而是下一个入队的数据元素下标。

顺序队列中出现的剩余存储空间但不能进行新的入队操作的溢出称为假溢出。循序循环队列为了解决假溢出的方案。

 

 

 

 

 循环队列

所谓 的顺序循环队列，是通过取模操作，将为顺序队列所分配的连续存储空间，变成一个逻辑上首位相连的“环形”队列。

为了实现顺序队列循环利用存储空间，进行入队和出队操作时，front和rear 不是简单的加1，而是加1后取模做取模操作。即如下操作：

IsFull: front== (rear + 1) % item.Length;
IsEmpty:front == rear;
Count: (rear - front + item.Length) % item.Length;

自定义循环队列

using System; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Drawing.Drawing2D; using System.IO; using System.Text; using System.Threading; using System.Xml; using System.Xml.XPath; namespace LinearList; public class Sample {     public static void Main()     {         SequencedQueue<int> queue = new SequencedQueue<int>();         for (int i = 0; i < 20; i++)         {             queue.Enqueue(i);         }         queue.Print();             }   public class SequencedQueue<T>     {         private T[] item;         private int front, rear;         public bool IsEmpty { get=> front == rear;  }         public int Count => (rear - front + item.Length) % item.Length;               public bool IsFull=>front== (rear + 1) % item.Length;                 public SequencedQueue():this(6)         {                          }         public SequencedQueue(int capacity)         {             item = new T[capacity];           }         //入队 尾部入队         public void Enqueue(T it )         {             if (IsFull) DoubleCapacity();             item[rear ] = it ;             rear = (rear + 1) % item.Length;          }         //出队 头部出队         public T Dequeue()         {             if (IsEmpty) throw new OverflowException(queue is Empty + item.GetType());             T k= item[front];             front = (front + 1) % item.Length;             return k;         }         public void DoubleCapacity()         {             T[] newarray= new T[Count*2];             Array.Copy(item, 0, newarray, 0, item.Length);             item = newarray;         }         public T Peek()         {             if (IsEmpty) throw new OverflowException(queue is Empty + item.GetType());             return item[front];         }         public void Print()         {             if (IsEmpty) Console.WriteLine(IsEmpty);             int n = front;             for(int i = 0; i < Count; i++)             {                                 Console.WriteLine(item[n]);                 n = (n + 1) % item.Length;             }           }     } }

View Code

 链式队列

 

 

 

 

 

 

判断链式队列为空：如果有hend节点 head=font=rear=null。如果没有hend节点 font=rear=null

 应用

用顺序独立实现素数环