What is an efficient way to implement a queue?

Question

What is an effective way to implement a queue to find out how it is implemented?

EDIT: I looked into the stl :: queue code inorder to find out how it is implemented, but the template code makes it difficult to understand. In the end, a more efficient way is used than a linked list.

Answer 1

Of course, for any production code, you must rely on a reliable library implementation that has already stood the test of time.

However, for self-study this may be interesting to write yourself. I have done this before.

The most efficient way I know is to use a similar approach to what most modified collections do: store an array that grows in size (usually doubles) as needed when the collection reaches the length of the array.

The queue is slightly different from the regular collection because you want you to be able to jump from the opposite end from which the elements were clicked.

Obviously, to remove the first element and shift all other elements down, one index will be costly and pointless. So instead, you track the start and end indices yourself. When the collection reaches the end of the array, you use % to start pushing items back at the beginning.

The key is simply to work out your math so that you handle all cases, for example, grow the array correctly when the queue is full, correctly evaluate your boundaries, increase the start index (or return to 0) for each pop, etc.

Obviously, the design described above has many limitations: thread safety, for example. But for a simple, single-threaded, efficient implementation, this is a pretty good starting point.

Good luck - and I also recommend publishing your code if / when you have one that you think works!

Answer 2

The most effective way is to get someone else to do it.

Both C ++ and C # (and .NET and others) have one in their native libraries.

Answer 3

In the most general sense, a linked list would be a better choice if you keep the front and rear pointer. In this case, inserting and deleting a queue is an O(1) operation. You can also implement one using an array, and maintain indexes for the front and back. Math is a bit involved (when you insert or delete, you should consider “wrapping” to avoid going beyond).

Answer 4

If you can accept the maximum size for a queue, the circular buffer is super efficient. Since library functions cannot take maximum size, they do not use this technique.

Answer 5

For C ++ stl :: queue <>.

Answer 6

Do you understand how the queue works ?

Do you understand how stl queue works ?

Do you understand that the "most effective" is an abstract concept that cannot be true for every case?

If you get all this, the "most efficient C ++ queue algorithm" will come to you.

Answer 7

If you need a thread-supported queue implementation, you can try my own library . It is not completed yet, but it is well documented.

Edit: It will fit into linked lists.

Answer 8

How many threads can your queue read at once? How much can be written at once? Can one thread read while the other writes? Do you want to preallocate space for the maximum queue size? Do you need a way to lock the reader while waiting for data or to lock the record when the queue is full? How many objects per second do you expect to feed through the queue?

The best approach will depend on the answers to these questions.

Answer 9

If your main goal is to find out how it is implemented, you should work with linked lists. They work with pleasure and really show the difference between consecutive arrays and talk a lot about memory.