Scribd Logo
Upload

Welcome to Scribd!

  • 44 views

    Queue: Introduction To Data Structures

    Uploaded by

    kamala thakur
    A queue is a first-in first-out (FIFO) data structure. Elements can be added to the rear of the queue and removed from the front of the queue. Queues can be implemented using arrays or circular arrays. With arrays, the queue moves in one direction and freed spaces are not reused, possibly leaving spaces empty. Circular arrays view the array as wrapping around so the queue can move in either direction without wasted space.

    Copyright:

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

    Queue: Introduction To Data Structures

    Uploaded by

    kamala thakur
    44 views11 pages
    A queue is a first-in first-out (FIFO) data structure. Elements can be added to the rear of the queue and removed from the front of the queue. Queues can be implemented using arrays or circular arrays. With arrays, the queue moves in one direction and freed spaces are not reused, possibly leaving spaces empty. Circular arrays view the array as wrapping around so the queue can move in either direction without wasted space.

    Original Title

    3 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 first-in first-out (FIFO) data structure. Elements can be added to the rear of the queue and removed from the front of the queue. Queues can be implemented using arrays or circular arrays. With arrays, the queue moves in one direction and freed spaces are not reused, possibly leaving spaces empty. Circular arrays view the array as wrapping around so the queue can move in either direction without wasted space.

    Copyright:

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

    Queue: Introduction To Data Structures

    Uploaded by

    kamala thakur
    A queue is a first-in first-out (FIFO) data structure. Elements can be added to the rear of the queue and removed from the front of the queue. Queues can be implemented using arrays or circular arrays. With arrays, the queue moves in one direction and freed spaces are not reused, possibly leaving spaces empty. Circular arrays view the array as wrapping around so the queue can move in either direction without wasted space.

    Copyright:

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

    Queue

    Introduction to Data Structures


    Queue
    • Modeled on real queue at counters, service centers, etc.
    • When input is to be processed as per arrival, but can’t wait for all
    input to be ready before processing.
    • Insertion at the tail; deletion from the front.
    • Unlike real queues, for each deletion we don’t want to move all the
    elements.

    Introduction to Data Structures


    Queue Operations
    • clear() – Clear the queue
    • isEmpty()
    • isFull()
    • enqueue(el) – Put element el at the end of the queue
    • dequeue() – Remove the first element from the queue
    • firstEl() – Return the first element in the queue without removing it

    Introduction to Data Structures


    Implementation Using Arrays

    a b c d

    first last
    • ‘last’ moves right for every addition
    • ‘first’ moves right for every deletion
    • empty when first = last + 1
    • full when last = arraysize
    • but ...

    Introduction to Data Structures


    Implementation Using Arrays

    • Queue moves right


    • Locations freed by delete not reused
    • Queue may be flagged full even with a single element!

    Introduction to Data Structures


    Implementation Using Circular Arrays
    • View array as circular -
    q[max +1] -> q[0]; q[0 - 1] -> q[max] 0
    first
    • last and first travels clockwise
    • first need not be less than last
    last

    Introduction to Data Structures


    Implementation Using Circular Arrays
    public class QueueArray{
    private int first, last, size, count;
    private Object[] storage;
    public QueueArray(int n){
    first = 0;last = -1;count = 0;size = n;
    storage = new Object[n];
    }
    public boolean isFull(){
    return count >= size;
    }
    public boolean isEmpty(){
    return count == 0;
    }
    Introduction to Data Structures
    Implementation Using Circular Arrays
    public void enqueue(Object el){
    last = (last+1)%size; count++;
    storage[last] = el;
    //add suitable error checks
    }
    public Object dequeue(){
    Object tmp = storage[first];
    first = (first+1)%size; count--;
    return tmp;
    //add suitable error checks
    }

    Introduction to Data Structures


    Example
    Railway Ticket Reservation
    • Ten counters, all identical.
    • Customers arrive - Assume only one type of transaction.
    • A single queue.
    • When a counter falls vacant, the person at the front of the queue
    goes there.
    • Simulate this.

    Introduction to Data Structures


    Ticket Counter
    • A queue structure will maintain the queue.
    • An array [1..c] records status of the counters. -1
    indicates empty; otherwise expected time of
    completion.
    • For each time tick:
    • if any arrival, insert in the queue.
    • if any counter has serve [i] = timer, set serve[i] = -1
    • if any counter vacant, dequeue a person and send to
    first available counter, update serve array.
    • Can extend to record max queue size, vacant
    counter time etc.

    Introduction to Data Structures


    Summary
    • Data Structures: useful abstractions for a programmer
    • Arrays, Stacks and Queues: simple linear data structures
    • We will discuss “better” representations for these, and introduce
    more sophisticated DS in subsequent sessions.

    Introduction to Data Structures

    You might also like