정수값으로 데이터와 우선순위를 부여받았고 주어진 우선순위에 따라 이중연결리스트를 생성하여 결과를 출력하는 작업입니다.
큐는 먼저 삽입된 요소가 가장 먼저 제거되는 FIFO 데이터 구조입니다. 우선 순위 대기열은 우선 순위에 따라 요소를 삽입하거나 삭제할 수 있는 대기열 유형입니다. 큐, 스택 또는 연결 목록 데이터 구조를 사용하여 구현할 수 있습니다. 우선 순위 대기열은 다음 규칙에 따라 구현됩니다 -
- 우선순위가 가장 높은 데이터 또는 요소가 우선순위가 가장 낮은 데이터 또는 요소보다 먼저 실행됩니다.
- 두 요소가 순서대로 실행되는 것보다 우선순위가 같으면 목록에 추가됩니다.
우선 순위 대기열을 구현하기 위한 이중 연결 목록의 노드에는 세 부분이 포함됩니다. -
- 데이터 - 정수 값을 저장합니다.
- 다음 주소 - 다음 노드의 주소를 저장합니다.
- Previous Address - 이전 노드의 주소를 저장합니다.
- Priority - 정수 값인 우선 순위를 저장합니다. 0-10 범위에서 0은 가장 높은 우선순위를 나타내고 10은 가장 낮은 우선순위를 나타냅니다.
예시
입력 -
출력-
알고리즘
Start Step 1-> Declare a struct Node Declare info, priority Declare struct Node *prev, *next Step 2-> In function push(Node** fr, Node** rr, int n, int p) Set Node* news = (Node*)malloc(sizeof(Node)) Set news->info = n Set news->priority = p If *fr == NULL then, Set *fr = news Set *rr = news Set news->next = NULL Else If p <= (*fr)->priority then, Set news->next = *fr Set (*fr)->prev = news->next Set *fr = news Else If p > (*rr)->priority then, Set news->next = NULL Set (*rr)->next = news Set news->prev = (*rr)->next Set *rr = news Else Set Node* start = (*fr)->next Loop While start->priority > p Set start = start->next Set (start->prev)->next = news Set news->next = start->prev Set news->prev = (start->prev)->next Set start->prev = news->next Step 3-> In function int peek(Node *fr) Return fr->info Step 4-> In function bool isEmpty(Node *fr) Return (fr == NULL) Step 5-> In function int pop(Node** fr, Node** rr) Set Node* temp = *fr Set res = temp->info Set (*fr) = (*fr)->next free(temp) If *fr == NULL then, *rr = NULL Return res Step 6-> In function int main() Declare and assign Node *front = NULL, *rear = NULL Call function push(&front, &rear, 4, 3) Call function push(&front, &rear, 3, 2) Call function push(&front, &rear, 5, 2) Call function push(&front, &rear, 5, 7) Call function push(&front, &rear, 2, 6) Call function push(&front, &rear, 1, 4) Print the results obtained from calling the function pop(&front, &rear) Print the results obtained from calling the function peek(front) Stop함수 호출 결과 출력
예시
#include <bits/stdc++.h>
using namespace std;
//doubly linked list node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
//inserting a new Node
void push(Node** fr, Node** rr, int n, int p) {
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// if the linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
} else {
// If p is less than or equal front
// node's priority, then insert the node
// at front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
} else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
} else {
// Finding the position where we need to
// insert the new node.
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
//the last value
int peek(Node *fr) {
return fr->info;
}
bool isEmpty(Node *fr) {
return (fr == NULL);
}
int pop(Node** fr, Node** rr) {
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
// main function
int main() {
Node *front = NULL, *rear = NULL;
push(&front, &rear, 4, 3);
push(&front, &rear, 3, 2);
push(&front, &rear, 5, 2);
push(&front, &rear, 5, 7);
push(&front, &rear, 2, 6);
push(&front, &rear, 1, 4);
printf("%d\n", pop(&front, &rear));
printf("%d\n", peek(front));
return 0;
} 출력
5 3