Как реализовать стек с использованием очереди приоритетов?

Как реализовать стек с использованием очереди приоритетов?

Ребята, это вопрос о Microsoft для разработчиков программного обеспечения/разработчика. Я просто не могу разобрать смысл вопроса. Поэтому я изучил и нашел это:

Стеки и очереди могут быть смоделированы как отдельные типы очередей приоритетов. В стеке приоритет каждого вставленного элемента монотонно возрастает; таким образом, последний вставленный элемент всегда будет первым извлеченным.

Итак, что этот вопрос требует от нас. Как стеки (Исправить меня, если не так) неявно реализованы как очереди приоритетов (приоритет монотонно возрастает по мере добавления элементов).

Кто-нибудь может понять смысл этого вопроса. Что мы должны делать, когда в интервью задается такой тип вопроса.

Ответ 1

псевдокод:

// 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 следует из того факта, что каждый новый элемент продвигается с приоритетом выше всех текущих элементов, поэтому он будет вытолкнут перед любым из них.

Есть два способа ответить на этот вопрос интервью. Один из них - подробно объяснить структуру выше. Во-вторых, кратко упомянуть об этом, пробормотать что-то о O (lg n) и сказать, что вы никогда не реализуете стек таким образом.

Ответ 2

Если вы не знаете, что такое приоритетная очередь, спросите. Если вы не знаете, что такое стек, спросите. Если вы не понимаете вопрос, спросите. К настоящему моменту вы, надеюсь, сможете решить, что требуется адаптер, такой как следующий.

Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

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

Ответ 3

Такие вопросы требуют, чтобы вы подумали немного глубоко (хотя и не настолько глубоко с этим).

Объяснение этого ответа заключается в том, что вместо того, чтобы вставлять каждый элемент со своими значениями в качестве ключа, вы должны обернуть их в Object и назначить order как атрибут. Вы должны сделать этот заказ в качестве ключа.

Пример кода C:

struct MyNode
{
  DataPacket dataPacket;
  int order;
};

Ответ 4

Вот реализация java для этого вопроса.

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;
  }

}

Ответ 5

Вы можете реализовать стек, используя приоритетную очередь (скажем, PQ), используя минимальную кучу. Вам понадобится одна дополнительная целочисленная переменная (например, t). 't' будет использоваться в качестве приоритета при вставке/удалении элементов из PQ.

Вы должны инициализировать t (например, t = 100) до некоторого значения при запуске.

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();
}

Примечание. Вы также можете использовать системное время для ввода элементов в соответствии с приоритетом.

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