CODEWITHSUNDEEP
c++data-structuresstackqueueheap
Duong Phan
Duong Phan

Reputation: 341

Priority stack in C++

C++ standard library provides a priority queue with priority_queue. But does it also provide a priority stack ? I looked for priority_stack but did not find anything.

Upvotes: 4

Views: 5358

Answers (3)

Gardener
Gardener

Reputation: 2660

In c++, the standard template library (STL) provides a priority_queue. See for example priority_queue. The STL does not provide a priority_stack container.

Upvotes: 2

Christophe
Christophe

Reputation: 73366

What is a priority stack ?

Stacks and queues are similar abstract container data structures. Their main abstract difference, is that the stack implements the LIFO principle (Last In First Out), whereas a queue is FIFO (First In First Out).

The priority is orthogonal to the order in which items are removed. Priority means that an item with a higher priority is removed before an item with the lower priority:

  • In both case, if only one element has the highest priority, it will be the one to be removed first.
  • But if several elements have the same highest priority, the priority stack will first remove the latest pushed one, whereas the priority queue will first remove the first enqueued one.

Is there a priority stack in the C++ standard library ?

Unfortunately, the standard C++ provides only a priority_queue. It's an adapter.

There is no priority_stack. So you'd need to implement your own.

Hypothesis: I think that the reason is that priority stacks are something rather exotic. There are certainly valid use cases, but most uses of stacks is to implement in an iterative way some recursive algorithms, where priority would not make sense.

A quick implementation

If you don't know where to start, here a quick-and-dirty implementation: 

template<class T> 
class priority_stack {
    vector<T> stack;  
public:  
    bool empty() const { return stack.size()==0; } 
    void push(const T& x) { 
        stack.push_back(x); 
        for (int i=stack.size()-1; i!=0; i--)
            if ( (stack[i]<stack[i-1]))            // assuming priority is reflected in order of elements
                swap (stack[i-1],stack[i]);
    }  
    void pop() {
        if (! empty() )
            stack.resize(stack.size()-1);
    }
    T top() { 
        if (empty()) 
            throw; 
        return stack[stack.size()-1]; 
    }  
};

You can test it with the following data structure: 

struct data {
    int priority; 
    string message;  
    bool operator< (const data&a) const {  // order by priority
        return priority<a.priority;  
    } 
};

The online demo will show you the difference: 

Data to be pushed:(10,one) (10,two) (11,high) (12,very high) (10,three) 
Priority queue (FIFO): (12,very high) (11,high) (10,one) (10,two) (10,three) 
Priority stack (LIFO): (12,very high) (11,high) (10,three) (10,two) (10,one)

Note: if your data elements are quite large, it may be more interesting to base the structure on a list rather than a vector, and insert the pushed data at the right place, thus minimizing swaps.

Upvotes: 4

Freyja
Freyja

Reputation: 40794

In a regular queue or stack, the order of the elements' removal is dependent on the order of insertion (the same order for a queue, and reverse order for a stack).

In a priority queue, the order does not depend on the order of insertion, but on some custom "priority" assigned to each element. The priority queue gives elements with highest priority first.

For example: a priority queue (A 1) (B 3) (C 2) will give the elements in order B C A.

It's unclear what you mean by "priority stack", but if a stack is just a queue with the order of removal reversed, then the natural interpretation of "priority stack" is a priority queue where the order of removal is reversed, i.e. giving elements with lowest priority first. But this is the same as a priority queue where the priorities are reversed (typically by just negating them):

Example: a "priority stack" (A 1) (B 3) (C 2), which would give the order A C B, would be the same as the priority queue (A -1) (B -3) (C -2).

Upvotes: 0

Related Questions