There are much better ways to implement a concurrent queue than the ones shown. Using locks for every single queue/dequeue is a very good way to completely kill performance. A much better alternative is to use hand-over-hand locking, or use CAS for a lock-free implementation.

TAOMP ( http://www.amazon.com/The-Multiprocessor-Programming-Maurice... ) goes over this in great detail and is overall an excellent book.