Queue implementation

This is a discussion on Queue implementation within the C++ Programming forums, part of the General Programming Boards category; Not sure if this belonged on the Articles board or not. I just read today's article off the main CProg ...

  1. #1
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879

    Queue implementation

    Not sure if this belonged on the Articles board or not.

    I just read today's article off the main CProg site, here. Seems a little odd to me how it's implemented; IMO, conceptually a linked list lends itself to the purpose much more nicely - when you dequeue an element, the head automatically is changed, and when you queue an element the tail is automatically changed, and no shuffling forward is ever done - all without having to resort to sneaky circles. You might lose a little time allocating/constructing/destroying each node, but you wouldn't have to worry about size limitations and reallocating your dynamic array every time you run out of space (which would lose you even more time).

    Thoughts anyone?
    Last edited by Hunter2; 02-18-2005 at 04:10 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  2. #2
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    Uh, what's your question?

    I think he used a queue rather than a linked-list simply because he wanted to demonstrate a queue.

    having to resort to sneaky circles.
    Typically, that's how you make a queue/buffer. It's very efficient. Conceptually, you are shifting data thru the queue, but actually physically-shifting all of the data would be ridiculous!

    When you receive streaming multimedia, a circular buffer is used:

    You reserve a fixed amount of memory.*

    You start filling the queue/buffer by incrementing a pointer.

    If you are using the queue as a buffer, you wait for the queue to partially fill-up, so you can read it at a constant rate, even if it's not getting filled at a constant rate.

    You start reading the queue/buffer with another incrementing-pointer.

    When the write-pointer gets to the end, it starts-over, overwriting the old (already-read) data.

    You have to make sure that the write-buffer doesn't "overtake" the read buffer... or, buffer overflow! And, you have to make sure that the read-pointer doesn't "overtake" the write buffer... or, buffer underflow.

    *It's not unusual for a queue to be implemented in hardware... memory that can't be accessed by the CPU. Printers have a hardware queue. My video capture card has a hardware buffer which causes an obvious delay during capture.
    Last edited by DougDbug; 02-18-2005 at 07:46 PM.

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >I think he used a queue rather than a linked-list simply because he wanted to demonstrate a queue.
    DougDbug, I think you misunderstood what Hunter is saying. He's saying why not implement a queue as a linked list?

    It makes sense to me, and I would not be surprised if the STL in fact implements a queue as a linked list. After all, you only need direct access to the front and back of the queue, so why not a linked list?

  4. #4
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>I think he used a queue rather than a linked-list simply because he wanted to demonstrate a queue.
    Swoopy's nailed what I meant

    I see, though, how implementing queues in this (the article's) way can be more efficient - assuming you're just using the queue as a fixed-size buffer, i.e. for streaming media, you save time by overwriting rather than creating and destroying nodes. However, if you want something that will resize indefinitely as you push more data onto the queue, then a linked list would probably be better to use.

    Interestingly enough, the STL queue uses a template argument for its container type, with the default being std::deque; and MSDN also suggests std::list as an alternate container.
    Quote Originally Posted by Visual Studio MSDN
    Suitable underlying container classes for queue include deque and list, or any other sequence container that supports the operations of front, back, push_back, and pop_front.
    I am curious to know if deque (double-ended queue) is implemented as described in the article.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 09:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Queue implementation
    By kolliash in forum C Programming
    Replies: 1
    Last Post: 06-01-2008, 09:25 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 10:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 12:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21