Queues in C

Discussion in 'C Programming' started by mike79, Sep 9, 2003.

  1. mike79

    mike79 Guest

    Hi all,

    I have attempted to implement a queue in C.

    So far all is well, but I have a question to ask you experts in
    regards to my implementation.

    Say I have a queue of integers. My queue will be an array of integers
    which could hold 100 elements for example.

    I have two variables namely firstElement and lastElement. When I add
    an integer to the queue, the lastElement variable will be incremented
    and the integer stored at this index (lastElement) into the queue
    array.

    When I remove an element from the queue, the integer stored at
    "firstElement" will be returned and the variable firstElement will
    also be incremented.

    If I keep doing this, soon the lastElement will reach the end of the
    queue, and I will run out of space. Should I shift all the elements
    back to the start of the queue array everytime I get a value from the
    queue, or should this be how a queue is implemented? But if I shift
    everytime i retrieve data from the queue, wouldn't this slow down the
    program alot?

    Thank you for all the help and support,
    mike79
     
    mike79, Sep 9, 2003
    #1
    1. Advertisements

  2. Yes, this is queue in action, first in last out.

    Perhaps you want a _circular_ queue or a.k.a. ring buffer.

    In a circular queue, based on an array, when the pointers go past
    the end of the array, they are moved to the beginning of the array.
    One technique for implementing a circular queue is to have two
    pointers, first and last; and a boolean variable to indicate full
    or empty. When first == last, the queue is either full or empty
    which the boolean variable is used for.

    For more information about this and other data structures,
    read
    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c++-faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c++/faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
     
    Thomas Matthews, Sep 9, 2003
    #2
    1. Advertisements

  3. mike79

    Ema Guest

    You can implement a circular buffer for the queue.
    In practice, it means that you increment firstElement and
    lastElement module (%) the lenght of the array.

    You must also pay attention not to reach lastElement with firstElement,
    that is "to dequeue elements that are not been enqueued".

    Bye,
    Ema

    PS. Sorry for my English...
     
    Ema, Sep 9, 2003
    #3
  4. mike79

    Fogus Guest

    If I keep doing this, soon the lastElement will reach the end of the
    Why not just make the array circular. That is, when you get to the
    index length-1 loop the index back around to zero. The only problem
    with this is that if you keep adding elements then the firstElement and
    lastElement indexes will cross... but such is life with static
    structures.

    -m
     
    Fogus, Sep 9, 2003
    #4
  5. mike79

    Peter Ammon Guest

    *cough*

    [...]

    -Peter
     
    Peter Ammon, Sep 9, 2003
    #5
  6. mike79

    Default User Guest


    That would be a stack. Queues are FIFO.



    Brian Rodenborn
     
    Default User, Sep 9, 2003
    #6
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.