Animierte Darstellung einer Ringwarteschlange

什么是循环队列？

循环队列是普通队列的扩展版本，其中队列的最后一个元素连接到队列的第一个元素形成一个循环。

操作基于 FIFO（先进先出）原则执行。它也被称为 “环形缓冲区” 。

循环队列

在普通队列中，我们可以插入元素直到队列满。但是一旦队列满了，即使队列前面有空间，我们也无法插入下一个元素。

循环队列的操作：

Front： 从队列中获取最前面的项目。
后部： 从队列中获取最后一项。
enQueue(value) 该函数用于向循环队列中插入一个元素。在循环队列中，新元素总是插入到最后位置。
- 检查队列是否已满——【即循环地后端正好在前端之前】。
- 如果已满则显示队列已满。
  - 如果队列未满，则在队列末尾插入一个元素。
deQueue() 该函数用于从循环队列中删除一个元素。在循环队列中，总是从最前面的位置删除元素。
- 检查队列是否为空。
- 如果为空则显示队列为空。
  - 如果队列不为空，则获取最后一个元素并将其从队列中删除。

循环队列操作说明：

按照下图可以更好地理解入队和出队操作。

循环队列操作的工作原理

如何实现循环队列？

循环队列可以使用两种数据结构来实现：

大批
链表

这里我们展示了使用数组数据结构的循环队列的实现。

使用数组实现循环队列：

初始化一个大小为n 的数组队列，其中 n 是队列可以容纳的最大元素数。
将front和rear两个变量初始化为-1。
入队： 要将元素 x 入队，请执行以下操作：
- 后面加 1。
  - 如果后部等于n，则将后部设置为0。
- 如果 front 为 -1，则将 front 设置为 0。
- 将队列[rear]设置为x。
出队： 要将元素从队列中出队，请执行以下操作：
- 通过检查front 是否为 -1 来检查队列是否为空。
  - 如果是，则返回错误消息，指示队列为空。
- 将 x 设置为队列[front]。
- 如果 front 等于 back ，则将 front 和 back 设置为 -1。
- 否则，将 front 加 1，如果 front 等于 n，则将 front 设置为 0。
- 返回x。

下面是上述想法的实现：

C++
Java
C＃
蟒蛇3
JavaScript

C++

              
                
                    // C or C++ program for insertion and
// deletion in Circular Queue
#include<bits/stdc++.h>
using namespace std;
 
class Queue
{
    // Initialize front and rear
    int
                          rear, front;
 
    // Circular Queue
    int
                          size;
    int
                          *arr;
public:
    Queue(int s)
    {
       front = rear = -1;
       size = s;
       arr = new int[s];
    }
 
    void enQueue(int value);
    int
                          deQueue();
    void displayQueue();
};
 
 
/* Function to create Circular queue */
void Queue::enQueue(int value)
{
    if
                          ((front == 0 && rear == size-1) ||
            ((rear+1) % size == front))
    {
        printf("\nQueue is Full");
        return;
    }
 
    else if (front == -1) /* Insert First Element */
                        
    {
        front = rear = 0;
        arr[rear] = value;
    }
 
    else if (rear == size-1 && front != 0)
    {
        rear = 0;
        arr[rear] = value;
    }
 
    else
    {
        rear++;
        arr[rear] = value;
    }
}
 
