자료구조 - 중간값 삭제가 가능한 큐
22 Aug 2020 | 알고리즘 자료구조한정된 메모리에서 오래된 데이터는 삭제하고 최신 데이터만 유지해야하는 경우가 있습니다. 이럴 때 원형 큐(circular queue)를 사용하면 쉽게 구현할 수 있습니다. 하지만 오래된 데이터가 아닌 중간에 들어온 데이터를 삭제해야 하는 경우에는 추가 작업을 해줘야 합니다. 여기서 추가 작업이란 삭제 후 다시 큐를 연결해주는 것입니다. 배열을 이용하여 큐를 이용한 경우 남아 있는 데이터를 앞으로 당겨서 삭제된 부분을 다시 채워줘야 합니다.
큐의 맨 앞에 있는 데이터를 삭제하는 경우 Head의 위치가 변경됩니다. 이럴 때 Head와 Tail의 위치를 모두 재조정해야 하는데, 삭제된 데이터 수만큼 Tail의 위치를 당겨주고, 변경된 Tail에서 데이터의 수만큼 이동간 위치가 Head값이 됩니다. 삭제된 데이터 수를 가지고 Size, Head, Tail, 배열의 데이터 위치를 재배치 하는 것이 중요 포인트입니다.
또 주의해야할 점은 전체 큐 배열의 사이즈는 저장할 데이터의 수보다 하나 더 크게 잡아서 끝에 버퍼를 둬야 합니다. 만약 큐 배열 사이즈만큼 모두 입력을 받으면 Head의 위치와 Tail의 위치가 같아지기 때문에, 데이터가 하나도 들어오지 않았을 때와 같이 취급하는 경우가 발생하게 됩니다.
중간값 삭제가 가능한 배열로 된 큐
#include <iostream>
using namespace std;
#define QUEUE_SIZE 5
int queue[QUEUE_SIZE];
int cur_size;
int head;
int tail;
bool is_full() {
return ((tail + 1) % QUEUE_SIZE) == head;
}
void enqueue(int data) {
queue[tail] = data;
tail = (tail + 1) % QUEUE_SIZE;
cur_size++;
}
int dequeue() {
int ret = queue[head];
queue[head] = 0;
head = (head + 1) % QUEUE_SIZE;
cur_size--;
return ret;
}
void del_data(int data) {
cout << "Del " << data << endl;
// 삭제된 데이터 수
int del_count = 0;
for (int now = head; now != tail; now = (now + 1) % QUEUE_SIZE) {
// 찾은 경우
if (queue[now] == data) {
queue[now] = 0;
del_count++;
// 앞에 삭제된게 있는 경우
} else if (del_count > 0){
// target 위치 계산
int target = now - del_count;
if (target < 0) target += QUEUE_SIZE;
// target 바로 앞까지 이동
queue[target] = queue[now];
queue[now] = 0;
}
}
// cur_size 조정
cur_size -= del_count;
// tail, head 위치 재배치
tail = tail - del_count;
if (tail < 0) tail += QUEUE_SIZE;
head = tail - cur_size;
if (head < 0) head += QUEUE_SIZE;
}
void add_data(int data) {
cout << "Add " << data << endl;
if (is_full()) {
dequeue();
}
enqueue(data);
}
void print_queue() {
cout << "head: " << head << ", tail: " << tail << endl;
cout << " -> ";
for (int i = 0; i < QUEUE_SIZE; i++) {
cout << queue[i] << " ";
}
cout << endl;
cout << endl;
}
메인 함수
int main() {
// 초기화
head = 0;
tail = 0;
add_data(1);
print_queue();
del_data(1);
print_queue();
add_data(2);
print_queue();
add_data(3);
print_queue();
add_data(4);
print_queue();
add_data(5);
print_queue();
del_data(1);
print_queue();
del_data(2);
print_queue();
add_data(6);
print_queue();
add_data(7);
print_queue();
add_data(8);
print_queue();
add_data(8);
print_queue();
del_data(1);
print_queue();
del_data(8);
print_queue();
add_data(5);
print_queue();
del_data(5);
print_queue();
del_data(7);
print_queue();
return 0;
}
출력
Add 1
head: 0, tail: 1
-> 1 0 0 0 0
Del 1
head: 0, tail: 0
-> 0 0 0 0 0
Add 2
head: 0, tail: 1
-> 2 0 0 0 0
Add 3
head: 0, tail: 2
-> 2 3 0 0 0
Add 4
head: 0, tail: 3
-> 2 3 4 0 0
Add 5
head: 0, tail: 4
-> 2 3 4 5 0
Del 1
head: 0, tail: 4
-> 2 3 4 5 0
Del 2
head: 0, tail: 3
-> 3 4 5 0 0
Add 6
head: 0, tail: 4
-> 3 4 5 6 0
Add 7
head: 1, tail: 0
-> 0 4 5 6 7
Add 8
head: 2, tail: 1
-> 8 0 5 6 7
Add 8
head: 3, tail: 2
-> 8 8 0 6 7
Del 1
head: 3, tail: 2
-> 8 8 0 6 7
Del 8
head: 3, tail: 0
-> 0 0 0 6 7
Add 5
head: 3, tail: 1
-> 5 0 0 6 7
Del 5
head: 3, tail: 0
-> 0 0 0 6 7
Del 7
head: 3, tail: 4
-> 0 0 0 6 0
Comments