Cola circular | Conjunto 1 (Introducción e implementación de array)

Requisito previo: colas

¿Qué es una cola circular?

Una cola circular es una versión especial de cola donde el último elemento de la cola está conectado al primer elemento de la cola formando un círculo.

Las operaciones se realizan según el principio FIFO (primero en entrar, primero en salir). También se le llama ‘Ring Buffer’
 

Circular Queue

 

En una cola normal, podemos insertar elementos hasta que la cola se llene. Pero una vez que la cola se llena, no podemos insertar el siguiente elemento incluso si hay un espacio delante de la cola.
 

Operations-on-Circular queue

Operaciones en cola circular:

  • Anverso: Obtener el elemento frontal de la cola.
  • Posterior: Obtener el último elemento de la cola.
  • enQueue(valor) Esta función se utiliza para insertar un elemento en la cola circular. En una cola circular, el nuevo elemento siempre se inserta en la posición Posterior. 
    1. Comprobar si la cola está llena – Comprobar ((posterior == TAMAÑO-1 && frontal == 0) || (posterior == frontal-1)).
    2. Si está lleno, la cola de visualización está llena. Si la cola no está llena, verifique si (trasero == TAMAÑO – 1 && frente! = 0) si es cierto, luego configure trasero = 0 e inserte el elemento.
  • deQueue() Esta función se usa para eliminar un elemento de la cola circular. En una cola circular, el elemento siempre se elimina desde la posición frontal. 
    1. Comprobar si la cola está vacía significa comprobar (frontal==-1).
    2. Si está vacío, la cola de visualización está vacía. Si la cola no está vacía, paso 3
    3. Compruebe si (frente==trasero) si es verdadero, luego establezca frente=trasero= -1; de lo contrario, verifique si (frente==tamaño-1), si es verdadero, luego configure frente=0 y devuelva el elemento.

Implementación:

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 == (front-1)%(size-1)))
    {
        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

Python 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
        else if (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
        else if (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")
 
        else if (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
Producción

Elements in Circular Queue are: 14 22 13 -6 
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 13 -6 
Elements in Circular Queue are: 13 -6 9 20 5 
Queue is Full

Complejidad de tiempo: la complejidad de tiempo de la operación enQueue(), deQueue() es O(1) ya que no hay bucle en ninguna de las operaciones.

Aplicaciones:

  1. Gestión de memoria: las ubicaciones de memoria no utilizadas en el caso de colas ordinarias se pueden utilizar en colas circulares.
  2. Sistema de tráfico: en el sistema de tráfico controlado por computadora, las colas circulares se utilizan para encender los semáforos uno por uno repetidamente según el tiempo establecido.
  3. Programación de CPU: los sistemas operativos a menudo mantienen una cola de procesos que están listos para ejecutarse o que están esperando que ocurra un evento en particular.

Este artículo es una contribución de Akash Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *