Regarding how to “create a queue of some sort for Arduino”, about the first thing to settle is how many items may need to be queued. On a typical personal computer with gigabytes of RAM, queue size often is not much of an issue ... one just allocates a few more megabytes whenever necessary. On an typical Arduino, however, with a few kilobytes or few tens of kilobytes of RAM, use of dynamic (heap) allocation is risky unless you carefully analyze possible execution paths.
If you are ok with a fixed queue size, the next issue is what kind of queue, eg FIFO, LIFO, priority, etc. The question's concern about a “shift the data to the left, so that the next one will be selected in the queue” issue suggests a FIFO (first in first out) queue is desired. For this, a circular buffer or circular queue is a relatively-low-overhead method often used. Using terms from the wikipedia article, Start and End pointers are maintained, marking next-data-out and last-data-in positions. Via modular arithmetic or
if tests, each of these pointers wraps to array front whenever it goes past the array end. The queue is empty if
Start == End (modulo N, if queue size is N) and full if
Start == End+1.
If an interrupt-driven process can modify pointers asynchronously to the main thread of execution, then synchronization methods need to be used to ensure atomic updates of pointers. (This is true for all kinds of queues, not just circular ones.)
If instead of a FIFO queue you need a priority queue, a binary heap is easy to implement. Usually Fibonacci heaps and binomial heaps are not worth the extra trouble of implementing, except when you need efficient heap merging or secondary operations like decreasing keys of elements. The Summary of running times section of wikipedia's binomial heap article shows the complexity of different operations across different heap structures. Note that with Arduino RAM being so limited, a complexity difference like Θ(log n) vs Θ(1) is negligible; simplicity of code, leading to a compact implementation, is more important.
Note, also see QueueList Library For Arduino at arduino.cc. This library apparently uses dynamic allocation. It provides methods
push(), pop(), peek() et al. Also see QueueArray Library For Arduino at arduino.cc, which provides the same methods as QueueList, plus
dequeue() as synonyms for
pop(). Where QueueList uses lists to build its data structures, QueueArray uses arrays.
OsWrap at arduino.cc is a heavy package (eg 15KB flash, 1.5KB RAM) that supports various message and priority queue structures.
Depending on your rationale for using a queue, Task Scheduler Library may also be of interest.
As noted in Mikael Patel's comments above, Cosa platform software includes a Queue class, which is a “Template class for ring-buffer for queueing data elements”, with usage of the class illustrated in an Event class, which in turn is used in a Job class.