[C++] STL - 컨테이너 어댑터(container adapter) [stack, queue]

stack

스택 컨테이너는 vector 클래스를 기반으로 한다. 스택의 메모리 구조는 LIFO(Last In First Out)를 따르는 자료구조이다. DFS(Depth First Search, 깊이 우선 탐색)나 특별한 알고리즘이 필요한 상황이 아니라 문제 상황을 구현하는 데 LIFO의 구조를 가지고 있다고 판단되는 문제를 풀 때 사용된다.

#include <stack>
stack<타입> 스택명;

스택의 멤버함수를 확인하면 다음과 같다.

s.size() : s의 원소의 개수를 반환(메모리 용량이 아님)

s.empty() : s가 비어있는지 확인, 비어있으면 true를 반환한다.

s.top() : s의 제일 위에 위치한(제일 나중에 저장된) 원소를 반환

s.push(x) : s에 x값을 저장

s.pop() :  s의 제일 위에 위치한(제일 나중에 저장된) 원소를 삭제(LIFO 이므로) 

 

간단한 예시로 스택의 구조와 멤버 함수를 확인해보면

 

queue

큐 컨테이너는 deque 클래스를 기반으로 한다. 큐의 메모리 구조는 FIFO(First In First Out)를 따른다. BFS(Breadth First Search, 너비우선탐색)나 특별한 알고리즘이 필요한 상황이 아니라 문제 상황을 구현하는데 FIFO의 구조를 가지고 있다고 판단되는 문제를 풀 때 사용된다.

#include <queue>
queue<타입> 큐이름;

큐의 멤버 함수는 다음과 같다.

q.size() : q의 원소의 개수를 반환(메모리 용량이 아님)

q.empty() : q가 비어있는지 확인, 비어있으면 true를 반환한다.

q.front() : q의 맨 앞의(가장 먼저 저장된) 원소를 반환한다.

q.back() : q의 맨뒤의(가장 나중에 저장된) 원소를 반환한다.

q.push(x) : q에 x값을 저장

q.pop() :  q의 맨 앞에 위치한(가장 먼저 저장된) 원소를 삭제(FIFO 이므로) 

 

간단한 예시를 통해 queue를 확인해보면

 

priority_queue

우선순위 큐(priority queue)는 queue와 똑같은 구조를 갖는다. 차이점은 vector 기반이며 오름차순이나 내림차순과 같은 정렬 기능이 있다.

#include <queue>
priority_queue<타입, 구현체, 비교연산자> 우선순위큐명;

비교연산자에는 less<자료형>, greater<자료형>이 있다. less는 내림차순으로, greater은 오름차순으로 출력된다. default는 오름차순이다.