C++ STL - stack, queue, priority_queue, deque

C++ STL

• Standard Template Library의 약자로 효율적이고 안정적인 라이브러리로 코딩 테스트에서 유용하게 활용할 수 있다.

스택(stack)

• 컴퓨터의 기본 아키텍쳐
• LIFO(Last In First Out) 구조로 차곡차곡 박스를 아래부터 쌓아두고 위에서부터 꺼내는 방식으로 재귀함수의 호출 방식과 같은 개념이다.

#include <stack>
// 변수 선언 방법 : stack<type> name;
stack<int> s;

기본함수

• push(element) : 스택에 element를 쌓는 함수
• pop(): 스택 맨 위 요소를 제거
• top(): 스택 맨 위 요소를 반환
• empty(): 스택이 비어있으면 true, 비어있지 않으면 false 반환
• size(): 현재 스택에 저장된 데이터의 크기를 반환

큐(queue)

• FIFO(First In First Out) 구조로 먼저 들어온 데이터를 먼저 처리하여 내보내는 방식이다.

#include <queue>
// 변수 선언 방법 : queue<type> name;
queue<char> q;

기본함수

• push(element) : element를 큐 맨 뒤에 삽입
• pop(): 큐의 맨 앞 요소를 제거
• front(): 큐의 맨 앞 요소를 반환
• back(): 큐의 맨 뒤 요소를 반환
• empty(): 큐가 비어있으면 true, 비어있지 않으면 false 반환
• size(): 현재 큐에 저장된 데이터의 크기를 반환

우선순위 큐(priority_queue)

• 큐의 한 종류로 우선순위에 따라 정렬되어 정렬된 큐의 맨 앞 요소부터 데이터를 처리하는 자료구조이다.
• 내가 원하는 비교함수는 연산자 오버로딩으로 구현한다.

#include <queue>
/* 변수 선언 방법 
priority_queue<type, container, 비교함수> name;
- 비교함수에 따라 정렬하는 우선순위 큐 선언
- 오름차순 비교함수로는 greater<type> */
priority_queue<int, vector<int>, greater<int>> pq1;

/*
priority_queue<type> name;
- 선언한 자료형 변수를 내림차순으로 정렬하는 우선순위 큐 선언 */
priority_queue<int> pq2;

기본함수

• push(element): 우선순위 큐에 element를 삽입. 비교함수에 따라 내부적으로 자동 정렬
• pop(): 우선순위 큐의 맨 앞 요소를 제거
• top(): 우선순위 큐의 맨 앞 요소를 반환
• empty(): 우선순위 큐가 비어있으면 true, 비어있지 않으면 false 반환
• size(): 현재 우선순위 큐에 저장된 데이터의 크기를 반환

덱(deque)

• Double Ended Queue로 이름과 같이 두 개의 큐를 가진다는 의미로 앞뒤로 데이터 삽입과 삭제가 가능하다.
• 스택과 큐의 역할을 모두 할 수 있다.
• 인덱스를 이용한 접근이 가능하다.

#include <deque>
// 변수 선언 방법 : deque<type> name;
deque<int> dq;

기본함수

• push_front(element): element를 덱의 맨 앞에 삽입
• push_back(element): element를 덱의 맨 뒤에 삽입
• pop_front(): 덱의 맨 앞 요소를 제거
• pop_back(): 덱의 맨 뒤 요소를 제거
• front(): 덱의 맨 앞 요소를 반환
• back(): 덱의 맨 뒤 요소를 반환
• empty(): 덱이 비어있으면 true, 비어있지 않으면 false 반환
• size(): 현재 덱에 저장된 데이터의 크기를 반환