Requisito previo: lista circular enlazada individualmente Hemos discutido los conceptos básicos y cómo implementar una cola circular usando una array en el conjunto 1. Cola circular | Conjunto 1 (Introducción e implementación de arrays) En esta publicación, se analiza otro método de implementación de colas circulares, utilizando la lista circular enlazada individualmente.
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.
- Cree un nuevo Node dinámicamente e inserte valor en él.
- Compruebe si front==NULL, si es cierto, entonces front = rear = (Node recién creado)
- Si es falso, entonces rear=(Node recién creado) y el Node trasero siempre contiene la dirección del Node delantero.
- deQueue() Esta función se usa para eliminar un elemento de la cola circular. En una cola, el elemento siempre se elimina desde la posición frontal.
- Verificar si la cola está vacía o no significa frente == NULL.
- Si está vacío, la cola de visualización está vacía. Si la cola no está vacía, paso 3
- Verifique si (frente == trasero) si es verdadero, luego configure frente = trasero = NULL; de lo contrario, mueva el frente hacia adelante en la cola, actualice la dirección del frente en el Node trasero y devuelva el elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for insertion and
// deletion in Circular Queue
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node
struct Node {
int data;
struct Node* link;
};
struct Queue {
struct Node *front, *rear;
};
// Function to create Circular queue
void enQueue(Queue* q, int value)
{
struct Node* temp = new Node;
temp->data = value;
if (q->front == NULL)
q->front = temp;
else
q->rear->link = temp;
q->rear = temp;
q->rear->link = q->front;
}
// Function to delete element from Circular Queue
int deQueue(Queue* q)
{
if (q->front == NULL) {
printf("Queue is empty");
return INT_MIN;
}
// If this is the last node to be deleted
int value; // Value to be dequeued
if (q->front == q->rear) {
value = q->front->data;
free(q->front);
q->front = NULL;
q->rear = NULL;
}
else // There are more than one nodes
{
struct Node* temp = q->front;
value = temp->data;
q->front = q->front->link;
q->rear->link = q->front;
free(temp);
}
return value;
}
// Function displaying the elements of Circular Queue
void displayQueue(struct Queue* q)
{
struct Node* temp = q->front;
printf("\nElements in Circular Queue are: ");
while (temp->link != q->front) {
printf("%d ", temp->data);
temp = temp->link;
}
printf("%d", temp->data);
}
/* Driver of the program */
int main()
{
// Create a queue and initialize front and rear
Queue* q = new Queue;
q->front = q->rear = NULL;
// Inserting elements in Circular Queue
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
// Display elements present in Circular Queue
displayQueue(q);
// Deleting elements from Circular Queue
printf("\nDeleted value = %d", deQueue(q));
printf("\nDeleted value = %d", deQueue(q));
// Remaining elements in Circular Queue
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
return 0;
}
Java
// Java program for insertion and
// deletion in Circular Queue
import java.util.*;
class Solution {
// Structure of a Node
static class Node {
int data;
Node link;
}
static class Queue {
Node front, rear;
}
// Function to create Circular queue
static void enQueue(Queue q, int value)
{
Node temp = new Node();
temp.data = value;
if (q.front == null)
q.front = temp;
else
q.rear.link = temp;
q.rear = temp;
q.rear.link = q.front;
}
// Function to delete element from Circular Queue
static int deQueue(Queue q)
{
if (q.front == null) {
System.out.printf("Queue is empty");
return Integer.MIN_VALUE;
}
// If this is the last node to be deleted
int value; // Value to be dequeued
if (q.front == q.rear) {
value = q.front.data;
q.front = null;
q.rear = null;
}
else // There are more than one nodes
{
Node temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
// Function displaying the elements of Circular Queue
static void displayQueue(Queue q)
{
Node temp = q.front;
System.out.printf("\nElements in Circular Queue are: ");
while (temp.link != q.front) {
System.out.printf("%d ", temp.data);
temp = temp.link;
}
System.out.printf("%d", temp.data);
}
/* Driver of the program */
public static void main(String args[])
{
// Create a queue and initialize front and rear
Queue q = new Queue();
q.front = q.rear = null;
// Inserting elements in Circular Queue
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
// Display elements present in Circular Queue
displayQueue(q);
// Deleting elements from Circular Queue
System.out.printf("\nDeleted value = %d", deQueue(q));
System.out.printf("\nDeleted value = %d", deQueue(q));
// Remaining elements in Circular Queue
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program for insertion and
# deletion in Circular Queue
# Structure of a Node
class Node:
def __init__(self):
self.data = None
self.link = None
class Queue:
def __init__(self):
front = None
rear = None
# Function to create Circular queue
def enQueue(q, value):
temp = Node()
temp.data = value
if (q.front == None):
q.front = temp
else:
q.rear.link = temp
q.rear = temp
q.rear.link = q.front
# Function to delete element from
# Circular Queue
def deQueue(q):
if (q.front == None):
print("Queue is empty")
return -999999999999
# If this is the last node to be deleted
value = None # Value to be dequeued
if (q.front == q.rear):
value = q.front.data
q.front = None
q.rear = None
else: # There are more than one nodes
temp = q.front
value = temp.data
q.front = q.front.link
q.rear.link = q.front
return value
# Function displaying the elements
# of Circular Queue
def displayQueue(q):
temp = q.front
print("Elements in Circular Queue are: ",
end = " ")
while (temp.link != q.front):
print(temp.data, end = " ")
temp = temp.link
print(temp.data)
# Driver Code
if __name__ == '__main__':
# Create a queue and initialize
# front and rear
q = Queue()
q.front = q.rear = None
# Inserting elements in Circular Queue
enQueue(q, 14)
enQueue(q, 22)
enQueue(q, 6)
# Display elements present in
# Circular Queue
displayQueue(q)
# Deleting elements from Circular Queue
print("Deleted value = ", deQueue(q))
print("Deleted value = ", deQueue(q))
# Remaining elements in Circular Queue
displayQueue(q)
enQueue(q, 9)
enQueue(q, 20)
displayQueue(q)
# This code is contributed by PranchalK
C#
// C# program for insertion and
// deletion in Circular Queue
using System;
using System.Collections.Generic;
public class GFG {
// Structure of a Node
public class Node {
public int data;
public Node link;
}
public class LinkedList {
public Node front, rear;
}
// Function to create Circular queue
public static void enQueue(LinkedList q,
int value)
{
Node temp = new Node();
temp.data = value;
if (q.front == null) {
q.front = temp;
}
else {
q.rear.link = temp;
}
q.rear = temp;
q.rear.link = q.front;
}
// Function to delete element from
// Circular Queue
public static int deQueue(LinkedList q)
{
if (q.front == null) {
Console.Write("Queue is empty");
return int.MinValue;
}
// If this is the last node to be deleted
int value; // Value to be dequeued
if (q.front == q.rear) {
value = q.front.data;
q.front = null;
q.rear = null;
}
else // There are more than one nodes
{
Node temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
// Function displaying the elements
// of Circular Queue
public static void displayQueue(LinkedList q)
{
Node temp = q.front;
Console.Write("\nElements in Circular Queue are: ");
while (temp.link != q.front) {
Console.Write("{0:D} ", temp.data);
temp = temp.link;
}
Console.Write("{0:D}", temp.data);
}
// Driver Code
public static void Main(string[] args)
{
// Create a queue and initialize
// front and rear
LinkedList q = new LinkedList();
q.front = q.rear = null;
// Inserting elements in Circular Queue
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
// Display elements present in
// Circular Queue
displayQueue(q);
// Deleting elements from Circular Queue
Console.Write("\nDeleted value = {0:D}",
deQueue(q));
Console.Write("\nDeleted value = {0:D}",
deQueue(q));
// Remaining elements in Circular Queue
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
}
}
// This code is contributed by Shrikant13
Producción
Elements in Circular Queue are: 14 22 6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 6 Elements in Circular Queue are: 6 9 20
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.
Nota: En caso de implementación de lista enlazada, una cola se puede implementar fácilmente sin ser circular. Sin embargo, en el caso de la implementación de arrays, necesitamos una cola circular para ahorrar espacio.
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