[C++] Circular Queue 구현
Circular Queue로 푸는 문제 (백준 11866) 를 풀면서 구현했다.
// 6-2. 요세푸스 문제 0 https://www.acmicpc.net/problem/11866
// circular queue로 푸는 문제.
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
Node(int value, Node * next) {
this->value = value;
this->next = next;
}
int value;
Node * next;
};
Node * head = NULL;
Node * tail = NULL;
bool isEmpty() {
return head == NULL && tail == NULL;
}
void push(int value) {
Node * newNode = new Node(value, head);
if(isEmpty()) {
head = tail = newNode;
head->next = tail;
tail->next = head;
return;
}
if(head == tail) {
head->next = newNode;
} else {
tail->next = newNode;
}
tail = newNode;
}
int pop(int idx = 0) {
if(isEmpty()) return -1;
if(head == tail) {
int ret = head->value;
free(head);
head = tail = NULL;
return ret;
}
while(idx--) {
tail = head; // ( == tail->next)
head = head->next;
}
int ret = head->value;
Node * ptr = head;
tail->next = head->next;
head = head->next;
free(ptr);
return ret;
}
int main() {
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
push(i);
vector<int> ans;
while(!isEmpty()) {
int v = pop(k - 1);
ans.push_back(v);
}
cout << '<';
for(int i = 0; i < ans.size(); i++) {
cout << ans[i];
if(i != (int)ans.size() - 1) cout << ", ";
}
cout << '>';
return 0;
}
Author And Source
이 문제에 관하여([C++] Circular Queue 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyeonseop/C-Circular-Queue-구현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)