Priority Queue 또는 Heap을 사용하여 스택을 구현하는 방법은 무엇입니까?

난이도 중급
자주 묻는 질문 아마존 광신자 포카이트
더미 우선 순위 대기열 스택조회수 44

구현 스택 우선의 도움으로 변발 또는 더미.

우선 순위 대기열 :

우선 순위 큐 데이터 구조는 우선 순위가 추가 된 큐 또는 스택 데이터 구조와 유사합니다. 모든 요소에는 우선 순위 번호가 부여됩니다. 결론적으로, 우선 순위가 높은 요소가 우선 순위가 낮은 요소보다 우선하거나 우선 제공됩니다.

예 :

우선 순위 대기열 = x (우선 순위 = 0), y (우선 순위 = 1), z (우선 순위 = 3). z 요소의 우선 순위가 가장 높으므로 먼저 게재됩니다.

Priority Queue 또는 Heap을 사용하여 스택을 구현하는 방법은 무엇입니까?

입력 

푸시 (1)
푸시 (2)
팝 ()

산출 

2

입력 
팝 ()

산출 

빈 스택

방법

스택의 작업은 LIFO (Last in Forst out) 시스템을 기반으로하며 우선 순위 대기열 우선 순위가 요소에 할당된다는 것을 알고 있습니다. 따라서 두 데이터 구조의 기능을 연결하기 위해 변수 저장소를 유지하거나 요소가 푸시되는 수를 계산할 수 있습니다. 우선 순위 대기열에서이 개수 변수를 키로 사용할 수 있습니다.

암호알고리즘

  1. 우선 순위 대기열을 사용하여 클래스 스택을 만듭니다. 대기열에 추가하여 변수 개수 = 0을 초기화합니다.
  2. 정수 값을 매개 변수로 받아들이는 함수 push ()를 만듭니다. 개수를 늘리고 우선 순위 대기열에서 개수와 요소 쌍을 푸시합니다.
  3. top () 함수를 생성하고 상위에 저장된 요소, 즉 우선 순위 큐의 상단에 저장된 쌍의 두 번째 부분을 반환합니다.
  4. 그 후 isEmpty () 함수를 만듭니다. 우선 순위 큐가 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
  5. 마찬가지로 pop () 함수를 만들고 대기열이 비어 있는지 확인하고“Empty Stack”을 인쇄합니다. 그렇지 않으면 개수를 줄이고 우선 순위 대기열의 맨 위를 팝합니다.
  6. 마지막으로 스택을 가로 지르고 스택이 비어 있지 않은 동안 상단을 인쇄하고 상단을 팝합니다.

우선 순위 큐 또는 힙을 사용하여 스택을 구현하는 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 쌍에 대한 우선 순위 대기열의 공간을 사용했기 때문입니다.

레퍼런스 1  참조 2

Translate »