一、队列（Queue）

        像堆栈一样，队列是一个线性结构，它遵循执行操作的特定顺序。 顺序是先进先出 (FIFO)。

        队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分，队列结构包括两类。

        ・顺序队列结构：即使用一组地址连续的内存单元依次保存队列中的数据。在程序中，可以定义一个指定大小的结构数组作为队列。

        ・链式队列结构：即使用链表形式保存队列中各元素的值。

        队列应用广泛，从打印机的作业设置，到网络应用程序的后台任务，都有队列的存在。 

二、队列操作

        对队列主要进行以下四个基本操作：

        Enqueue：将项目添加到队列中。 如果队列已满，则称其为溢出条件。

        Dequeue：从队列中删除一个项目。 项目的弹出顺序与它们被推送的顺序相同。 如果队列为空，则称其为下溢条件。

        Front：从队列中获取最前面的项目。

        Rear：从队列中获取最后一项。

三、实现队列

1、数组实现

（1）出入队列可视化

 （2）代码参考

        使用java代码进行实现

// Java program for array
// implementation of queue

// A class to represent a queue
class Queue {
	int front, rear, size;
	int capacity;
	int array[];

	public Queue(int capacity)
	{
		this.capacity = capacity;
		front = this.size = 0;
		rear = capacity - 1;
		array = new int[this.capacity];
	}

	// Queue is full when size becomes
	// equal to the capacity
	boolean isFull(Queue queue)
	{
		return (queue.size == queue.capacity);
	}

	// Queue is empty when size is 0
	boolean isEmpty(Queue queue)
	{
		return (queue.size == 0);
	}

	// Method to add an item to the queue.
	// It changes rear and size
	void enqueue(int item)
	{
		if (isFull(this))
			return;
		this.rear = (this.rear + 1)
					% this.capacity;
		this.array[this.rear] = item;
		this.size = this.size + 1;
		System.out.println(item
						+ " enqueued to queue");
	}

	// Method to remove an item from queue.
	// It changes front and size
	int dequeue()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		int item = this.array[this.front];
		this.front = (this.front + 1)
					% this.capacity;
		this.size = this.size - 1;
		return item;
	}

	// Method to get front of queue
	int front()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.front];
	}

	// Method to get rear of queue
	int rear()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.rear];
	}
}

// Driver class
public class Test {
	public static void main(String[] args)
	{
		Queue queue = new Queue(1000);

		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		queue.enqueue(40);

		System.out.println(queue.dequeue()
						+ " dequeued from queue\n");

		System.out.println("Front item is "
						+ queue.front());

		System.out.println("Rear item is "
						+ queue.rear());
	}
}

        数组实现的缺点：  

        1、静态数据结构，固定大小。

        2、如果队列有大量的入队和出队操作，在某些时候（在前后索引线性递增的情况下）我们可能无法在队列中插入元素，即使队列是空的（这个问题可以避免通过使用循环队列）。

2、链表实现

（1）出入队列可视化

 （2）代码参考

// A linked list (LL) node to store a queue entry
class QNode {
    int key;
    QNode next;
 
    // constructor to create a new linked list node
    public QNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
// A class to represent a queue
// The queue, front stores the front node of LL and rear stores the
// last node of LL
class Queue {
    QNode front, rear;
 
    public Queue()
    {
        this.front = this.rear = null;
    }
 
    // Method to add an key to the queue.
    void enqueue(int key)
    {
 
        // Create a new LL node
        QNode temp = new QNode(key);
 
        // If queue is empty, then new node is front and rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
 
        // Add the new node at the end of queue and change rear
        this.rear.next = temp;
        this.rear = temp;
    }
 
    // Method to remove an key from queue.
    void dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
            return;
 
        // Store previous front and move front one node ahead
        QNode temp = this.front;
        this.front = this.front.next;
 
        // If front becomes NULL, then change rear also as NULL
        if (this.front == null)
            this.rear = null;
    }
}
 
// Driver class
public class Test {
    public static void main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.dequeue();
        q.dequeue();
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);
        q.dequeue();
        System.out.println("Queue Front : " + q.front.key);
        System.out.println("Queue Rear : " + q.rear.key);
    }
}

四、其它队列类型

1、循环队列

        在循环队列中，所有节点都表示为循环。它类似于线性队列，只是队列的最后一个元素连接到第一个元素。它也称为环形缓冲区，因为所有端都连接到另一端。循环队列的表示如下图所示 -

        使用循环队列克服了线性队列中出现的缺点。如果循环队列中有可用的空白空间，则可以通过简单地增加rear的值将新元素添加到空白空间中。使用循环队列的主要优点是更好的内存利用率。

2、双端队列

         双端队列是一种线性数据结构，插入和删除操作都是从两端进行的。

        虽然在一个双端队列中的插入和删除都可以在两端进行，但它并不遵循先进先出规则。

        有两种类型的双端队列

        输入受限队列

        在输入受限队列中，只能在一端进行插入操作，而从两端都可以进行删除操作。

         输出受限队列 

        在输出受限队列中，删除操作只能在一端进行，而插入则可以从两端进行。

3、优先队列

        优先队列是一种特殊类型的队列，其中元素根据优先级排列。它是一种特殊类型的队列数据结构，其中每个元素都有一个与之关联的优先级。假设某些元素以相同的优先级出现，它们将按照先进先出原则进行排列。优先队列的表示如下图所示 -

        优先队列中的插入基于到达发生，而优先队列中的删除基于优先级发生。优先级队列主要用于实现 CPU 调度算法。

        升序优先级队列 -在升序优先级队列中，可以按任意顺序插入元素，但只能先删除最小的元素。假设一个数组的元素 7、5、3 的顺序相同，那么，插入可以按照相同的顺序进行，但删除元素的顺序是 3、5、7。
        降序优先级队列 -在降序优先级队列中，可以按任意顺序插入元素，但只能先删除最大的元素。假设一个数组中元素 7、3、5 的顺序相同，那么，插入可以按照相同的顺序进行，但删除元素的顺序是 7、5、3。