// Function to delete element from Circular Queue
int Queue::deQueue()
{
    if
                          (front == -1)
    {
        printf("\nQueue is Empty");
        return INT_MIN;
    }
 
    int
                          data = arr[front];
    arr[front] = -1;
    if
                          (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else if (front == size-1)
        front = 0;
    else
        front++;
 
    return data;
}
 
// Function displaying the elements
// of Circular Queue
void Queue::displayQueue()
{
    if
                          (front == -1)
    {
        printf("\nQueue is Empty");
        return;
    }
    printf("\nElements in Circular Queue are: ");
                        
    if
                          (rear >= front)
    {
        for (int i = front; i <= rear; i++)
                        
            printf("%d ",arr[i]);
    }
    else
    {
        for (int i = front; i < size; i++)
            printf("%d ", arr[i]);
 
        for (int i = 0; i <= rear; i++)
            printf("%d ", arr[i]);
    }
}
 
/* Driver of the program */
int main()
{
    Queue q(5);
 
    // Inserting elements in Circular Queue
    q.enQueue(14);
    q.enQueue(22);
    q.enQueue(13);
    q.enQueue(-6);
 
    // Display elements present in Circular Queue
    q.displayQueue();
 
    // Deleting elements from Circular Queue
    printf("\nDeleted value = %d", q.deQueue());
    printf("\nDeleted value = %d", q.deQueue());
 
    q.displayQueue();
 
    q.enQueue(9);
    q.enQueue(20);
    q.enQueue(5);
 
    q.displayQueue();
 
    q.enQueue(20);
    return 0;
}

                  

              
            

Java

              
                
                    // Java program for insertion and
// deletion in Circular Queue
import java.util.ArrayList;
 
class CircularQueue{
 
// Declaring the class variables.
private int size, front, rear;
 
// Declaring array list of integer type.
private ArrayList<Integer> queue = new ArrayList<Integer>();
 
// Constructor
CircularQueue(int size)
{
    this.size = size;
    this.front = this.rear = -1;
}
 
// Method to insert a new element in the queue.
public void enQueue(int data)
{
     
    // Condition if queue is full.
    if((front == 0 && rear == size - 1) ||
      (rear == (front - 1) % (size - 1)))
                        
    {
        System.out.print("Queue is Full");
    }
 
    // condition for empty queue.
    else
                          if(front == -1)
    {
        front = 0;
        rear = 0;
        queue.add(rear, data);
    }
 
    else
                          if(rear == size - 1 && front != 0)
    {
        rear = 0;
        queue.set(rear, data);
    }
 
    else
                        
    {
        rear = (rear + 1);
     
        // Adding a new element if 
        if(front <= rear)
        {
            queue.add(rear, data);
        }
     
        // Else updating old value
        else
        {
            queue.set(rear, data);
        }
    }
}
 
// Function to dequeue an element
// form th queue.
public int deQueue()
{
    int
                          temp;
 
    // Condition for empty queue.
    if(front == -1)
                        
    {
        System.out.print("Queue is Empty");
         
        // Return -1 in case of empty queue
        return -1; 
    }
 
    temp = queue.get(front);
 
    // Condition for only one element
    if(front == rear)
    {
        front = -1;
        rear = -1;
    }
 
    else
                          if(front == size - 1)
    {
        front = 0;
    }
    else
                        
    {
        front = front + 1;
    }
     
    // Returns the dequeued element
    return
                          temp;
}
 
// Method to display the elements of queue
public void displayQueue()
{
     
    // Condition for empty queue.
    if(front == -1)
                        
    {
        System.out.print("Queue is Empty");
        return;
    }
 
    // If rear has not crossed the max size
    // or queue rear is still greater then
    // front.
    System.out.print("Elements in the " +
                     "circular queue are: ");
 
    if(rear >= front)
    {
     
        // Loop to print elements from
        // front to rear.
        for(int i = front; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
 
    // If rear crossed the max index and
    // indexing has started in loop
    else
                        
    {
         
        // Loop for printing elements from
        // front to max size or last index
        for(int i = front; i < size; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
 
        // Loop for printing elements from
        // 0th index till rear position
        for(int i = 0; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Initialising new object of
    // CircularQueue class.
    CircularQueue q = new CircularQueue(5);
                        
     
    q.enQueue(14);
                        
    q.enQueue(22);
                        
    q.enQueue(13);
                        
    q.enQueue(-6);
                        
     
    q.displayQueue();
 
    int
                          x = q.deQueue();
 
    // Checking for empty queue.
    if(x != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(x);
    }
 
    x = q.deQueue();
 
    // Checking for empty queue.
    if(x != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(x);
    }
 
    q.displayQueue();
     
    q.enQueue(9);
                        
    q.enQueue(20);
                        
    q.enQueue(5);
                        
     
    q.displayQueue();
     
    q.enQueue(20);
                        
}
}
 
// This code is contributed by Amit Mangal.

                  

              
            

C＃

              
                
                    // C# program for insertion and
// deletion in Circular Queue
using System;
using System.Collections.Generic;
 
public class CircularQueue{
     
    // Declaring the class variables.
    private
                          int size, front, rear;
      
    // Declaring array list of integer type.
    private
                          List<int> queue = new List<int>();
     
    // Constructor
    CircularQueue(int size)
    {
        this.size = size;
        this.front = this.rear = -1;
    }
     
    // Method to insert a new element in the queue.
    public
                          void enQueue(int data)
    {
          
                        
        // Condition if queue is full.
        if((front == 0 && rear == size - 1) ||
          (rear == (front - 1) % (size - 1)))
        {
            Console.Write("Queue is Full");
        }
      
        // condition for empty queue.
        else if(front == -1)
        {
            front = 0;
            rear = 0;
            queue.Add(data);
        }
      
        else if(rear == size - 1 && front != 0)
        {
            rear = 0;
            queue[rear]=data;
        }
      
        else
        {
            rear = (rear + 1);
          
                        
            // Adding a new element if
            if(front <= rear)
            {
                queue.Add(data);
            }
          
                        
            // Else updating old value
            else
            {
                queue[rear]=data;
            }
        }
    }
     
    // Function to dequeue an element
    // form th queue.
    public
                          int deQueue()
    {
        int temp;
      
        // Condition for empty queue.
        if(front == -1)
        {
            Console.Write("Queue is Empty");
              
                        
            // Return -1 in case of empty queue
            return -1;
        }
      
        temp = queue[front];
      
        // Condition for only one element
        if(front == rear)
        {
            front = -1;
            rear = -1;
        }
      
        else if(front == size - 1)
        {
            front = 0;
        }
        else
        {
            front = front + 1;
        }
          
                        
        // Returns the dequeued element
        return temp;
    }
      
    // Method to display the elements of queue
    public
                          void displayQueue()
    {
          
                        
        // Condition for empty queue.
        if(front == -1)
        {
            Console.Write("Queue is Empty");
            return;
        }
      
        // If rear has not crossed the max size
        // or queue rear is still greater then
        // front.
        Console.Write("Elements in the circular queue are: ");
                        
      
        if(rear >= front)
        {
          
                        
            // Loop to print elements from
            // front to rear.
            for(int i = front; i <= rear; i++)
            {
                Console.Write(queue[i]);
                Console.Write(" ");
            }
            Console.Write("\n");
        }
      
        // If rear crossed the max index and
        // indexing has started in loop
        else
        {
              
                        
            // Loop for printing elements from
            // front to max size or last index
            for(int i = front; i < size; i++)
            {
                Console.Write(queue[i]);
                Console.Write(" ");
            }
      
            // Loop for printing elements from
            // 0th index till rear position
            for(int i = 0; i <= rear; i++)
            {
                Console.Write(queue[i]);
                Console.Write(" ");
            }
            Console.Write("\n");
        }
    }
     
    // Driver code
    static
                          public void Main (){
        // Initialising new object of
        // CircularQueue class.
        CircularQueue q = new CircularQueue(5);
          
                        
        q.enQueue(14);
        q.enQueue(22);
        q.enQueue(13);
        q.enQueue(-6);
          
                        
        q.displayQueue();
      
        int x = q.deQueue();
      
        // Checking for empty queue.
        if(x != -1)
        {
            Console.Write("Deleted value = ");
            Console.Write(x+"\n");
        }
      
        x = q.deQueue();
      
        // Checking for empty queue.
        if(x != -1)
        {
            Console.Write("Deleted value = ");
            Console.Write(x+"\n");
        }
      
        q.displayQueue();
          
                        
        q.enQueue(9);
        q.enQueue(20);
        q.enQueue(5);
          
                        
        q.displayQueue();
          
                        
        q.enQueue(20);
    }
}
 
// This code is contributed by shruti456rawal

                  

              
            

蟒蛇3

              
                
                    class CircularQueue():
 
    # constructor
    def
                          __init__(self, size): # initializing the class
        self.size =
                          size
         
        # initializing queue with none
        self.queue =
                          [None for
                          i in range(size)] 
        self.front =
                          self.rear = -1
 
    def
                          enqueue(self, data):
         
        # condition if queue is full
        if ((self.rear + 1) % self.size ==
                          self.front): 
            print(" Queue is Full\n")
             
                        
        # condition for empty queue
        elif (self.front == -1): 
            self.front =
                          0
            self.rear =
                          0
            self.queue[self.rear] =
                          data
        else:
             
                        
            # next position of rear
            self.rear =
                          (self.rear + 1) % self.size 
            self.queue[self.rear] =
                          data
             
                        
    def
                          dequeue(self):
        if (self.front ==
                          -1): # condition for empty queue
            print ("Queue is Empty\n")
             
                        
        # condition for only one element
        elif (self.front == self.rear): 
            temp=self.queue[self.front]
            self.front =
                          -1
            self.rear =
                          -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front =
                          (self.front + 1) % self.size
            return temp
 
    def
                          display(self):
     
        # condition for empty queue
        if(self.front ==
                          -1): 
            print ("Queue is Empty")
 
        elif (self.rear >= self.front):
                        
            print("Elements in the circular queue are:", 
                        
                                              end = " ")
            for i in
                          range(self.front, self.rear +
                          1):
                print(self.queue[i], end = " ")
            print ()
 
        else:
            print ("Elements in Circular Queue are:", 
                                           end = " ")
            for i in
                          range(self.front, self.size):
                print(self.queue[i], end = " ")
            for i in
                          range(0, self.rear + 1):
                print(self.queue[i], end = " ")
            print ()
 
        if ((self.rear + 1) % self.size ==
                          self.front):
            print("Queue is Full")
 
# Driver Code
ob = CircularQueue(5)
ob.enqueue(14)
ob.enqueue(22)
ob.enqueue(13)
ob.enqueue(-6)
ob.display()
print ("Deleted value = ", ob.dequeue())
print ("Deleted value = ", ob.dequeue())
ob.display()
ob.enqueue(9)
ob.enqueue(20)
ob.enqueue(5)
ob.display()
 
# This code is contributed by AshwinGoel 

                  

              
            

JavaScript

              
                
                    // JS program for insertion and
// deletion in Circular Queue
class Queue {
    constructor() {
        this.rear = -1;
        this.front = -1;
        this.size = 5;
        this.arr = new Array();
    }
    enQueue(value) {
        if ((this.front == 0 && this.rear == this.size - 1) ||
            (this.rear == (this.front - 1) % (this.size - 1))) {
            console.log("Queue is Full");
            return;
        }
        else if (this.front == -1) /* Insert First Element */
                          {
            this.front = this.rear = 0;
            this.arr[this.rear] = value;
        }
        else if (this.rear == this.size - 1 && this.front != 0) {
            this.rear = 0;
            this.arr[this.rear] = value;
        }
        else {
            this.rear++;
            this.arr[this.rear] = value;
        }
    }
    deQueue() {
        if (this.front == -1) {
            console.log("Queue is Empty");
            return INT_MIN;
        }
        let data = this.arr[this.front];
        this.arr[this.front] = -1;
        if (this.front == this.rear) {
            this.front = -1;
            this.rear = -1;
        }
        else if (this.front == this.size - 1)
            this.front = 0;
        else
            this.front++;
        // console.log("Data: ",data);
        return data;
    }
    displayQueue() {
        if (this.front == -1) {
            console.log("Queue is Empty");
            return;
        }
        console.log("\nElements in Circular Queue are: ");
                        
        if (this.rear >= this.front) {
            for (let i = this.front; i <= this.rear; i++)
                console.log(this.arr[i]);
        }
        else {
            for (let i = this.front; i < this.size; i++)
                console.log(this.arr[i]);
            for (let i = 0; i <= this.rear; i++)
                console.log(this.arr[i]);
        }
    }
}
 
/* Driver of the program */
let q = new Queue;
 
// Inserting elements in Circular Queue
q.enQueue(14);
q.enQueue(22);
q.enQueue(13);
q.enQueue(-6);
 
// Display elements present in Circular Queue
q.displayQueue();
 
// Deleting elements from Circular Queue
console.log("Deleted value = ", q.deQueue());
console.log("Deleted value = ", q.deQueue());
q.displayQueue();
q.enQueue(9);
q.enQueue(20);
q.enQueue(5);
q.displayQueue();
q.enQueue(20);
 
// This code is contributed by ishankhandelwals.

                  

              
            

输出

循环队列中的元素为：14 22 13 -6
删除的值 = 14
删除值 = 22
循环队列中的元素为：13 -6
循环队列中的元素为： 13 -6 9 20 5
队列已满

循环队列操作的复杂度分析：

时间复杂度：
- 入队：O(1)，因为单个入队不涉及循环。
- 出队：O(1)，因为一次出队操作不涉及循环。
辅助空间： O(N)，因为队列大小为 N。

循环队列的应用：

内存管理： 普通队列中未使用的内存位置可以在循环队列中利用。
交通系统： 在计算机控制的交通系统中，采用循环队列，按照设定的时间一一重复地打开交通灯。
CPU 调度： 操作系统通常维护一个准备执行或等待特定事件发生的进程队列。

如果您喜欢图码并愿意做出贡献，您还可以使用 write.geeksforgeeks.org 撰写文章或将您的文章邮寄至 review-team@geeksforgeeks.org。查看您的文章出现在图码主页上并帮助其他极客。