If you have an AUTO_INCREMENT column, the last inserted row will have the highest id and the first inserted will have the lowest.
When you want to remove an element from the queue, do ("ai_col" = the name of the AUTO_INCREMENT column)
Code:
SELECT ... FROM tab WHERE id=MIN(ai_col);
DELETE FROM tab WHERE id=MIN(ai_col);
If there are many clients accessing the "queue" at the same time, use some locking mechanism to avoid race conditions and other weird stuff.