How to Implement stack using priority queue?

Question

How to Implement stack using priority queue?

Guys this is a Microsoft Interview Question for Software Engineer/Developer.I just can't make out the meaning of the question.So I goggled and found this:

Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved.

So what this question wants us to do.As stacks (Correct me if am wrong) are implicitly implemented as priority queues (priority being monotonically increasing as elements are added).

Does anybody can make out the meaning of this question.What we are supposed to do when such type of question is asked in an interview.

Answer 1

Here is the java implementation for this question.

import org.junit.Test;

import java.util.PriorityQueue;

import static org.junit.Assert.assertEquals;

public class StackHeap {
    @Test
    public void test() {
        Stack s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        assertEquals(3, s.pop());
        assertEquals(2, s.pop());
        s.push(4);
        s.push(5);
        assertEquals(5, s.pop());
        assertEquals(4, s.pop());
        assertEquals(1, s.pop());
    }

    class Stack {
        PriorityQueue<Node> pq = new PriorityQueue<>((Node x, Node y) -> Integer.compare(y.position, x.position));
        int position = -1;

        public void push(int data) {
            pq.add(new Node(data, ++position));
        }

        public int pop() {
            if (position == -1) {
                return Integer.MIN_VALUE;
            }
            position--;
            return pq.poll().data;
        }
    }

    class Node {
        int data;
        int position;
        public Node (int data, int position) {
            this.data = data;
            this.position = position;
        }
    }
}

Answer 2

Java Implementation with Time Complexity and Space Complexity:

Time Complexity: Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)), time complexity to insert the element.

Space Complexity: O(2k) for storing the elements in the Priority Queue and their associated ordering.

public class StackUsingHeap {

public static void main(String[] args) {

    Stack stack = new Stack();
    stack.push(10);
    stack.push(15);
    stack.push(20);

    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
}
}

class Stack {

    PriorityQueue<Node> pq = new PriorityQueue<>(new Node());
    static int position = -1;

    public void push(int data) {
      pq.add(new Node(data, ++position));
   }

   public int pop() {
     --position; // optional
     return pq.remove().data;
   }
  }

 class Node implements Comparator<Node> {

   int data;
   int position;

   public Node() {
   }

   public Node(int data, int position) {
    this.data = data;
    this.position = position;
  }

  @Override
  public int compare(Node n1, Node n2) {
    if (n1.position < n2.position)
        return 1;
    else if (n1.position > n2.position)
        return -1;
    return 0;
  }
 }

Answer 3

Here is the java implementation for this question.

public class StackPriorityQueue {

PriorityQueue<StackElement> queue = new PriorityQueue<>(10, new Comparator<StackElement>() {
    @Override
    public int compare(StackElement o1, StackElement o2) {
        return o2.key - o1.key;
    }
});

int order = 1;

public void push(int val){
    StackElement element = new StackElement(order++,val);
    queue.add(element);
}

public Integer pop(){
    if(queue.isEmpty()){
        System.out.println("Stack Underflow");
        return null;
    }
    return queue.poll().value;
}

public static void main(String... args){
    StackPriorityQueue q = new StackPriorityQueue();
    q.push(5);
    q.push(10);
    q.push(1);
    q.push(3);
    q.push(50);
    q.push(500);
    q.push(60);
    q.push(30);
    q.push(40);
    q.push(23);
    q.push(34);

    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());

   }

}

class StackElement {
  int key;
  int value;

  public StackElement(int key, int value) {
    this.key = key;
    this.value = value;
  }

}

Answer 4

You can implement a stack using a priority queue( say PQ) using min heap. You need one extra integer variable (say t). 't' will be used as the priority while inserting/deleting the elements from PQ.

You have to initialize t (say t=100) to some value at starting.

push(int element){
PQ.insert(t,element);
t--;           //decrease priority value(less priority will be popped first)
}

pop(){
return PQ.deleteMin();
}

peek(){
return PQ.min();
}

Note: You can also use system time to push elements according to the priority.

push(int element){
PQ.insert(-getTime(),element);   //negative of sys time(less priority will be popped first)
}

Answer 5

If you don't know what a priority queue is, ask. If you don't know what a stack is, ask. If you don't understand the question, ask. By now you should hopefully be able to work out that an adaptor like the following is required.

Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

    public:
      push(x) : q.add(x, counter++)
      pop() : q.remove()

Answer 6

Pseudocode:

// stack of Key
class Stack {
    class Element { int prio, Key elem; };
    MaxPriorityQueue<Element> q;
    int top_priority = 0;

    void push(Key x) { q.push(Element(top_priority++, x)); }
    Key pop() { top_priority--; return q.pop().elem; }
};

LIFO behavior follows from the fact that every new element is pushed with a priority higher than all the current elements, so it will be popped before any of them.

There are two ways to respond to this interview question. One is to explain in detail the structure above. The second is to briefly mention it, mumble something about O(lg n) and say you'd never implement a stack this way.

Answer 7

Such questions require you to think a bit deep( though not so deep with this one).

The explanation for this answer is, instead of inserting each element with their values being the key, you should wrap them into a Object and assign order as an attribute. You should make this Order as the key.

Sample C Code:

struct MyNode
{
  DataPacket dataPacket;
  int order;
};