Abstract: Priority queues are widely used in many parallel algorithms,e.g.,multiprocessor sche- duling and some combinatorial search algorithms.But the speedups of these algorithms are often limi- ted by the access conflict of shared priority queues.In this paper,we design a concurrent insertion and deletion algorithm for linear list priority queues,with less overhead,to achieve more parallelism. The algorithm assures that the priority order of queue is the same as that of the sequential algorithm, i.e.,deletion operation returns the best one of all elements inserted and being inserted.We also int- roduce the most efficient concurrent insertion and deletion algosithm of heap structure,and compare its efficiency and scope with that of linear lists.On this basis,we propose the structure of hash list priority queue to overcome the shortcomings of linear lists.The experiments on ENCORE Multimax 520 multiprocessor has verified the results of theoretical analysis:Using linear list priority queue can greatly improve the efficiency of parallel branch and bound algorithms.