[C++#5-3] queue

이 게시물은 다음 링크를 참조하여 학습했습니다.

[C++][STL] Queue 기본 사용법 및 예제

[C++] deque container 정리 및 사용법

[C++ STL] Priority_queue 사용법

 

1. queue?

queue는 FIFO(First-In-First-Out)의 형태를 갖는 자료구조이다.

쉽게 생각하면 한 방향으로 갈 수 있는 터널을 생각하면 된다. 

들어갈때는 뒤에서 들어가고, 나올때는 앞에서 나오면서 가장 먼저 들어간 값이 가장 먼저 나온다.

queue를 사용하려면 아래처럼 사용하면 된다.

#include <queue>
 
queue<int> Q;

 

1-1. 멤버함수

queue의 멤버함수에 대한 자세한 설명은 아래 링크에서 확인할 수 있다.

std::queue - cppreference.com

이번 게시물에서는 내가 자주 사용하는 멤버함수만 정리했다.

함수	설명
void push(value);	큐에 value를 넣어준다.
void pop();	큐에서 제일 앞단의 value 하나를 제거한다.
value front();	큐에서 제일 앞단의 value를 반환한다.
int size();	큐의 사이즈를 반환한다.
bool empty();	큐가 비어있는지 확인한다.

 

2. deque?

deque는 Double ended queue의 약자로, 한국말로 해석하면 "양방향 큐"이다.

큐의 삽입/삭제가 한방향만 가능한것에 반해, 덱은 양방향 삽입/삭제가 가능하다.

또한, 큐와 스택에서 불가능했던 at(), []를 사용한 인덱스 참조도 가능하다.

vector를 사용할 바에 deque를 사용하는게 낫지 않냐 할수도 있겠지만, 자료를 뒤에서만 삽입하고 단순히 배열의 용도로만 사용할꺼면 vector를 사용하는게 낫다고 한다.

이 내용에 대해서는 따로 정리를 하려한다.

deque를 사용하려면 아래처럼 사용하면 된다.

#include <deque>
 
deque<int> DQ;

 

2-1. 멤버함수

deque의 멤버함수에 대한 자세한 설명은 아래 링크에서 확인할 수 있다.

deque - C++ Reference

이번 게시물에서는 내가 자주 사용하는 멤버함수만 정리했다.

함수	설명
iterator begin();	덱의 첫번째 값을 가리키는 반복자
iterator end();	덱의 마지막 값의 다음을 가리키는 반복자
int size();	덱의 사이즈를 반환한다.
value at(int position);	덱의 position 위치의 값을 반환한다. 유효한 값인지 판별 하기 때문에 안정적이지만 시간복잡도 ↑
operator [int position];	덱의 position위치의 값을 반환한다. 값 판별이 없기때문에 시간복잡도 ↓, 사용자가 값 판별 해줘야 함
void erase(iterator position);	덱의 position에 해당하는 위치의 값을 삭제한다.
void push_back(value);	덱의 맨 뒤에 value를 넣어준다.
void push_front(value);	덱의 맨 앞에 value를 넣어준다.
void pop_back();	덱의 맨 뒤 값을 삭제한다.
void pop_front();	덱의 맨 앞 값을 삭제한다.
value front();	덱의 첫번째 value를 반환한다.
value back();	덱의 마지막 value를 반환한다.
bool empty();	덱이 비어있는지 확인한다.

 

3. priority_queue?

priority_queue는 우리말로 하면 "우선순위 큐"이다. 

우선순위 큐를 사용하면 모든 원소중에 가장 큰/작은 값이 top()에 위치하도록 할 수 있다.

내부적으로는 벡터로 설계되어 있는데, Heap자료구조를 프로그램적으로 사용하는 것이라 생각하면 이해가 쉽다.

priority_queue는 아래처럼 사용한다!

#include <queue>
 
priority_queue<int> PQ;    // 기본( 큰 값 기준 정렬)
 
priority_queue<int, vector<int>, less<int> > PQ;        // 큰 값 기준 정렬
priority_queue<int, vector<int>, greater<int> > PQ;        // 작은 값 기준 정렬

 

3-1. 멤버함수

priority_queue의 멤버함수에 대한 자세한 설명은 아래 링크에서 확인할 수 있다.

std::priority_queue - cppreference.com

이번 게시물에서는 내가 자주 사용하는 멤버함수만 정리했다.

함수	설명
void push(value);	우선순위 큐에 value를 삽입한다.
void pop();	우선순위 큐에서 top()의 원소를 제거한다.
value top();	우선순위 큐에서 최상단의 value를 반환한다.
int size();	우선순위 큐의 사이즈를 반환한다.
bool empty();	우선순위 큐가 비어있는지 확인한다.