队列-顺序表可视化交互式动画版

与Stack 类似， Queue 是一种线性数据结构，遵循特定的顺序执行存储数据的操作。顺序是先进先出 （FIFO） 。

人们可以将队列想象成一队人从队列的开头开始按顺序等待接收某些东西。它是一个有序列表，其中插入是在一端（称为后部）完成的，删除是从另一端（称为前部）完成的。队列的一个很好的例子是资源的任何消费者队列，其中先到达的消费者首先得到服务。
栈和队列的区别在于删除。在堆栈中，我们删除最近添加的项目；在队列中，我们删除最近最少添加的项目。

队列数据结构

队列的基本操作：

enqueue()： 将一个元素插入到队列的末尾，即后端。
dequeue()： 此操作删除并返回位于队列前端的元素。
front()： 该操作返回前端的元素，但不删除它。
after()： 该操作返回后端的元素，但不删除它。
isEmpty()： 该操作指示队列是否为空。
isFull()： 该操作指示队列是否已满。
size()： 此操作返回队列的大小，即队列包含的元素总数。

队列类型：

简单队列： 简单队列也称为线性队列，是队列的最基本版本。这里，插入元素即入队操作发生在后端，移除元素即出队操作发生在前端。这里的问题是，如果我们从前面弹出一些项目，然后后面达到队列的容量，虽然前面有空白意味着队列未满，但根据 isFull() 函数中的条件，它将显示那么队列已满。为了解决这个问题我们使用循环队列。
循环队列 ：在循环队列中，队列的元素充当圆环。循环队列的工作原理与线性队列类似，只是最后一个元素连接到第一个元素。它的优点是可以更好地利用内存。这是因为如果存在空白空间，即如果队列中的某个位置不存在元素，则可以使用模容量（%n）轻松地在该位置添加元素。
优先队列 ：该队列是一种特殊类型的队列。它的特点是它根据某种优先级排列队列中的元素。优先级可以是具有最高值的元素具有优先级，因此它创建一个按值降序排列的队列。优先级也可以是具有最低值的元素获得最高优先级，因此它依次创建一个值顺序递增的队列。在预定义优先级队列中，C++优先考虑最高值，而Java优先考虑最低值。
出队：出队也称为双端队列。顾名思义，双端队列意味着可以从队列的两端插入或删除一个元素，这与其他队列只能从一端插入或删除元素不同。由于此属性，它可能不遵守先进先出属性。

队列的应用：

当事物不需要立即处理，但必须像广度优先搜索那样以先入先出的顺序处理时，就会使用队列。队列的这一属性使其在以下场景中也很有用。

当资源在多个消费者之间共享时。示例包括 CPU 调度、磁盘调度。
当数据在两个进程之间异步传输时（数据接收速率不一定与发送速率相同）。示例包括 IO 缓冲区、管道、文件 IO 等。
队列可以用作各种其他数据结构的重要组成部分。

队列的数组实现：

为了实现队列，我们需要跟踪两个索引：前索引和后索引。我们在后面将一个项目入队，并从前面将一个项目出队。如果我们只是简单地增加前部和后部索引，那么可能会出现问题，前部可能会到达数组的末尾。解决这个问题的办法就是以循环的方式增加前后。

入队步骤：

检查队列是否已满
如果已满，则打印溢出并退出
如果队列未满，则增加tail并添加元素

出队步骤：

检查队列是否为空
如果为空，则打印下溢并退出
如果不为空，则打印头部元素并增加头部

下面是一个在队列上实现上述操作的程序

C++

              
                
                    // CPP program for array
                        
// implementation of queue
                        
#include <bits/stdc++.h>
using namespace std;
 
// A structure to represent a queue
class Queue {
public:
    int
                          front, rear, size;
    unsigned capacity;
    int* array;
};
 
// function to create a queue
// of given capacity.
                        
// It initializes size of queue as 0
Queue* createQueue(unsigned capacity)
{
    Queue* queue = new Queue();
    queue->capacity = capacity;
    queue->front = queue->size = 0;
 
    // This is important, see the enqueue
    queue->rear = capacity - 1;
    queue->array = new int[queue->capacity];
    return queue;
}
 
// Queue is full when size
                        
// becomes equal to the capacity
int isFull(Queue* queue)
{
    return (queue->size == queue->capacity);
}
 
