详解4种队列实现方式

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。队列分为顺序队列和循环队列两种，4种队列实现方式，分别为：顺序队列、循环队列、链表队列和数组队列。

下面我们一一来看4种队列实现方式：

1.顺序队列

using System;

public class QueueLine<T>: IQueue<T>

{

    private int count;

    private int front;

    private int rear;

    public T[] data;

    public int size;

    public QueueLine(int size)

    {

        data = new T[size];

        this.size = size;

        count = 0;

        front = -1;

        rear = -1;

    }

    //默认创建10个

    public QueueLine() : this(10)

    {

    }

    public int Count

    {

        get =>count;

    }

    public int Size

    {

        get => size;

    }

    public int GetLength()

    {

        return count;

    }

    public bool IsEmpty()

    {

        return count == 0;

    }

    public void Clear()

    {

        count = 0;

        front = rear = -1;

    }

    public bool IsFull()

    {

        return count == size;

    }

    public void EnQueue(T elem)

    {

        if (IsFull())

        {

            Console.WriteLine("队列已满");

            return;

        }

        data[++rear] = elem;

        count++;

    }

    public T DeQueue()

    {

        if (count > 0)

        {

            T temp = data[front + 1];

            front++;

            count--;

            return temp;

        }

        else

        {

            Console.WriteLine("队列为空，无法取得队首元素");

            return default(T);

        }

    }

    public T Peek()

    {

        if (IsEmpty())

        {

            Console.WriteLine("队列为空，无法取得队首元素");

            return default(T);

        }

        return data[front + 1];

    }

}

2.循环队列

using System;

public class QueueLoop<T> : IQueue<T>

{

    private int maxSize; //循环队列的容量

    private T[] data; //数组，存储数据元素

    private int front; //指示最近一个已经离开队列的元素所占有的位置  循环顺序队列的对头

    private int rear; //指示最近一个进入队列的元素的位置  循环顺序队列的队尾

    public T this[int index]

    {

        get { return data[index]; }

        set { data[index] = value; }

    }

    public int MaxSize

    {

        get => maxSize;

        set => maxSize = value;

    }

    public int Front

    {

        get => front;

        set => front = value;

    }

    public int Rear

    {

        get => rear;

        set => rear = value;

    }

    public QueueLoop()

    {

    }

    public QueueLoop(int size)

    {

        data = new T[size];

        maxSize = size;

        front = rear = -1;

    }

    public void EnQueue(T elem)

    {

        if (IsFull())

        {

            Console.WriteLine("Queue is Full!");

            return;

        }

        rear = (rear + 1) % maxSize;

        data[rear] = elem;

    }

    public T DeQueue()

    {

        if (IsEmpty())

        {

            Console.WriteLine("Queue is Empty!");

            return default(T);

        }

        front = (front + 1) % maxSize;

        return data[front];

    }

    public T Peek()

    {

        if (IsEmpty())

        {

            Console.WriteLine("Queue is Empty!");

            return default(T);

        }

        return data[(front + 1) % maxSize];

    }

    public int GetLength()

    {

        return (rear - front + maxSize) % maxSize;

    }

    public bool IsEmpty()

    {

        return front == rear;

    }

    public void Clear()

    {

        front = rear = -1;

    }

    //判断循环队列是否已满

    public bool IsFull()

    {

        return (front == -1 && rear == maxSize - 1) || (rear + 1) % maxSize == front;

    }

}

3.链表队列

using System;

public class QueueLink<T> : IQueue<T>

{

    private QueueNode<T> front;

    private QueueNode<T> rear;

    private int size;

    public QueueNode<T> Front

    {

        get => front;

        set => front = value;

    }

    public QueueNode<T> Rear

    {

        get => rear;

        set => rear = value;

    }

    public int Size

    {

        get => size;

        set => size = value;

    }

    public QueueLink()

    {

        front = rear = null;

        size = 0;

    }

    public void EnQueue(T elem)

    {

        QueueNode<T> q = new QueueNode<T>(elem);

        if (IsEmpty())

        {

            front = q;

            rear = q;

        }

        else

        {

            rear.Next = q;

            rear = q;

        }

        size++;

    }

    public T DeQueue()

    {

        if (IsEmpty())

        {

            Console.WriteLine("Queue is Empty!");

            return default(T);

        }

        QueueNode<T> p = front;

        front = front.Next;

        if (front == null)

        {

            rear = null;

        }

        --size;

        return p.Data;

    }

    public T Peek()

    {

        if (IsEmpty())

        {

            Console.WriteLine("Queue is Empty!");

            return default(T);

        }

        return front.Data;

    }

    public int GetLength()

    {

        return size;

    }

    public bool IsEmpty()

    {

        return front == rear && size == 0;

    }

    public void Clear()

    {

        front = rear = null;

    }

    //由于链表不存在满的情况

    public bool IsFull()

    {

        return false;

    }

}

public class QueueNode<T>

{

    private T data; //数据域

    private QueueNode<T> next; //指针域

    public QueueNode(T val, QueueNode<T> p)

    {

        data = val;

        next = p;

    }

    public QueueNode(QueueNode<T> p)

    {

        next = p;

    }

    public QueueNode(T val)

    {

        data = val;

    }

    public QueueNode()

    {

        data = default(T);

        next = null;

    }

    public T Data

    {

        get => data;

        set => data = value;

    }

    public QueueNode<T> Next

    {

        get => next;

        set => next = value;

    }

}

4.数组队列

用 head、tail、count 分别代表队首、队尾、队列中的元素个数，在 QueueStudy 实例对象构造时将数组大小初始化。class QueueStudy

{

    private int[] queue ; // 数组队列

    private int head; // 队首

    private int tail; // 队尾

    private int count; // 队列元素

    public QueueStudy(int len)

    {

        queue = new int[len];

        head = 0;

        tail = 0;

        count = 0;

    }

    public void push(int element)

    {

        if(tail== queue.length)

            System.out.println("队列已满，无法入队");

        else{

            queue[tail++] = element;

            count++;

        }

    }

    public int pop()

    {

        if(tail== 0)

            return -1 ; // 这里用 -1 代表无元素可出队

        int num = queue[head++];

        count--;

        return num;

    }

    public int peek()

    {

        if(count == 0)

            return -1 ; // 这里用 -1 代表队首无元素

        return queue[head];

    }

    public Boolean isEmpty()

    {

        return count==0;

    }

    public int size()

    {

        return count;

    }

}

因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。因此，在某种程度上，队列也有着线性表的基本性质，想要了解更多的队列相关的知识，可以观看本站的数据结构和算法教程，快速掌握各种数据结构的知识。