우선 순위 대기열 :
우선 순위 큐 데이터 구조는 우선 순위가 추가 된 큐 또는 스택 데이터 구조와 유사합니다. 모든 요소에는 우선 순위 번호가 부여됩니다. 결론적으로, 우선 순위가 높은 요소가 우선 순위가 낮은 요소보다 우선하거나 우선 제공됩니다.
예 :
우선 순위 대기열 = x (우선 순위 = 0), y (우선 순위 = 1), z (우선 순위 = 3). z 요소의 우선 순위가 가장 높으므로 먼저 게재됩니다.
차례
예
입력
푸시 (1)
푸시 (2)
팝 ()
산출
2
입력
팝 ()
산출
빈 스택
방법
스택의 작업은 LIFO (Last in Forst out) 시스템을 기반으로하며 우선 순위 대기열 우선 순위가 요소에 할당된다는 것을 알고 있습니다. 따라서 두 데이터 구조의 기능을 연결하기 위해 변수 저장소를 유지하거나 요소가 푸시되는 수를 계산할 수 있습니다. 우선 순위 대기열에서이 개수 변수를 키로 사용할 수 있습니다.
암호알고리즘
- 우선 순위 대기열을 사용하여 클래스 스택을 만듭니다. 대기열에 추가하여 변수 개수 = 0을 초기화합니다.
- 정수 값을 매개 변수로 받아들이는 함수 push ()를 만듭니다. 개수를 늘리고 우선 순위 대기열에서 개수와 요소 쌍을 푸시합니다.
- top () 함수를 생성하고 상위에 저장된 요소, 즉 우선 순위 큐의 상단에 저장된 쌍의 두 번째 부분을 반환합니다.
- 그 후 isEmpty () 함수를 만듭니다. 우선 순위 큐가 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- 마찬가지로 pop () 함수를 만들고 대기열이 비어 있는지 확인하고“Empty Stack”을 인쇄합니다. 그렇지 않으면 개수를 줄이고 우선 순위 대기열의 맨 위를 팝합니다.
- 마지막으로 스택을 가로 지르고 스택이 비어 있지 않은 동안 상단을 인쇄하고 상단을 팝합니다.
우선 순위 큐 또는 힙을 사용하여 스택을 구현하는 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
class Stack{
int count;
priority_queue<pair<int, int> > pq;
public:
Stack():count(0){}
void push(int n);
void pop();
int top();
bool isEmpty();
};
void Stack::push(int n){
count++;
pq.push(pi(count, n));
}
void Stack::pop(){
if(pq.empty()){
cout<<"Empty Stack!!!";
}
count--;
pq.pop();
}
int Stack::top(){
pi temp=pq.top();
return temp.second;
}
bool Stack::isEmpty(){
return pq.empty();
}
int main(){
Stack* s=new Stack();
s->push(1);
s->push(2);
s->push(3);
while(!s->isEmpty()){
cout<<s->top()<<" ";
s->pop();
}
}
3 2 1
우선 순위 큐 또는 힙을 사용하여 스택을 구현하는 Java 프로그램
import java.util.*;
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("Empty Stack");
return null;
}
return queue.poll().value;
}
public static void main(String[] args){
StackPriorityQueue q = new StackPriorityQueue();
q.push(1);
q.push(2);
q.push(3);
System.out.print(q.pop()+" ");
System.out.print(q.pop()+" ");
System.out.print(q.pop()+" ");
}
}
class StackElement {
int key;
int value;
public StackElement(int key, int value) {
this.key = key;
this.value = value;
}
}
3 2 1
복잡성 분석
시간 복잡성 : O (k) 여기서 k는 요소의 수입니다.
보조 공간 : O (k) k 쌍에 대한 우선 순위 대기열의 공간을 사용했기 때문입니다.