// Queue is empty when size is 0
int isEmpty(Queue* queue)
{
    return (queue->size == 0);
}
 
// Function to add an item to the queue.
// It changes rear and size
void enqueue(Queue* queue, int item)
{
    if
                          (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)
                  % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    cout << item << " enqueued to queue\n";
}
 
// Function to remove an item from queue.
// It changes front and size
int dequeue(Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    int
                          item = queue->array[queue->front];
    queue->front = (queue->front + 1)
                   % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}
 
// Function to get front of queue
int front(Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}
 
// Function to get rear of queue
int rear(Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}
 
// Driver code
int main()
{
    Queue* queue = createQueue(1000);
 
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
 
    cout << dequeue(queue)
         << " dequeued from queue\n";
 
    cout << "Front item is "
         << front(queue) << endl;
    cout << "Rear item is "
         << rear(queue) << endl;
 
    return 0;
}
 
// This code is contributed by rathbhupendra

                  

              
            

C

              
                
                    // C program for array implementation of queue
#include <limits.h>
#include <stdio.h>
                        
#include <stdlib.h>
 
// A structure to represent a queue
struct Queue {
    int
                          front, rear, size;
    unsigned capacity;
    int* array;
};
 
// function to create a queue
// of given capacity.
                        
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
    struct Queue* queue = (struct Queue*)malloc(
        sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
 
    // This is important, see the enqueue
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(
        queue->capacity * sizeof(int));
                        
    return queue;
}
 
// Queue is full when size becomes
// equal to the capacity
                        
int isFull(struct Queue* queue)
{
    return (queue->size == queue->capacity);
}
 
// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{
    return (queue->size == 0);
}
 
// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
    if
                          (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)
                  % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}
 
// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    int
                          item = queue->array[queue->front];
    queue->front = (queue->front + 1)
                   % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}
 
// Function to get front of queue
int front(struct Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}
 
// Function to get rear of queue
int rear(struct Queue* queue)
{
    if
                          (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}
 
// Driver program to test above functions./
int main()
{
    struct Queue* queue = createQueue(1000);
 
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
 
    printf("%d dequeued from queue\n\n",
           dequeue(queue));
 
    printf("Front item is %d\n", front(queue));
    printf("Rear item is %d\n", rear(queue));
 
    return 0;
}

                  

              
            

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());
    }
}
 
// This code is contributed by Gaurav Miglani

                  

              
            

Python3

              
                
                    # Python3 program for array implementation of queue
 
# Class Queue to represent a queue
class Queue:
 
    # __init__ function
    def
                          __init__(self, capacity):
        self.front =
                          self.size = 0
        self.rear =
                          capacity -1
                        
        self.Q = [None]*capacity
        self.capacity = capacity
     
    # Queue is full when size becomes
    # equal to the capacity 
    def
                          isFull(self):
        return self.size ==
                          self.capacity
     
    # Queue is empty when size is 0
    def
                          isEmpty(self):
        return self.size ==
                          0
 
    # Function to add an item to the queue. 
    # It changes rear and size
    def
                          EnQueue(self, item):
        if self.isFull():
            print("Full")
            return
        self.rear =
                          (self.rear + 1) % (self.capacity)
        self.Q[self.rear] =
                          item
        self.size =
                          self.size + 1
        print("% s enqueued to queue"  % str(item))
 
    # Function to remove an item from queue. 
    # It changes front and size
    def
                          DeQueue(self):
        if self.isEmpty():
            print("Empty")
            return
         
        print("% s dequeued from queue" % str(self.Q[self.front]))
        self.front =
                          (self.front + 1) % (self.capacity)
        self.size =
                          self.size -1
         
    # Function to get front of queue
    def
                          que_front(self):
        if self.isEmpty():
            print("Queue is empty")
 
        print("Front item is", self.Q[self.front])
         
    # Function to get rear of queue
    def
                          que_rear(self):
        if self.isEmpty():
            print("Queue is empty")
        print("Rear item is",  self.Q[self.rear])
 
 
# Driver Code
if __name__ ==
                          '__main__':
 
    queue = Queue(30)
    queue.EnQueue(10)
                        
    queue.EnQueue(20)
                        
    queue.EnQueue(30)
                        
    queue.EnQueue(40)
                        
    queue.DeQueue()
    queue.que_front()
    queue.que_rear()

                  

              
            

