What is the efficient way of implementing a queue, inorder to learn how it is implemented?
EDIT: I looked into stl::queue code inorder to learn abt how it is implemented, but the template code making it difficult to understand. After all there is better efficient way is used than having a linked list.
The most efficent way is to have someone else do it.
Both C++ and C# (and .NET et al) have one in their native libraries.
Of course for any production code you should rely on a robust library implementation that's already withstood the test of time.
That said, for self-teaching it can be fun to write one yourself. I've done it before.
The most efficient way I know of is to use a similar approach to what most resizable collections do internally: store an array, which is increased in size (typically doubled) as needed when the collection's size reaches the length of the array.
A queue is a bit different from an ordinary collection, though, because you want to be able to pop off from the opposite end from where elements are pushed.
Obviously, to remove the first element and shift all other elements down one index would be costly and pointless. So instead you keep track of the starting and ending indices yourself. When the collection reaches the end of the array you use % to start pushing elements back at the beginning.
The key is simply working out your math so that you handle all cases, e.g., correctly growing the array when the queue is full, getting your bounds checks right, incrementing the start index (or looping back to 0) on every pop, etc.
Clearly, the design I've described above has many limitations: thread safety, for example. But for a simple, single-threaded, efficient implementation, it's a pretty good starting point.
Good luck -- and I also recommend posting your code if/when you've got one that you think is working!
If you can accept a maximum size for the queue, a circular buffer is super efficient. Because the library functions can't assume a maximum size they don't use this technique.
front, back, push_back, and pop_front. Because these containers start out empty and grow as needed, so does the queue.In the most generic sense, a linked-list would be your best bet if you maintain a front and rear pointer. In this case, queue insertion and deletion is an O(1) operation. You can also implement one using an array and maintaining indices for the front and rear. The math is marginally more involved (when you insert or delete you have to take into account "wrapping" to avoid going out of bounds).
For C++, stl::queue<>.
Do you understand how a queue works?
Do you understand how stl queue works?
Do you understand that "most efficient" is an abstract concept that can't hold true for every case?
If you get all of that, the "most efficient c++ queue algorithm" will come to you
If you need a thread-aware queue implementation you can try my own library. It's not complete yet, but it's well documented.
Edit: it's impemented by linked lists.
How many threads may be reading your queue at once? How many may be writing it at once? Can one thread be reading while another is writing? Do you want to pre-allocate space for the maximum size of queue? Do you need a way for a reader to block while waiting for data, or for a writer to block when the queue is full? How many objects per second do you expect to be feeding through the queue?
The optimal approach will depend upon the answers to those questions.
If your main goal is to learn how it is implemented, then you should work with linked lists. They are fun to work with and really shows the difference from sequential arrays and teaches a lot about memory.
