## The Queue Data Structure in C++By Eric Suh
The cafeteria line is one type of queue. Queues are often used in programming networks, operating systems, and other situations in which many different processes must share resources such as CPU time. One bit of terminology: the addition of an element to a queue is
known as an Although
the concept may be simple, There are a couple of basic ways to implement a queue. The first is to just make an array and shift all the elements to accommodate enqueues and dequeues. This, as we said above, is slow. The slowness of the previous method is that with many elements,
the shifting takes time. Thus, another method, instead of shifting
the elements, Unfortunately, this method is much more complicated than the basic method. Instead of keeping track of just the enqueue point (the "end"), we also need to keep track of the dequeue point (the "front"). This all gets even more complicated when we realize that after a bunch of enqueues and dequeues, the line will need to wrap around the end of the array. Think of the cafeteria line. As people enter and leave the line, the line moves farther and farther backwards, and eventually it will circle the entire cafeteria and end up at its original location. The best way to understand all of this is to read some source code. The example source code uses the second method, and is commented to help you understand. Try working through the code on paper. Check out sample code of a queue implementationPrevious: Learn about stacks Next: Learn about heaps Back to algorithm and data structure tutorial index |