문제 |
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
코드 1 (std::queue) |
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
void push(int num) {
q.emplace(num);
}
bool empty() {
return q.empty();
}
int pop() {
if (empty()) return -1;
int res = q.front();
q.pop();
return res;
}
int size() {
return (int) q.size();
}
int front() {
if (empty()) return -1;
return q.front();
}
int back() {
if (empty()) return -1;
return q.back();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
while (n--) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int num;
cin >> num;
push(num);
} else if (cmd == "pop") {
cout << pop() << '\n';
} else if (cmd == "size") {
cout << size() << '\n';
} else if (cmd == "empty") {
cout << empty() << '\n';
} else if (cmd == "front") {
cout << front() << '\n';
} else if (cmd == "back") {
cout << back() << '\n';
}
}
return 0;
}
설명 |
queue 헤더의 std::queue를 이용해 손쉽게 해결할 수 있다.
코드 2 (직접 구현) |
#include <iostream>
using namespace std;
struct LinkedList {
struct Node {
int data;
Node *next;
explicit Node(int data) : data(data), next(nullptr) {}
};
Node *head = nullptr;
Node *tail = nullptr;
[[nodiscard]] bool isEmpty() const {
return !head;
}
void addBack(int data) {
Node *pNode = new Node(data);
if (isEmpty()) {
head = pNode;
tail = pNode;
} else {
tail->next = pNode;
tail = pNode;
}
}
void deleteFront() {
if (head == tail) {
head = nullptr;
tail = nullptr;
} else {
head = head->next;
}
}
};
struct Queue : LinkedList {
void push(int num) {
addBack(num);
}
bool empty() {
return isEmpty();
}
int front() {
if (empty()) return -1;
return head->data;
}
int back() {
if (empty()) return -1;
return tail->data;
}
int pop() {
if (empty()) return -1;
int res = front();
deleteFront();
return res;
}
int size() {
int cnt = 0;
Node *pNode = head;
while (pNode) {
cnt++;
pNode = pNode->next;
}
return cnt;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Queue q;
int n;
cin >> n;
while (n--) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int num;
cin >> num;
q.push(num);
} else if (cmd == "pop") {
cout << q.pop() << '\n';
} else if (cmd == "size") {
cout << q.size() << '\n';
} else if (cmd == "empty") {
cout << q.empty() << '\n';
} else if (cmd == "front") {
cout << q.front() << '\n';
} else if (cmd == "back") {
cout << q.back() << '\n';
}
}
return 0;
}
설명 |
Linked List를 구현한 후 상속하여 Queue를 구현하였다.
'PS > BOJ' 카테고리의 다른 글
[C++] BOJ (백준) 10989 : 수 정렬하기 3 (0) | 2023.03.05 |
---|---|
[C++] BOJ (백준) 10866 : 덱 (0) | 2023.03.05 |
[C++] BOJ (백준) 10828 : 스택 (0) | 2023.03.05 |
[C++] BOJ (백준) 10816 : 숫자 카드 2 (0) | 2023.03.05 |
[C++] BOJ (백준) 10814 : 나이순 정렬 (0) | 2023.03.05 |