C＃

              
                
                    // C# program for array implementation of queue
using System;
 
namespace GeeksForGeeks {
// A class to represent a linearqueue
class Queue {
    private
                          int[] ele;
    private
                          int front;
    private
                          int rear;
    private
                          int max;
 
    public
                          Queue(int size)
    {
        ele = new int[size];
        front = 0;
        rear = -1;
        max = size;
    }
 
    // Function to add an item to the queue.
    // It changes rear and size
    public
                          void enqueue(int item)
    {
        if (rear == max - 1) {
            Console.WriteLine("Queue Overflow");
            return;
        }
        else {
            ele[++rear] = item;
        }
    }
 
    // Function to remove an item from queue.
    // It changes front and size
    public
                          int dequeue()
    {
        if (front == rear + 1) {
            Console.WriteLine("Queue is Empty");
            return -1;
        }
        else {
            Console.WriteLine(ele[front] + " dequeued from queue");
            int p = ele[front++];
            Console.WriteLine();
            Console.WriteLine("Front item is {0}", ele[front]);
            Console.WriteLine("Rear item is {0} ", ele[rear]);
            return p;
        }
    }
 
    // Function to print queue.
    public
                          void printQueue()
    {
        if (front == rear + 1) {
            Console.WriteLine("Queue is Empty");
            return;
        }
        else {
            for (int
                          i = front; i <= rear; i++) {
                Console.WriteLine(ele[i] + " enqueued to queue");
            }
        }
    }
}
 
// Driver code
class Program {
    static
                          void Main()
    {
        Queue Q = new Queue(5);
 
        Q.enqueue(10);
        Q.enqueue(20);
        Q.enqueue(30);
        Q.enqueue(40);
        Q.printQueue();
        Q.dequeue();
    }
}
}

                  

              
            

JavaScript

              
                
                    <script>
// Queue class
class Queue
{
    // Array is used to implement a Queue
    constructor()
    {
        this.items = [];
    }
    isEmpty()
                        
    {
        // return true if the queue is empty.
        return this.items.length == 0;
    }
    enqueue(element)
    {    
        // adding element to the queue
        this.items.push(element);
        document.write(element + " enqueued to queue<br>");
    }
    dequeue()
                        
    {
        // removing element from the queue
        // returns underflow when called 
        // on empty queue
        if(this.isEmpty())
            return "Underflow<br>";
        return this.items.shift();
    }
    front()
                        
    {
        // returns the Front element of 
        // the queue without removing it.
        if(this.isEmpty())
            return "No elements in Queue<br>";
        return this.items[0];
    }
    rear()
                        
    {
        // returns the Rear element of 
        // the queue without removing it.
        if(this.isEmpty())
            return "No elements in Queue<br>";
        return this.items[this.items.length-1];
    }
}
 
// creating object for queue class
var queue = new Queue();
 
// Adding elements to the queue
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
 
// queue contains [10, 20, 30, 40]
// removes 10
document.write(queue.dequeue() + " dequeued from queue<br>");
 
// queue contains [20, 30, 40]
// Front is now 20
document.write("Front item is " + queue.front() + "<br>");
 
// printing the rear element
// Rear is 40
document.write("Rear item is " + queue.rear() + "<br>");
 
// This code is contributed by Susobhan Akhuli
</script>

                  

              
            

输出

10 已排队
20 已排队
30 已排队
40 正在排队
10 已从队列中出队
前面的项目是 20
后面的项目是 40

复杂度分析：

时间复杂度

运营	复杂
入队（插入）	复杂度(1)
双端队列（删除）	复杂度(1)
前面（取得前面）	复杂度(1)
后部（获得后部）	复杂度(1)
IsFull(检查队列是否已满)	复杂度(1)
IsEmpty(检查队列是否为空)	复杂度(1)

辅助空间： O(N)，其中 N 是用于存储元素的数组的大小。

数组实现的优点：

易于实施。
可以轻松有效地管理大量数据。
由于遵循先进先出的规则，可以轻松执行插入和删除等操作。

数组实现的缺点：

静态数据结构，固定大小。
如果队列有大量的入队和出队操作，在某个时刻（前后索引线性递增的情况下）我们可能无法在队列为空的情况下插入元素（这个问题可以避免）通过使用循环队列）。
必须事先定义队列的最大大小。