{"id":387,"date":"2023-06-28T11:36:59","date_gmt":"2023-06-28T11:36:59","guid":{"rendered":"http:\/\/localhost\/embeddedwala\/?p=387"},"modified":"2023-07-27T04:13:10","modified_gmt":"2023-07-27T04:13:10","slug":"circular-queue-basics","status":"publish","type":"post","link":"https:\/\/embeddedwala.com\/beta\/blogs\/digital-communication\/circular-queue-basics\/","title":{"rendered":"Circular Queue Basics"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t

What is Circular Queue?<\/span><\/h2>

The\u00a0Circular Queue<\/strong>\u00a0is the Extention of a queue that is a linear user-defined data structure. The circular queue is often used in situations where elements can be added to or removed from the queue at any point in a program, rather than following a predetermined enqueue or dequeue order.<\/span><\/p>

A circular queue is often used in embedded systems to manage memory. It is also utilized in the process management of real-time operating systems\u00a0(RTOS)<\/strong>\u00a0for scheduling.<\/span><\/p>

A circular queue typically includes four main functions:<\/strong><\/span><\/p>

  1. Checking if the queue is empty<\/span><\/li>
  2. Checking if the queue is full<\/span><\/li>
  3. Adding an element to the queue (enqueue)<\/span><\/li>
  4. Removing an element from the queue (dequeue)<\/span><\/li><\/ol>

    \"\"<\/p>

    \u00a0<\/p>

    This code is an implementation of a circular queue in C<\/strong>. The circular queue is a data structure that behaves like a queue but has a fixed size and wraps around when the end of the queue is reached.<\/p>

    The circular queue is defined using a struct called\u00a0CircularQueue<\/code><\/strong>, which has an array\u00a0data<\/code>\u00a0to store the elements, and two pointers\u00a0front<\/code>\u00a0and\u00a0end<\/code>\u00a0to keep track of the front and end of the queue. The\u00a0init_circular_queue<\/code>\u00a0<\/strong>function initializes the queue by setting the front and end pointers to -1 and clearing the data array.<\/p>

    The\u00a0is_queue_full<\/code>\u00a0<\/strong>function checks if the queue is full by checking if the front pointer is at the beginning of the array and the end pointer is at the end of the array, or if the end pointer is just before the front pointer (which indicates that the queue has overlapped). The\u00a0is_queue_empty<\/code>\u00a0<\/strong>function checks if the queue is empty by checking if the front pointer is -1.<\/p>

    The\u00a0add_element_in_queue<\/code>\u00a0<\/strong>function adds an element to the queue by first checking if the queue is full. If the queue is not full, it updates the end pointer to the next index (using modulo arithmetic to wrap around to the beginning of the array if necessary) and stores the element at that index. The\u00a0remove_element_from_queue<\/code>\u00a0<\/strong>function removes an element from the queue by first checking if the queue is empty. If the queue is not empty, it updates the front pointer to the next index (using modulo arithmetic to wrap around to the beginning of the array if necessary).<\/p>

    The\u00a0print_full_queue<\/code>\u00a0<\/strong>function is a helper function that prints the entire contents of the queue.<\/p>

    Finally, the\u00a0main<\/code>\u00a0<\/strong>function initializes the circular queue using\u00a0init_circular_queue<\/code>\u00a0<\/strong>and then adds elements to it using\u00a0add_element_in_queue<\/code>\u00a0<\/strong>and prints the full queue using\u00a0print_full_queue<\/code><\/strong>. It adds 14 elements to the queue (the size of the queue is 5), which causes the circular queue to wrap around and overwrite the oldest elements in the queue.<\/p>

    #include <stdio.h>\n#include <stdint.h>
    \n\/* \n * Size of Queue in Bytes\n *\/\n#define SIZE_OF_QUEUE_IN_BYTES       5\n\n\/*\n * Structure holds the circular queue\n *\/\ntypedef struct CircularQueue {\n    char data[SIZE_OF_QUEUE_IN_BYTES];\n    int front;\n    int end;\n} CircularQueue;\n\n\/*\n * Global variable holding instance of the circular queue\n *\/\nCircularQueue Circular_Queue;\n\nvoid init_circular_queue(CircularQueue * queue) {\n    queue->front = -1;\n    queue->end   = -1;\n    for(int idx = 0; idx < SIZE_OF_QUEUE_IN_BYTES; idx++) {\n        queue->data[idx] = 0;\n    }    \n}\n
    \/*
     * There are two ways to find out if the circular queue is full.
     * 1) If linearly the queue is full with no overlap
     * 2) If the circular queue has overlapped. 
     *\/\nbool is_queue_full(CircularQueue queue) {\n    if(((queue.front == 0) && (queue.end == SIZE_OF_QUEUE_IN_BYTES)) ||\n        (queue.front == queue.end + 1)) {\n        return true;\n    }\n    return false;\n}\n
    \/*
     * Simply by making sure with a placeholder value (-1) if the queue is empty. 
     *\/\nbool is_queue_empty(CircularQueue queue) {\n    if(queue.front == -1) {\n        return true;\n    }\n    return false;\n}\n\nbool add_element_in_queue(CircularQueue * queue, int data) {\n    if(is_queue_full(*queue) == false) {\n        if(queue->front == -1) {\n            queue->front = 0;\n        }\n        queue->end = (queue->end + 1) % SIZE_OF_QUEUE_IN_BYTES;\n        queue->data[queue->end] = data;    \n        return true;\n    }\n    return false;\n}\n\nbool remove_element_from_queue(CircularQueue * queue) {\n    if(is_queue_empty(*queue) == false) {\n        if(queue->front == queue->end) {\n            queue->front = -1;\n            queue->end   = -1;\n        } else {\n            queue->front = (queue->front + 1) % SIZE_OF_QUEUE_IN_BYTES;\n        }\n        return true;\n    }\n    return false;\n}\n\nvoid print_full_queue(CircularQueue queue) {\n    for(int idx = 0; idx < SIZE_OF_QUEUE_IN_BYTES; idx++) {\n        printf(\"%d \", queue.data[idx]);\n    }\n    printf(\"\\n\");\n}\n\nint main()\n{\n    init_circular_queue(&Circular_Queue);\n    for(int idx = 1; idx < 15; idx++) {\n        add_element_in_queue(&Circular_Queue, idx);\n        print_full_queue(Circular_Queue);\n    }\n    return 0;\n}\n<\/pre><\/div>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
    What is Circular Queue? The Circular Queue is the Extention of a queue that is a linear…<\/p>\n","protected":false},"author":1,"featured_media":388,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[34],"tags":[90,91],"class_list":["post-387","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-digital-communication","tag-circular-queue","tag-queue"],"acf":[],"views":372,"featured_image_urls":{"full":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"thumbnail":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",150,101,false],"medium":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",300,202,false],"medium_large":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"large":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"1536x1536":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"2048x2048":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"tp-image-grid":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"covernews-slider-full":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"covernews-slider-center":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"covernews-featured":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",520,350,false],"covernews-medium":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",505,340,false],"covernews-medium-square":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",371,250,false],"_nx_notification_thumb":["https:\/\/embeddedwala.com\/beta\/wp-content\/uploads\/2023\/06\/Circular-quene-c-banner.png",100,67,false]},"author_info":{"display_name":"embeddedwala","author_link":"https:\/\/embeddedwala.com\/beta\/author\/embeddedwala\/"},"category_info":"Digital Communication<\/a>","tag_info":"Digital Communication","comment_count":"0","_links":{"self":[{"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/posts\/387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/comments?post=387"}],"version-history":[{"count":5,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/posts\/387\/revisions"}],"predecessor-version":[{"id":6198,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/posts\/387\/revisions\/6198"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/media\/388"}],"wp:attachment":[{"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/media?parent=387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/categories?post=387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/embeddedwala.com\/beta\/wp-json\/wp\/v2\/tags?post=387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}