[C++/STL]queue, stack

1. queue

1) 정의

FIFO(First In First Out, 선입선출) 자료구조

2) 용도

① BFS(Breadth First Search, 너비우선탐색)

② 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 FIFO의 구조를 가지는 문제를 풀 때

(Ex. 다리에 올라갈 수 있는 최대 하중과 각 트럭의 무게가 주어질 때, 모든 트럭이 다리를 지나가는 데 걸리는 최소 시간을 구하는 문제. 다리에 먼저 올라간 트럭이 먼저 나오게 되기 때문에 queue를 이용해 구현하면 풀 수 있다.)

3) 사용법

queue를 사용하기 위해서는 <queue>를 include 해야 합니다.

편의상 멤버 함수의 적용 대상이 되는 queue를 q라고 부르도록 하겠습니다.

멤버 함수	기능
q.size()	q의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴
q.empty()	q의 사이즈가 0인지 아닌지를 확인
q.front()	q에 가장 먼저 들어간 원소를 리턴
q.back()	q에 가장 나중에 들어간 원소를 리턴
q.push(val)	q의 위(뒤에 val 추가
q.pop()	q에 가장 먼저 들어간 원소를 삭제

<front와 back>

<push와 pop>

4) 예제

queue<pair<int,int>> q;
 
q.push(make_pair(1,2));
 
int a = 2, b = 3;
pair<int,int> p = make_pair(a,b);
q.push(p);
 
cout << q.front().first << ' ' << q.front().second;        // 1 2
cout << q.back().first << ' ' << q.back().second;          // 2 3
 
//q가 비어있지 않은 동안
while(!q.empty())
{
    pair<int,int> n = q.front();
    q.pop();
 
    cout << n.first << ' ' << n.second << '\n';            // 1 2
                                                           // 2 3
}
 
cout << q.size();                                          // 0

q.push(make_pair(4,5));
q.push(make_pair(5,6));


queue<pair<int,int>> emt;
swap(q, emt);

cout << q.size();                                           // 0
                                  

29번째 줄을 보면 swap이라는 함수를 사용한 것을 볼 수 있습니다. 자주 쓰이지는 않지만, vector와는 달리 queue는 clear() 멤버 함수가 없으므로 swap이라는 함수를 이용해 clear() 하고자 하는 queue를 빈 queue와 swap해줌으로써 clear()와 같은 효과를 낼 수 있습니다. 이렇게 swap을 이용하는 것이 queue가 빌 때까지 원소를 pop()하는 것보다 빠르기 때문에 알아두는 것이 좋겠습니다.

2. stack

1) 정의

LIFO(Last In First Out, 후입선출) 자료구조

2) 용도

① DFS(Depth First Search, 깊이우선탐색)

② 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 LIFO의 구조를 가지는 문제를 풀 때

(Ex. 만약 어떤 일의 실행순서를 기록해두었다가 나중에 일의 순서를 반대로 출력하고 싶은 경우, 일을 실행할 때마다 stack에 차례대로 push 해두었다가 모든 일을 실행하고 나서 stack이 빌 때까지 pop하면 된다)

3) 사용법

stack을 사용하기 위해서는 <stack>을 include 해야 합니다.

편의상 멤버 함수의 적용 대상이 되는 stack을 s라고 부르도록 하겠습니다.

stack의 멤버 함수들은 queue와 매우 유사한 형태를 띄고 있기 때문에, queue를 이해하신 분이라면 비슷한 맥락으로 사용이 가능합니다.

멤버 함수	기능
s.size()	s의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴
s.empty()	s의 사이즈가 0인지 아닌지를 확인
s.top()	s에 가장 나중에 들어간 원소를 리턴
s.push(val)	s의 뒤에 val 추가
s.pop()	s에 가장 나중에 들어간 원소를 삭제

4) 예제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

stack<int> s;   for(int i=1; i<=5; i++)     s.push(i);   cout << s.size();                                        // 5   //s가 비어있지 않은 동안 while(!s.empty()) {     int n = s.top();     s.pop();       cout << n << '\n';             // 5 4 3 2 1  }   cout << s.size();                                       // 0                        Colored by Color Scripter

cs