개요
한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조
Queue의 성질
First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다.
rear에 삽입하고 front에서 삭제한다.
Queue
대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다.
Array 또는 Linked List로 구현할 수 있다.
Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다.
배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다.
아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.)
struct ArrayQueue {
int* que;
int maxSize, f, r, n;
ArrayQueue(int ms) {
maxSize = ms;
f = r = n = 0;
que = new int[maxSize];
for (int i = 0; i < maxSize; ++i) que[i] = 0;
}
void enqueue(int data);
int dequeue();
}
예외처리
빈 큐에 dequeue, front를 호출하거나 Array 기반 큐가 가득 찼을 때 enqueue를 호출하면 예외가 발생한다.
Implementation
아래는 이론에서 배운 내용을 구현한 코드이다.
#include <bits/stdc++.h>
using namespace std;
struct ArrayQueue {
int* que;
int maxSize;
int f, r, n;
ArrayQueue(int ms) {
maxSize = ms;
f = r = n = 0;
que = new int[maxSize];
for (int i = 0; i < maxSize; ++i) que[i] = 0;
}
int size() {
return n;
}
bool empty() {
return (n == 0);
}
int front() {
if (empty()) return -1;
return que[f];
}
int rear() {
if (empty()) return -1;
return que[(f + n - 1) % maxSize];
}
void enqueue(int e) {
if (n == maxSize) {
cout << "Full\n"; return;
}
que[r] = e;
r = (r + 1) % maxSize;
n++;
}
int dequeue() {
if (n == 0) return -1;
int ret = que[f];
f = (f + 1) % maxSize;
n--;
return ret;
}
};
struct Node {
int data;
Node* next;
Node(int e) {
data = e;
next = nullptr;
}
};
struct SLLQueue {
Node* head;
Node* tail;
int sz;
SLLQueue() {
head = nullptr;
tail = nullptr;
sz = 0;
}
bool empty() {
return (!head);
}
int size() {
return sz;
}
int front() {
if (empty()) return -1;
return head->data;
}
int rear() {
if (empty()) return -1;
return tail->data;
}
int dequeue() {
if (empty()) return -1;
Node* oldHead = head;
int ret = oldHead->data;
head = oldHead->next;
delete oldHead;
sz--;
if (!head) tail = nullptr;
return ret;
}
void enqueue(int e) {
Node* newNode = new Node(e);
if (tail) tail->next = newNode;
tail = newNode;
if (!head) head = newNode;
sz++;
}
};
int main() {
int S, TEST; cin >> S >> TEST;
ArrayQueue Q(S);
// SLLQueue Q;
while (TEST--) {
string oper; int p; cin >> oper;
if (oper == "enqueue") {
cin >> p; Q.enqueue(p);
}
if (oper == "dequeue") {
cout << Q.dequeue() << "\n";
}
if (oper == "size") {
cout << Q.size() << "\n";
}
if (oper == "isEmpty") {
cout << (Q.empty() ? 1 : 0) << "\n";
}
if (oper == "front") {
cout << Q.front() << "\n";
}
if (oper == "rear") {
cout << Q.rear() << "\n";
}
}
}
응용
카드2 boj.kr/2164
#include <bits/stdc++.h>
using namespace std;
struct ArrayQueue {
int* que;
int maxSize;
int f, r, n;
ArrayQueue(int ms) {
maxSize = ms;
f = r = n = 0;
que = new int[maxSize];
for (int i = 0; i < maxSize; ++i) que[i] = 0;
}
int size() {
return n;
}
bool empty() {
return (n == 0);
}
void enqueue(int e) {
if (n == maxSize) {
cout << "Full\n"; return;
}
que[r] = e;
r = (r + 1) % maxSize;
n++;
}
int dequeue() {
if (n == 0) return -1;
int ret = que[f];
f = (f + 1) % maxSize;
n--;
return ret;
}
};
int main() {
int n; cin >> n;
ArrayQueue Q(n);
for (int i = 1; i <= n; ++i) {
Q.enqueue(i);
}
while (1) {
if (Q.size() > 1) Q.dequeue();
if (Q.size() > 1) Q.enqueue(Q.dequeue());
if (Q.size() == 1) break;
}
cout << Q.dequeue();
}
'학과공부 > 자료구조' 카테고리의 다른 글
Heap (0) | 2020.12.03 |
---|---|
Priority Queue (0) | 2020.12.03 |
Stack (0) | 2020.10.26 |
Doubly Linked List와 Iterator (0) | 2020.10.26 |
Singly Linked List (0) | 2020.10.26 |
댓글