Sure it is. Priority queues are a common example of this behavior, and they're still queues.

chj's question is interesting. It's not obvious how to build a lock-free code in the original article's framework if you aren't representing your queue as a list, but many queues are not represented this way. If you need this 'insert in the middle of the queue' operation, you probably aren't representing your queue as with a linked list since insertion will be inefficient - chances are you're using a heap.