[C++ 템플릿] 스택(stack), 큐(queue), 우선순위 큐(priority_queue)

1. 스택(stack)

https://www.cplusplus.com/reference/stack/stack/?kw=stack

stack - C++ Reference

 

 

Member functions

• empty: 스택이 비었는지 확인
• size: 스택에 들어있는 엘리먼트 수 = 스택 사이즈 반환
• top: 다음 엘리먼트 접근
• push: 새로운 엘리먼트 추가
• emplace: construct and insert element
• pop: 맨 위에 있는 엘리먼트 삭제
• swap: 내용물 바꿈

예시)

#include <iostream>
#include <stack>

using namespace std;

int main(void){
	stack<int> s;
	s.push(7);
	s.push(3);
	s.push(4);
	s.pop();
	s.push(6);
	
	while(!s.empty()){
		cout << s.top() << ' ';
		s.pop();
	}
	
	s.push(7);
	s.push(3);
	s.push(4);
	s.pop();
	s.emplace(6);
	
	stack<int> s1;
	s1.swap(s);
	while(!s1.empty()){
		cout << s1.top() << ' ';
		s1.pop();
	}
	

	return 0;
}

 

* emplace 와 push의 차이점:

기본적으로 integer 과 같은 단순한 변수를 사용할 때는 거의 차이가 없으나, 좀더 복잡한 구조체를 사용하는 stack의 경우에 emplace를 이용해 construct과 push의 기능을 할 수 있다.

간단하게 구분하자면 push는 매개변수로 요소 하나만 받을 수 있다. (이미 완성된 객체)

emplace는 알아서 constructor을 불러내서 construct하고 뒤에 넣는 듯..

 

참고) https://stackoverflow.com/questions/26198350/c-stacks-push-vs-emplace/26198609

 

2. 큐(queue)

https://www.cplusplus.com/reference/queue/queue/

 

큐는 First in first out 구조이다.

따라서 front가 가장 먼저 들어간 애고, back이 가장 뒤에 들어간 애다.

 

Member functions:

• empty
• size
• front: 가장 먼저 들어갔던, 큐의 맨 앞 element 반환
• back: 가장 나중에 들어간, 큐의 맨 뒤 element 반환
• push: 뒤에 새로운 element 추가
• emplace: 뒤에 새로운 element construct후 추가
• pop: next element(앞에 있는 것) 제거 (주의: return 하지 않는다!!!)
• swap

#include <iostream>
#include <queue>

using namespace std;

int main(void){

    queue<int> q;
    for(int i = 1; i<=5; i++){
        q.push(i);
    }

    cout << "size: " << q.size() << "\n";

    for(int i = 1; i<=3; i++){
        cout << q.front() << " "; // front를 추출 후에 제거해줘야
        q.pop(); // pop이 리턴하지 않는다. 
    }

    cout << endl;

    while(!q.empty()){
        cout << q.front() << " ";
        q.pop();
    }

    return 0;
}

priority queue

https://www.cplusplus.com/reference/queue/priority_queue/

 

 

선언:

priority_queue<데이터타입, vector<데이터타입>, compare>;

 

1. 데이터 타입(T): int든 뭐든 안에 들어갈 element의 변수 종류
2. vector<데이터타입>: 데이터 저장할 벡터 공간
3. compare: 두 개의 T 변수를 받아서 bool을 반환한다. 예를 들어 compare(a, b)라면, a가 먼저 들어가야하면 true를 반환하고, b가 우선이면 false를 반환한다. 이 compare는 function pointer일 수도 있고, 함수 객체일 수도 있다. 기본적으로 less<T>로 설정되어있다.

         * less<T> : a<b ( <연산자로 그냥 계산   해버림)

 

특징:

compare 이용해서, 특정 기준에 따라 정렬해서 저장한다는 점 -> heap properties를 유지한다

 

Member Functions:

• empty
• size
• top (*** queue와 다른 점, front, back이 아니라 top 사용함)
• push
• emplace
• pop
• swap(큐 객체)

#include <iostream>
#include <queue>

using namespace std;

struct compare{

	bool operator()(int a, int b){
	
		return a<b; //내림차순 	
	
	}

};

int main(void){
	
	priority_queue<int, vector<int>, compare> pq;
	
	pq.push(3);
	pq.push(2);
	pq.push(5);
	pq.push(7);
	pq.pop();
	pq.push(6);
	
	while(!pq.empty()){
		cout << pq.top() << ' ';
		pq.pop();
	}
	
	return 0;
}