Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Circular Queue PDF

    Uploaded by

    Badnaam Raja
    Circular queues are a linear data structure where the last position connects to the first, forming a circle. This allows insertion when the queue is full by reusing empty spaces. Operations have constant time complexity. Dequeues allow insertion and deletion from both ends, combining properties of stacks and queues. They are commonly used for memory management, traffic control systems, and process scheduling in operating systems.

    Copyright:

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

    Circular Queue PDF

    Uploaded by

    Badnaam Raja
    31 views15 pages
    Circular queues are a linear data structure where the last position connects to the first, forming a circle. This allows insertion when the queue is full by reusing empty spaces. Operations have constant time complexity. Dequeues allow insertion and deletion from both ends, combining properties of stacks and queues. They are commonly used for memory management, traffic control systems, and process scheduling in operating systems.

    Original Title

    Circular_queue.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Circular queues are a linear data structure where the last position connects to the first, forming a circle. This allows insertion when the queue is full by reusing empty spaces. Operations have constant time complexity. Dequeues allow insertion and deletion from both ends, combining properties of stacks and queues. They are commonly used for memory management, traffic control systems, and process scheduling in operating systems.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views15 pages

    Circular Queue PDF

    Uploaded by

    Badnaam Raja
    Circular queues are a linear data structure where the last position connects to the first, forming a circle. This allows insertion when the queue is full by reusing empty spaces. Operations have constant time complexity. Dequeues allow insertion and deletion from both ends, combining properties of stacks and queues. They are commonly used for memory management, traffic control systems, and process scheduling in operating systems.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Circular Queues

    • Circular Queue is a linear data structure in which the


    operations are performed based on FIFO (First In
    First Out) principle and the last position is connected
    back to the first position to make a circle. It is also
    called ‘Ring Buffer’.
    Why Circular queue?
    • Limitation of Linear queue:- inserting a new
    element after the queue becomes full is not
    possible even if there is free space in the
    queue.
    • This is solved by the circular queues. Here the
    end node is pointing to the initial node.
    • Complexity of insertion and deletion is
    constant.
    Circular queue implementation
    #define N 6
    Int queue[N];
    Int f=-1,r=-1; //initially front and rear are -1,
    queue is empty
    Void enqueue(int x)
    {
    if(f==-1 && r==-1) //empty case
    {
    f=rear=0;
    queue[r]=x;
    }
    elseif((r+1)%N==f)) //full
    printf(“queue is full”);
    else //at least one element exist
    {
    r=(r+1)%N;
    queue[r]=x;
    }
    }
    Void dequeue( )
    {
    if(f==-1 && r==-1) //underflow
    {
    f=rear=0;
    queue[r]=x;
    }
    elseif(f == r) //only one element exist
    f = r = -1;
    else {
    f = (f+1)%N;
    }
    }
    Applications
    • Memory Management: The unused memory
    locations in the case of ordinary queues can be
    utilized in circular queues.
    • Traffic system: In computer controlled traffic system,
    circular queues are used to switch on the traffic
    lights one by one repeatedly as per the time set.
    • CPU Scheduling: Operating systems often maintain a
    queue of processes that are ready to execute or that
    are waiting for a particular event to occur.
    DEQUEUE(Doubly Ended Queue)
    • A linear data structure in which Insertion and
    deletion are allowed from both the ends.
    • It is not possible in Linear or circular queue.
    • It is following both stack and queue structure.
    • For implementation use circular queue
    • Two type
    – Input restricted Insertion only through one end
    – Output restricted deletion only through one
    end
    • Operations on Dequeue
    – Insertion at rear
    – Insertion at front
    – Deletion from front
    – Deletion from rear
    • Applications
    – Applications of stack and queue
    – Palindrome check-read from both the ends
    – Multiprocessor scheduling
    Implementation
    #define N 5
    Deque[N]
    f = r = -1
    Void enquefront(int x)
    {
    If((f==0 && r==N-1)||(f==r+1))
    Printf(“Q is full”);
    elseif(f==-1 && r==-1) {
    f=r=0;
    deque[f]=x;
    }
    Elseif(f==0)
    {
    f=N-1;
    Deque[f]=x;
    }
    Else
    {
    F--;
    Deque[f] =x;
    }
    }
    Void enquerear(int x)
    {
    If((f==0 && r==N-1)||(f==r+1))
    Printf(“Q is full”);
    elseif(f==-1 && r==-1) {
    f=r=0;
    deque[r]=x;
    }
    Elseif(r==N-1)
    {
    r=0;
    Deque[r]=x;
    }
    Else
    {
    r++;
    Deque[r] =x;
    }
    }
    Void displayque()
    {
    Int i=f;
    While(i!=r)
    {
    printf(“%d”,deque[i]);
    i=(i+1)%N;
    }
    printf(“%d”,deque[r]);
    }
    Void dequefront( )
    {
    if(f==-1 && r==-1)
    printf(“ Q is empty”);
    Elseif(r==f)
    f=r=-1;
    Elseif(f=N-1)
    {
    printf(“%d”,deque[f]);
    f=0;
    }
    Else
    f++;
    }
    Void dequerear( )
    {
    if(f==-1 && r==-1)
    printf(“ Q is empty”);
    Elseif(r==f)
    f=r=-1;
    Elseif(r==0)
    {
    r=N-1;
    Printf(“%d”,deque[r]);
    }
    Else
    r--;
    }

    You might also like