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

// стек класса Key Stack {class Element {int prio, Key elem; }; MaxPriorityQueue <Элемент> q; int top_priority = 0; void push (Ключ x) {q.push (Элемент (top_priority ++, x)); } Key pop () {top_priority--; return q.pop (). elem; }};

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

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

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

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

algorithm,

11

Ответов: 5

20 принят

псевдокод:

Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

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

Поведение LIFO следует из того факта, что каждый новый элемент продвигается с приоритетом выше всех текущих элементов, поэтому он будет выскочить перед любым из них.

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

6

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

struct MyNode
{
  DataPacket dataPacket;
  int order;
};
2

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

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

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

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

}
1

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

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

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

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

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

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

A±
алгоритм,
Похожие вопросы
Яндекс.Метрика