Как реализовать стек, используя очередь приоритетов?

Question

Как реализовать стек, используя очередь приоритетов?

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

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

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

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

Answer 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 ) и сказать, что вы никогда не реализуете стек таким образом.

Answer 2

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

Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

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

Answer 3

Вот реализация 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;
  }

}

Answer 4

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

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

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

struct MyNode
{
  DataPacket dataPacket;
  int order;
};

Answer 5

Вы можете реализовать стек, используя приоритетную очередь (скажем, PQ) , используя min heap . Вам нужна одна дополнительная целочисленная переменная (скажем, 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)
}