[C++] Stack, Queue, 우선순위 큐에 구조체 넣는 법

Stack

LIFO(Last In First Out) 속성을 가진 자료구조이다. 책 쌓기처럼 가장 마지막에 push된 데이터가 pop된다. front에서 push, pop 모두 일어나며 벡터와 비슷한 메서드를 사용한다.

---

Queue

FIFO(First In First Out) 속성을 가진 자료구조이다. 줄 서기처럼 먼저 push된 데이터가 pop된다. front에서 pop, back에서 push가 일어나며 벡터와 비슷한 메서드를 사용한다.

---

Priority_queue

 priority_queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 우선순위 큐 자료구조이다. priority_queue<자료형, container, compare>로 정의한다. container는 디폴트로 vector을 사용한다. deque로 사용할 수 있다. compare는 디폴트로 less를 사용하며 이는 내림차순을 뜻한다. greater을 통해 오름차순으로 변경할 수 있다.

우선순위 큐에 구조체를 넣어보자. priority_queue<T, vector<T>, compare> pq;와 같이 많이 사용하며 T는 구조체이다. 예를 들어 좌표계를 뜻하는 coo 구조체가 있다고 생각해보자.

typedef struct coo{
	int x, y;
}

 

 이 때 새로운 compare을 사용하기 위해 compare 구조체를 만들고 그 구조체에 대해 ()연산자가 비교 연산자로 작용하게끔 만들자.

typedef struct compare{
	bool operator()(coo &I, coo &C){
  		if(I.x != C.x) return I.x < C.x;
  		return I.y < C.y;
	}
}

 

 이제 compare구조체에서 ()연산자를 사용하면 coo구조체의 비교가 가능하다. 따라서 priority_queue <coo, vector<coo>, compare> pq;와 같이 사용할 수 있다. 나머지 메서드들은 벡터와 비슷한 메서드를 사용하고 있다.