Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 62 views

    4 - Linear Queue and Circular Queue

    Uploaded by

    naveen ds
    A queue is a linear data structure that follows FIFO (First In First Out) ordering. Elements are inserted at the rear end and deleted from the front end. It can be represented using an array with pointers to track the front and rear positions. Enqueue operations increment the rear pointer while dequeue operations increment the front pointer. Circular queues overcome the limitation of regular queues by wrapping the pointers around to the beginning of the array when they reach the end.

    Copyright:

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

    4 - Linear Queue and Circular Queue

    Uploaded by

    naveen ds
    62 views13 pages
    A queue is a linear data structure that follows FIFO (First In First Out) ordering. Elements are inserted at the rear end and deleted from the front end. It can be represented using an array with pointers to track the front and rear positions. Enqueue operations increment the rear pointer while dequeue operations increment the front pointer. Circular queues overcome the limitation of regular queues by wrapping the pointers around to the beginning of the array when they reach the end.

    Original Description:

    Original Title

    4_Linear Queue and Circular Queue

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    A queue is a linear data structure that follows FIFO (First In First Out) ordering. Elements are inserted at the rear end and deleted from the front end. It can be represented using an array with pointers to track the front and rear positions. Enqueue operations increment the rear pointer while dequeue operations increment the front pointer. Circular queues overcome the limitation of regular queues by wrapping the pointers around to the beginning of the array when they reach the end.

    Copyright:

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

    4 - Linear Queue and Circular Queue

    Uploaded by

    naveen ds
    A queue is a linear data structure that follows FIFO (First In First Out) ordering. Elements are inserted at the rear end and deleted from the front end. It can be represented using an array with pointers to track the front and rear positions. Enqueue operations increment the rear pointer while dequeue operations increment the front pointer. Circular queues overcome the limitation of regular queues by wrapping the pointers around to the beginning of the array when they reach the end.

    Copyright:

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

    QUEUES - FIFO

    • Queue is a linear structure in which Deletions can take place


    at one end only, called the Front and Insertions can take place
    only at other end, called the Rear.

    • Three everyday examples of such a structure


    – Waiting Automobiles for Fuel
    – People Waiting in Line at Bank
    – Programs with the same Priority

    AAA BBB CCC DDD AAA Front


    DDD Rear
    Dr. P. Gayathri, Associate Professor, SCOPE 1
    Representation of Queues

    • FRONT: Containing the Location of the Front Element


    • REAR: Containing the Location of the Rear Element
    • Deletion: FRONT := FRONT + 1
    • Insertion: REAR := REAR + 1
    • After N Insertions, the Rear Element of the Queue will Occupy
    QUEUE [N]
    • Enqueue is the term used to denote insertion and dequeue is
    the term used to denote deletion operation

    Dr. P. Gayathri, Associate Professor, SCOPE 2


    Representation of Queues Cont…

    FRONT- 1 AAA BBB CCC DDD ……. ……. ……


    REAR - 4 1 2 3 4 5 6 N

    FRONT- 2 BBB CCC DDD ……. ……. ……


    REAR - 4 1 2 3 4 5 6 N

    FRONT- 2 BBB CCC DDD EEE FFF ……


    REAR - 6 1 2 3 4 5 6 N

    FRONT- 3 CCC DDD EEE FFF ……


    REAR - 6 1 2 3 4 5 6 N
    Dr. P. Gayathri, Associate Professor, SCOPE 3
    ENQ (ITEM)

    1. If REAR = N
    Then Print OVERFLOW
    2. Set REAR=REAR+1
    3. Set QUEUE[REAR]=ITEM
    4. If FRONT= 0 //queue is initially empty
    Then Set FRONT=1

    Dr. P. Gayathri, Associate Professor, SCOPE 4


    DEQ ()

    1. If FRONT=0, then print UNDERFLOW


    2. Else Set ITEM=QUEUE[FRONT]
    3. If FRONT=REAR, then //Queue has only one element]
    Set FRONT=0 and REAR=0
    Else Set FRONT=FRONT+1
    4. Print ITEM

    Dr. P. Gayathri, Associate Professor, SCOPE 5


    Queue applications
    • Printer
    • Device connected to a network
    • Client-server communication

    Dr. P. Gayathri, Associate Professor, SCOPE 6


    Circular Queue
    • Queue – Disadvantage is once if rear has
    reached the (end)max position, we cannot
    insert an element into queue though the
    number of elements is lesser than the max
    capacity of queue
    • Solution – Circular queue – whenever front or
    rear reaches the end of the queue, it is
    wrapped around to the beginning.
    Diagrammatic representation
    Diagrammatic representation
    Full queue condition
    (Rear == max and front ==1) or (rear+1 == front)
    Diagrammatic representation
    ENQ (ITEM)

    1. If (Rear == max and front ==1) or (rear+1 == front)


    Then Print OVERFLOW
    2. If rear == MAX
    rear = 1
    else rear = rear +1
    3. Set QUEUE[rear]=ITEM
    4. If FRONT= 0 //queue is initially empty
    Then Set FRONT=1

    Dr. P. Gayathri, Associate Professor, SCOPE 12


    DEQ ()

    1. If FRONT=0, then print UNDERFLOW


    2. Else Set ITEM=QUEUE[FRONT]
    3. If FRONT=REAR, then //Queue has only one element]
    Set FRONT=0 and REAR=0
    Else if (FRONT = MAX) Then set Front = 1
    else Set FRONT=FRONT+1
    4. Print ITEM

    Dr. P. Gayathri, Associate Professor, SCOPE 13

    You might also like