Priority queue vs standard queue

[hopesfall]

My professor stated that a Priority Queue ADT cannot be implemented by wrapping around a Queue ADT, nor vice-versa. Why is that?

[Duthomhas]

Because a regular queue properly does not support insertions/deletes except for push to front and pop from back.

(The STL std::queue can be used like a proper queue, but it also supports non-queue operations like insert and delete etc.)

[ne555]

No, it does not. http://cplusplus.com/reference/stl/queue/
I think that you are referring to std::deque

However you don't need insertions/deletes but reordering.
Because the priority_queue is a sorted container whereas the queue is an ordered one.

[Duthomhas]

Oh crap! You are right. I was thinking of std::deque. :-(

(The STL queue needs an underlying container, and it defaults to using a deque.)

You only add things one at a time in a priority queue, so adding a thing is the same as inserting it in its sorted location.

[ne555]

IIRC you add at the end, and then climb to your place. That moves O(lg n) elements in every push/pop. (priority queue as a heap)

I think that using std::vector to support the common queue would be a lot better (circular buffer)

[JLBorges]

> My professor stated that a Priority Queue ADT cannot be implemented by wrapping around a Queue ADT

Your professor is wrong. The implementation would be very (very) inefficient, though.

#include <functional>
#include <queue>
#include <initializer_list>
#include <iostream>

template< typename T, typename CMP = std::less<T> > struct pq_over_q
{
    explicit pq_over_q( CMP c = CMP() ) : cmp(c) {}

    template < typename ITERATOR > pq_over_q( ITERATOR begin, ITERATOR end )
    { for( ; begin != end ; ++begin ) push(*begin) ; }

    template < typename U > pq_over_q( std::initializer_list<U> ilist )
    { for( auto iter = ilist.begin() ; iter != ilist.end() ; ++iter ) push(*iter) ; }

    void push( const T& v )
    {
        q.push(v) ;
        bring_top_to_front() ;
    }

    T& top() { return q.front() ; }

    const T& top() const { return q.front() ; }

    void pop() { q.pop() ; bring_top_to_front() ; }

    bool empty() const { return q.empty() ; }

    std::size_t size() const { return q.size() ; }

    private:
       std::queue<T> q ;
       CMP cmp ;

       void bring_top_to_front()
       {
           if( !q.empty() )
           {
               T top( find_top() ) ;
               while( cmp( q.front(), top ) ) rotate() ;
           }
       }

       T find_top()
       {
           T top( q.front() ) ;
           for( std::size_t i = 1 ; i < q.size() ; ++i )
           {
               rotate() ;
               if( cmp( top, q.front() ) ) top = q.front() ;
           }
           return top ;
       }

       void rotate() { if( q.size() > 1U ) q.push( q.front() ) ; q.pop() ; }
};

int main()
{
    pq_over_q< int, std::greater<int> > pq = { 1, 2, 7, 4, 9, 2, 5, 4, 5, 4, 7, 6 } ;
    while( !pq.empty() ) { std::cout << pq.top() << ' ' ; pq.pop() ; }
}

This can be made a lot faster by caching the top and using multiple queues instead of just one; but it would still be very inefficient in comparison to the normal binary heap implementation.