Queue implementation

[Hunter2]

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?

[DougDbug]

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.

[swoopy]

>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?

[Hunter2]

>>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.

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.