Circular Queue

Circular Queue

Queue의 front에서 추가, 삭제시 O(N)이 걸린다는 것을 보완합니다.

 

 

 

1) List(연결 리스트) 이용해서 구현

#include <cstdio>
#include <list>

using namespace std;

list<int>::iterator circularNext(list<int> &l, list<int>::iterator &it) {
	return next(it) == l.end() ? l.begin() : next(it);
}

list<int>::iterator circularPrev(list<int> &l, list<int>::iterator &it) {
	return it == l.begin() ? --l.end() : prev(it);
}


list<int> circle;

int main() {

	for (int i = 1; i < 6; ++i) {
		circle.emplace_back(i);
	}

	list<int>::iterator it = circle.begin();
	printf("%d\n", *it);
	printf("%d\n", *circularNext(circle, it));
	printf("%d\n", *circularPrev(circle, it));
    
    return 0;
}

 

Size를 알기 위해서는, head부터 모든 포인터를 일일이 다 탐색하여 얻는 수 밖에 없어서 O(N)이 걸립니다.

 

 

2) Array(배열) 이용해서 구현

 

head와 tail을 설정하고, modulus 연산을 이용하여 구현합니다.

 

 

 

 

 

* 두 경우 모두 탐색, (임의 장소에) 추가, 삭제시 시간복잡도는 O(N)입니다.