C++ STL Stack/Queue(스택/큐)에 관한 정보!

이번에는 역시나 백준 문제를 풀 때 꽤 자주 쓰이는 STL 중 하나인 stack과 queue에 대해 알아보자! 참고로 이 글은 스택과 큐라는 자료구조에 대해서 알고 있다는 가정 하에 쓴 글이다. 따라서 스택이나 큐 자체가 뭔지 잘 모른다면 먼저 STL을 공부하기 전에 스택과 큐 자체에 대해 공부하고 오도록 하자!

그리고 추가적인 생각인데, STL을 사용하기에 앞서 먼저 스택과 큐를 배열 혹은 링크드 리스트 형태로 구현을 해서 사용을 좀 해보는 것도 꽤 좋은 방법이라고 생각한다. 학기 중에 STL이 금지됐어서 큐와 스택을 굉장히 여러번 구현했었는데, 이해에 있어서 꽤나 큰 도움이 됐던 것 같다. 그리고 맨날 구현해서 쓰다가 STL만 휙 갖다가 쓰니까 아주아주 편해죽겠다.

그리고 벡터 글에서도 말했지만, 여기서 설명하는 사용법이나 각종 내용들은 거의 다 내 뇌에서 나온 것이라서 빠뜨린 것도 많고, 좀 정확하지 않을수도 있다. 다만, 내 뇌를 써서 백준 문제들을 풀면서 아직까진 문법적으로 크게 걸린 것들이 없어서 좀 더 쉬운 이해를 돕고자 이렇게 적는다.

일단 사용하려면 헤더 include를 해줘야 한다

#include <stack>
#include <queue>

다음은 선언 방법이다. 바로 코드를 통해 알아보자.

stack<type> name;
queue<type> name;

다음과 같이 선언한다. 벡터랑 굉장히 비슷한 느낌이다.

일단 스택과 큐, 공통되는 함수부터 봐보자. 확실히 stl vector와 굉장히 비슷한 느낌이 들었다. 먼저 empty()다. 벡터와 똑같이 스택/큐가 비어있는지 확인해주는 함수다. 반환형은 bool이다. 당연히 비어있으면 true, 아니면 false 반환이다.
그리고 size()는 스택/큐의 크기를 반환한다. 여기서 크기란 스택/큐 속에 들어있는 요소의 개수를 의미한다.

이제 스택 고유의 함수를 보자.
먼저 top()이다. 스택의 top 원소를 반환한다. 다시 말해, 가장 최근에 push 됐던 원소를 반환한다.
push(삽입값)은 데이터 삽입함수다. 스택이니까 당연히 top에 삽입된다.
pop()은 데이터 삭제함수다. 역시 스택이니까 당연히 top의 원소를 삭제한다.
예시 코드를 살짝 써보자.

stack<int> s;
s.push(1);
s.push(2);
cout<<s.size()<<endl; // 2 출력
if(s.empty())
	cout<<"Empty!"<<endl; // 출력 x
cout<<s.top()<<endl; // 2 출력
s.pop(); // 2 삭제. 1만 남음
cout<<s.top()<<endl; // 1 출력
s.pop(); // 남은 1도 삭제

다음은 큐 고유의 함수다.
먼저 front()다. 큐의 front 원소를 반환한다. 다시 말해, 가장 처음에 push 됐던 원소를 반환한다.
다음은 back()이다. 큐의 back 원소를 반환한다. 다시 말해 가장 최근에 push 됐던 원소를 반환한다.
push(삽입값)은 스택과 같다. 다만 따로 해놓은 이유는 push 되는 위치가 다르기 때문이다. 당연히 큐니까 삽입은 back에 된다.
pop() 역시 같은데, 큐니까 front의 원소가 삭제된다.
역시 예시 코드를 살짝 써보자.

queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout<<q.size()<<endl; // 3 출력
if(q.empty())
	cout<<"Empty!"<<endl; // 출력 x
cout<<q.front()<<endl; // 1 출력
cout<<q.back()<<endl; // 3 출력
s.pop(); // 1 삭제

참고로 큐에서는 back을 rear라고 하기도 한다. 그리고 push를 enqueue, pop을 dequeue라고 하기도 한다.

그리고 이건 개인적으로도 생겼었던 궁금증인데, 벡터에는 벡터를 초기화시켜주는 clear()라는 함수가 존재한다. 그럼 스택이나 큐에는?
아쉽게도 존재하지 않는다. 다만, 그냥 우리가 코드를 통해 해줄 수 있다.
단순히 empty까지 계속 pop 해주면 된다.
그니까 이렇게 하는 것이다.

while(!s.empty()) // 혹은 q.empty()
	s.pop(); // 혹은 q.pop()

이렇게 되면 스택이나 큐가 완전히 비워질때까지 계속 pop을 하는 것이니까, 사실상 clear의 기능을 수행하게 되는 것이다.

오늘은 stl stack과 queue에 대해 알아봤다. 이외에도 여러 기능이 있지만, 지금까지는 이 정도만 사용을 했다. 역시 앞으로도 새로운 정보가 생기면 바로 추가하도록 하겠다!

추가: priority_queue / 우선순위큐!

queue 헤더에 priority_queue라는 친구가 있다. 이 우선순위큐는 내부적으로 Heap 자료구조를 사용하고 있다. 큐에 있는 모든 원소들 중에서 가장 우선순위가 값이 top이 되도록 해주는 자료구조다. 그냥 아래와 같이 선언하면

priority_queue<int> q;

기본적으로 내림차순 정렬이 된다. 이때 여기서 최댓값이 우선순위가 가장 높아 top이 된다.
만약 오름차순 정렬을 하고 싶으면

priority_queue<int, vector<int>, greater<int>> q;

이렇게 해주면 된다. 이때는 최솟값이 top이 된다. 그래서 이 우선순위 큐는 큐지만 top이라는 스택의 키워드를 사용한다.

만약 사용자 지정 함수를 사용하고 싶다면? 그땐 sort처럼 사용자 지정 함수 comp를 만들어서 넣어주면 끝 아닌가~라고 생각하면 틀린다. comp라는 구조체를 만들고 그 안에서 연산자 오버로딩을 통해서 사용자 지정을 해줘야 한다! 무슨 소리냐면

struct comp
{
    bool operator()(int a, int b) // 연산자 오버라이딩을 통해 사용자 지정 함수 정의!
    {
    .....
    }
};
....
int main()
{
	priority_queue<int, vector<int>, comp> q;
}

이렇게 해줘야 되는 것이다! sort랑은 조금 다르니까 꼭 참고하도록 하자!

주요함수는 아래와 같다.

• push(): 우리가 아는 그 push()
• pop(): top을 제거한다
• top(): top을 반환한다
• empty(): 우리가 아는 그 empty()
• size(): 우리가 아는 그 size()
  사실 push, empty, size는 같고 pop과 top만 좀 달라서 이것만 좀 참고하면 되겠다. 대표적인 우선순위 큐 문제로는 백준 1927번 문제가 있다! 우선순위 큐를 쓰면 간단하니까 한번 풀어보자!