[C++ STL] 3-3. 컨테이너 - 컨테이너 어댑터(container adapter)

공부 내용을 정리하는 목적 이므로 참고용으로만 읽어 주시기 바랍니다. 틀린 부분에 대한 지적은 감사합니다.

1. stack

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

문법)

#include <stack>

stack<타입> 스택명;

 

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

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

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

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

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

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

 

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

1 2 3 4 5 순서로 원소가 들어갔지만 나오는 것은 반대로 5 4 3 2 1의 순서로 LIFO의 메모리 구조를 확인할 수 있다. 

2. queue

큐(queue) 컨테이너는 deque 클래스를 기반으로 하며 queue 헤더파일을 include 해 사용한다. 큐의 메모리 구조는 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를 확인해보면

1 2 3 4 5의 순서로 들어가면 1 2 3 4 5의 순서로 나오는 FIFO의 구조를 확인할 수 있다.

3. priority_queue

우선순위 큐(priority queue)는 queue와 똑같은 구조를 같는다. 차이점은 vector기반으로 구성되어 있으며 맨 앞의 원소가 가장 먼저 저장된 원소가 아니라 가장 큰 값을 가지는 원소가 된다. queue와 마찬가지로 queue 헤더파일을 include 해서 사용한다.

 

문법)

#include <queue>

priority_queue<타입> 우선순위큐명;

 

5 30 100 2 77 의 순서로 원소를 집어넣었는데 우선순위큐는 100 77 30 5 2로 값이 큰 순서로 정렬되어 저장되어 있는 것을 확인할 수 있다.