[C++] STL stack, queue, priority queue

1. STL stack

: Last In First Out(LIFO)의 대표적인 케이스. 먼저 들어간 데이터는 다른 데이터가 다 빠져나오기 전까진 빼낼 수 없으며, 가장 먼저 뺄 수 있는 데이터는 가장 마지막에 들어간 데이터가 됨.


장점

1. 구현이 상대적으로 쉬움
2. 저장 공간이 상대적으로 적게 사용됨
3. LIFO 구조로 탐색 대상이 최근에 push된 경우 금방 찾을 수 있음


단점

1. LIFO 구조이기 때문에 오히려 탐색 대상을 찾는데 오랜 시간이 걸릴 수 있음
2. 1번과 연결 되는 내용으로 자칫하면 탐색 대상을 끝까지 찾지 못하게 될 수 있음


#include <stack>
stack<int> s;


s.size() : stack 크기 반환
s.empty() : stack이 비었는지 아닌지 확인

s.push(data) : stack에 data를 넣어줌
s.pop() : stack의 마지막 data를 빼줌

s.top() : stack의 top에 있는 data 반환



2. STL queue

: First In First Out(FIFO)의 대표적인 케이스. stack과는 다르게 pop할 수 있는 건 가장 먼저 들어간 데이터가 되며 push를 하게 되면 stack 과 마찬가지로 가장 윗부분에 데이터가 저장된다.


장점

1. 데이터가 들어간 순서대로 정리되기 때문에 정리에 유용함
2. 스택과 달리 '앞, 뒤'라는 개념이 생김


단점

1. 스택과 마찬가지로 탐색기간이 길어질 수 있는 한계를 해결할 수는 없음




#include <queue>
queue<int> q;


q.size() : queue 크기 반환
q.empty() : queue가 비었는지 아닌지 확인

q.push(data) : queue의 마지막에 data를 넣어줌
q.pop() : queue의 가장 앞에 있는 data를 빼줌

q.front() : queue의 제일 앞에 있는 원소 반환
q.back() : queue의 제일 뒤에 있는 원소 반환

3. STL priority queue

: 일반 queue에 '우선순위'라는 개념이 도입된 구조. 일반 queue는 FIFO 구조였지만 priority queue(이하 pq)는 가장 먼저 pop 되는 건 가장 큰 데이터거나 가장 작은 데이터. 작은 데이터 순으로 빠지면 Min heap, 가장 큰 데이터 순으로 빠지면 Max heap 구조라고 한다. (기본적으로 Max heap)

#include <queue>

priority_queue<int> pq;

장점

1. 힙이 완전 이진 트리 구조를 가지게 되며, pq 또한 힙 구조. 부모 노드는 자식 노드보다 우선순위가 크다.

2. 시간 복잡도가 O(nlogn)까지 가능

3. 우선순위를 프로그래머가 직접 정할 수도 있음

단점 

1. 데이터들의 최대, 최소만 알 수 없다는 한계 (사실상 단점이라고 보기도 힘듬)

2. 크기 순으로 정렬되어 있다는 것만 빼면 일반 큐와 크게 다르지 않음 (이것도 단점은 아닌듯)

#include <queue>

priority_queue<int> pq;

pq.size() : pq 크기 반환
pq.empty() : pq가 비었는지 아닌지 확인

pq.push(data) : pq의 마지막에 data를 넣어줌
pq.pop() : pq의 가장 앞에 있는 data를 빼줌

pq.top() : 가장 마지막에 있는 데이터 반환

1) 우선순위큐 우선순위 정하기

#include <queue> 
priority_queue<int> pq;

//Max_Heap
priority_queue<int, vector<int>, less<int> > pq;

//Min_Heap
priority_queue<int, vector<int>, greater<int> > pq;

2) 우선순위큐 응용

#include <queue> 
priority_queue<pair<int, int> > pq;