[C++] stack & queue & deque & priority_queue

map이 pair로 구현가능했다면 stack, queue, deque는 linked list로 구현 가능하다.

 

---

1. stack

 

 

#include<iostream>
#include<stack>
using namespace std;

stack<string> stk;
int main(){
    stk.push("엄");
    stk.push("준");
    stk.push("준");
    stk.push("식");
    stk.push("시..");
    while(stk.size()){
        cout << stk.top() << '\n';
        stk.pop();
    }
}
/*
시..
식
준
준
엄
*/

LIFO(Last In First Out)의 특성을 가진 자료 구조다.

• #include<stack>
• stk,push(”엄”); : 데이터 추가.
• stk.pop(); : 가장 마지막에 추가한(가장 상위의) 데이터 삭제.
• stk.top() : 가장 마지막에 추가한(가장 상위의) 데이터 반환.
• stk.empty() : stack이 비어있으면 true를 반환.

c++의 stack에는 clear() 메서드가 없는 관계로 초기화를 위해선 다음과 모든 요소를 pop()한다.

 

    while(stk.size()){
      stk.pop();
    }

 

---

2. queue

 

 

#include<iostream>
#include<queue>
using namespace std;

queue<int> q;
int main(){
    for(int i=1; i <= 10; i++) q.push(i);
    while(q.size()){
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}
/*
1 2 3 4 5 6 7 8 9 10 
*/

선입선출(FIFO, First In First Out)을 지닌 자료 구조.

• #include<queue>
• q.pusk(i); : 데이터 추가.
• q.pop(); : 가장 먼저 들어온 데이터 삭제.
• q.front() : 가장 먼저 들어온 데이터 반환.
• q.back() : 가장 마지막에 들어온 데이터 반환.
• q.empty() : queue가 비어있으면 true를 반환.

 

---

3. deque

 

앞뒤로 삽입, 삭제, 참조가 가능한 자료구조.

 

#include<iostream>
#include<deque>
using namespace std;

int main(){
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_back(3);
    cout << dq.front() << '\n';
    cout << dq.back() << '\n';
    cout << dq.size() << '\n';

    dq.pop_back();
    dq.pop_front();

    cout << dq.front() << '\n';
    cout << dq.back() << '\n';
    cout << dq.size() << '\n';
    return 0;
}
/*
1
3
3
2
2
1
*/

• #include<deque>
• dq.push_front()
• dq.push_back()
• dq.pop_front()
• dq.pop_end()
• dq.front()
• dq.back()

 

---

4. priority queue

 

 

우선순위 큐는 내부적으로 힙 구조를 사용하여 데이터를 정렬합니다.

 

기본적으로 우선순위 큐는 less<T>(a<b)으로 정렬된다.

 

이는 오름차순으로 정렬하게 되는데 priority queue에서는 back에서 front 방향으로 정렬하기 때문에 결과적으로 top() 함수는 가장 큰 값을 반환합니다. (괴상하다. sort랑 혼동될 것 같다.)

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<functional> //greater, less
using namespace std;

//vector를 greater<T>로 정렬한다. + queue는 back에서부터 출력한다 
//이에 sort()와는 반대의 차순으로 출력된다.
priority_queue<int, vector<int>, greater<int>> pq; 
priority_queue<int> pq2;
priority_queue<int, vector<int>, less<int>> pq3;

int main(){
    for(int i = 5; i>=1; i--){
        pq.push(i);
        pq2.push(i);
        pq3.push(i);
    }
    while(pq.size()){
        cout << pq.top() << " : " << pq2.top() << " : " << pq3.top() << '\n';
        pq.pop(); pq2.pop(); pq3.pop();
    }
    return 0;
}
/*
1 : 5 : 5
2 : 4 : 4
3 : 3 : 3
4 : 2 : 2
5 : 1 : 1
*/

기본적으로 내림차순(less<T>)으로 정렬한다.

• queue는 back에서부터 출력한다 → sort()와는 반대의 차순으로 출력된다.
• #include<queue>
• pq.push(i);
• pq.pop();
• pq.top()

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

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

• T : 저장된 요소의 Type이다. T가 Container::value_type과 동일해야 한다.
• Container : 요소를 저장하는 자료구조. SequenceContainer를 만족해야 한다.
• Compare : 비교 함수. greater<T> , less<T>를 사용할 수 있습니다.

 

출처 : https://en.cppreference.com/w/cpp/container/priority_queue

 

 

---

5. 주의점

 

queue나 stack 등등에서 top이나 pop 연산을 할 때 항상 size를 체크하자.

 

**if**(q.size() && q.top == value)

 

만약 해당 자료구조에 아무것도 없는데 해당 자료구조 내의 요소를 참조하려고 할 경우 참조에러(reference Error)가 발생할 수 있다.

 

---