Applications of queues
Here is an application of FIFOs in multiprocessor computers. A multiprocessor computer can be regarded as a distributed system.

To make a multiprocessor computer that correctly executes multiprocess programs, two requirements are given by Leslie Lamport [1]. The second one reads,


  Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.




For what it concerns applications of non-FIFO queues, I am confused about your requirement: Why do you use a queue if you don't need its features? 

Anyway, is the priority queue an application in which we need to investigate elements of the queue which are not at its extreme sides?



[1] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. By Leslie Lamport. IEEE Transactions on Computers, 1979.