Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Circular Queue

    Uploaded by

    Sagana C. CSE

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Circular Queue

    Uploaded by

    Sagana C. CSE
    4 views6 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    4 views6 pages

    Circular Queue

    Uploaded by

    Sagana C. CSE

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 6

    Circular Queue

    Linear queue: drawback memory wastage.

    Rear pointer reaches the MaxSize of a queueafter a certain number of dequeue() operations, it will
    create an empty space at the start of a queue.
    Newly created empty space can never be re-utilized as the rear pointer reaches the end of a queue.
    To overcome this limitation concept of the circular queue was introduced

    Circular Queue in a Data Structure


    A circular queue is an extended version of a linear queue as it follows the First In First Out principle
    with the exception that it connects the last node of a queue to its first by forming a circular link.
    Hence, it is also called a Ring Buffer.
    Circular queue resolves the memory wastage problem with the help of a circular link.
    Operations
     Front - Used to get the starting element of the Circular Queue.
     Rear - Used to get the end element of the Circular Queue.
     enQueue(value) - Used to insert a new value in the Circular Queue. This operation takes place
    from the end of the Queue.
     deQueue() - Used to delete a value from the Circular Queue. This operation takes place from
    the front of the Queue.

    Applications of Circular Queue:


    Memory Management:
    CPU Scheduling:
    Traffic System:
    Array Implementation of Circular Queue
    #include <stdio.h>
    #include <Windows.h>
    #define MAX_SIZE 5
    int queue[MAX_SIZE];
    int front = -1;
    int rear = -1;
    void enqueue(int x)
    {
    if (front == -1 && rear == -1)
    {
    front = rear = 0;
    }
    else if ((rear + 1) % MAX_SIZE == front)
    {
    printf("queue is full\n");
    return;
    }
    else
    rear = (rear + 1) % MAX_SIZE;
    queue[rear] = x;
    }
    void dequeue()
    {
    if (front == -1 && rear == -1)
    {
    printf("queue is empty \n");
    return;
    }
    else if (front == rear)
    {
    front = rear = -1;
    }
    else
    front = (front + 1) % MAX_SIZE;
    }
    int Peek()
    {
    if (queue[front] == -1)
    return -1;
    return queue[front];
    }
    void Print()
    {
    int count = ((rear + MAX_SIZE - front) % MAX_SIZE)+1;
    int i;
    for (i = 0; i < count; i++)
    {
    printf("%d ", queue[(front+i)%MAX_SIZE]);
    }
    printf("\n");
    }
    int main(void)
    {
    enqueue(5);
    printf("\nFirst insertion in circular Queue\n");
    Print();
    printf("\n Second insertion in circular Queue\n");
    enqueue(7);
    Print();
    printf("\n Third insertion in circular Queue\n");
    enqueue(-3);
    Print();
    printf("\n Fourth insertion in circular Queue\n");
    enqueue(9);
    Print();
    printf("\n Circular Queue after first deletion\n");
    dequeue();
    Print();
    printf("\n Circular Queue after 2nd deletion\n");
    dequeue();
    Print();
    printf("\n Insertion in circular Queue\n");
    enqueue(14);
    system("pause");
    return 0;
    }
    Linked List Implementation of Circular Queue
    #include <stdio.h>
    #include<stdlib.h>
    struct Node {
    int data;
    struct Node* next;
    };
    struct Node* front = NULL;
    struct Node* rear = NULL;
    void enqueue(int x)
    {
    struct Node* newnode =
    (struct Node*)malloc(sizeof(struct Node));
    newnode->data=x;
    newnode->next=0;
    if(rear== NULL)
    {
    front=rear=newnode;
    rear->next=front;
    }
    else
    {
    rear->next=newnode;
    rear=newnode;
    rear->next=front;
    }
    }
    void dequeue()
    {
    struct Node* temp = front;
    if((front==NULL)&&(rear==NULL))
    {
    printf("\nQueue is empty");
    }
    else if(front==rear)
    {
    front=rear=NULL;
    free(temp);
    }
    else
    {
    front=front->next;
    rear->next=front;
    free(temp);
    }
    }
    int peek()
    {
    if((front==NULL) &&(rear==NULL))
    {
    printf("\nQueue is empty");
    }
    else
    {
    printf("\nThe front element is %d", front->data);
    }
    }
    void display()
    {
    struct Node* temp = front;
    printf("\n The elements in a Queue are : ");
    if((front==NULL) && (rear==NULL))
    {
    printf("Queue is empty");
    }
    else
    {
    while(temp->next!=front)
    {
    printf("%d,", temp->data);
    temp=temp->next;
    }
    printf("%d", temp->data);
    }
    }
    int main()
    {
    enqueue(34);
    enqueue(10);
    enqueue(23);
    display();
    dequeue();
    peek();
    }

    You might also like