Рубрики

Круговая Очередь | Набор 2 (реализация в виде круглого связного списка)

Обязательное условиекруговой односвязный список

Мы обсудили основы и как реализовать круговую очередь, используя массив в наборе 1.
Круговая Очередь | Набор 1 (Введение и реализация массива)

В этом посте обсуждается другой метод реализации циклической очереди, использующий круговой односвязный список.

Операции с круговой очередью:

  • Front: получить передний элемент из очереди.
  • Сзади: получить последний элемент из очереди.
  • enQueue (значение) Эта функция используется для вставки элемента в круговую очередь. В круговой очереди новый элемент всегда вставляется в заднем положении.
      шаги:

    1. Динамически создайте новый узел и вставьте в него значение.
    2. Проверьте, что передний == NULL, если это правда, то передний = задний = (вновь созданный узел)
    3. Если оно ложно, то задний = (вновь созданный узел) и задний узел всегда содержат адрес переднего узла.
  • deQueue () Эта функция используется для удаления элемента из циклической очереди. В очереди элемент всегда удаляется из передней позиции.
      шаги:

    1. Проверить, пуста очередь или нет, означает front == NULL.
    2. Если он пуст, то дисплей Очередь пуст. Если очередь не пуста, тогда шаг 3
    3. Проверьте, если (передний == задний), если это правда, тогда установите передний = задний = NULL, иначе передвиньте фронт вперед в очереди, обновите адрес фронта в заднем узле и верните элемент.
  • Ниже приведена реализация вышеуказанного подхода:

    C ++

    // C ++ программа для вставки и
    // удаление в круговой очереди
    #include <bits/stdc++.h>

    using namespace std;

      
    // Структура узла

    struct Node

    {

        int data;

        struct Node* link;

    };

      

    struct Queue

    {

        struct Node *front, *rear;

    };

      
    // Функция для создания круговой очереди

    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;

    }

      
    // Функция для удаления элемента из круговой очереди

    int deQueue(Queue *q)

    {

        if (q->front == NULL)

        {

            printf ("Queue is empty");

            return INT_MIN;

        }

      

        // Если это последний узел, который будет удален

        int value; // Значение, которое будет удалено

        if (q->front == q->rear)

        {

            value = q->front->data;

            free(q->front);

            q->front = NULL;

            q->rear = NULL;

        }

        else  // Есть более одного узла

        {

            struct Node *temp = q->front;

            value = temp->data;

            q->front = q->front->link;

            q->rear->link= q->front;

            free(temp);

        }

      

        return value ;

    }

      
    // Функция отображения элементов круговой очереди

    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);

    }

      
    / * Драйвер программы * /

    int main()

    {

        // Создать очередь и инициализировать фронт и тыл

        Queue *q = new Queue;

        q->front = q->rear = NULL;

      

        // Вставка элементов в круговую очередь

        enQueue(q, 14);

        enQueue(q, 22);

        enQueue(q, 6);

      

        // Показать элементы, присутствующие в круговой очереди

        displayQueue(q);

      

        // Удаление элементов из круговой очереди

        printf("\nDeleted value = %d", deQueue(q));

        printf("\nDeleted value = %d", deQueue(q));

      

        // Остальные элементы в круговой очереди

        displayQueue(q);

      

        enQueue(q, 9);

        enQueue(q, 20);

        displayQueue(q);

      

        return 0;

    }

    Джава

    // Java-программа для вставки и
    // удаление в круговой очереди

    import java.util.* ;

      

    class Solution

    {

        
    // Структура узла

    static class Node 

        int data; 

         Node  link; 

    }

        

    static class Queue 

         Node  front,  rear; 

    }

        
    // Функция для создания круговой очереди

    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; 

        
    // Функция для удаления элемента из круговой очереди

    static  int deQueue(Queue  q) 

        if (q .front ==  null

        

            System.out.printf ("Queue is empty"); 

            return Integer.MIN_VALUE; 

        

        

        // Если это последний узел, который будет удален

        int value; // Значение, которое будет удалено

        if (q .front == q .rear) 

        

            value = q .front .data; 

            q .front =  null

            q .rear =  null

        

        else  // Есть более одного узла

        

             Node  temp = q .front; 

            value = temp .data; 

            q .front = q .front .link; 

            q .rear .link= q .front; 

        

        

        return value ; 

        
    // Функция отображения элементов круговой очереди

    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); 

        
    / * Драйвер программы * /

    public static void main(String args[])

        // Создать очередь и инициализировать фронт и тыл

        Queue  q = new Queue(); 

        q .front = q .rear =  null

        

        // Вставка элементов в круговую очередь

        enQueue(q, 14); 

        enQueue(q, 22); 

        enQueue(q, 6); 

        

        // Показать элементы, присутствующие в круговой очереди

        displayQueue(q); 

        

        // Удаление элементов из круговой очереди

        System.out.printf("\nDeleted value = %d", deQueue(q)); 

        System.out.printf("\nDeleted value = %d", deQueue(q)); 

        

        // Остальные элементы в круговой очереди

        displayQueue(q); 

        

        enQueue(q, 9); 

        enQueue(q, 20); 

        displayQueue(q); 

        

    }

      
    // Этот код добавлен
    // Арнаб Кунду

    python3

    # Python3 программа для вставки и
    # удаление в круговой очереди

      
    # Структура узла

    class Node:

        def __init__(self):

            self.data = None

            self.link = None

      

    class Queue:

        def __init__(self):

            front = None

            rear = None

      
    # Функция для создания круговой очереди

    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

      
    # Функция для удаления элемента из
    # Круговая очередь

    def deQueue(q):

        if (q.front == None):

            print("Queue is empty"

            return -999999999999

      

        # Если это последний узел, который будет удален

        value = None # Значение, подлежащее изъятию

        if (q.front == q.rear):

            value = q.front.data

            q.front = None

            q.rear = None

        else: # Есть более одного узла

            temp = q.front 

            value = temp.data 

            q.front = q.front.link 

            q.rear.link= q.front

      

        return value 

      
    # Функция отображения элементов
    № Круговой очереди

    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)

      
    Код водителя

    if __name__ == '__main__':

      

        # Создать очередь и инициализировать

        # передний и задний

        q = Queue() 

        q.front = q.rear = None

      

        # Вставка элементов в круговую очередь

        enQueue(q, 14

        enQueue(q, 22

        enQueue(q, 6

      

        # Показать элементы, присутствующие в

        # Круговая очередь

        displayQueue(q) 

      

        # Удаление элементов из круговой очереди

        print("Deleted value = ", deQueue(q)) 

        print("Deleted value = ", deQueue(q)) 

      

        # Остальные элементы в круговой очереди

        displayQueue(q) 

      

        enQueue(q, 9

        enQueue(q, 20

        displayQueue(q)

      
    # Этот код предоставлен PranchalK

    C #

    // C # программа для вставки и
    // удаление в круговой очереди

    using System;

    using System.Collections.Generic;

      

    public class GFG

    {

      
    // Структура узла

    public class Node

    {

        public int data;

        public Node link;

    }

      

    public class LinkedList

    {

        public Node front, rear;

    }

      
    // Функция для создания круговой очереди

    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;

    }

      
    // Функция для удаления элемента из
    // Круговая очередь

    public static int deQueue(LinkedList q)

    {

        if (q.front == null)

        {

            Console.Write("Queue is empty");

            return int.MinValue;

        }

      

        // Если это последний узел, который будет удален

        int value; // Значение, которое будет удалено

        if (q.front == q.rear)

        {

            value = q.front.data;

            q.front = null;

            q.rear = null;

        }

        else // Есть более одного узла

        {

            Node temp = q.front;

            value = temp.data;

            q.front = q.front.link;

            q.rear.link = q.front;

        }

      

        return value;

    }

      
    // Функция отображения элементов
    // Круговой очереди

    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);

    }

      
    // Код драйвера

    public static void Main(string[] args)

    {

        // Создать очередь и инициализировать

        // передний и задний

        LinkedList q = new LinkedList();

        q.front = q.rear = null;

      

        // Вставка элементов в круговую очередь

        enQueue(q, 14);

        enQueue(q, 22);

        enQueue(q, 6);

      

        // Показать элементы, присутствующие в

        // Круговая очередь

        displayQueue(q);

      

        // Удаление элементов из круговой очереди

        Console.Write("\nDeleted value = {0:D}",

                                    deQueue(q));

        Console.Write("\nDeleted value = {0:D}"

                                    deQueue(q));

      

        // Остальные элементы в круговой очереди

        displayQueue(q);

      

        enQueue(q, 9);

        enQueue(q, 20);

        displayQueue(q);

    }
    }

      
    // Этот код предоставлен Shrikant13


    Выход:

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

Сложность времени: временная сложность операции enQueue (), deQueue () равна O (1), поскольку в любой из операций нет цикла.

Примечание. В случае реализации связанного списка очередь может быть легко реализована, не будучи циклической. Однако в случае реализации массива нам нужна круговая очередь для экономии места.

Эта статья предоставлена Акашем Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Круговая Очередь | Набор 2 (реализация в виде круглого связного списка)

0.00 (0%) 0 votes