[자료구조] 스택, 큐, 우선순위 큐, 덱

01. 스택

스택 (Stack) 👉 박스 쌓기, 선입후출

스택 기본 함수

• stack.push(element): 스택에 데이터 추가
• stack.pop() : 스택의 top 데이터 삭제
• stack.top() : 스택의 top 데이터 반환
• stack.size() : 스택의 현재 size 반환
• stack.empty() : 스택이 비어있는지 확인
• swap(stack1, stack2) : 두 개의 스택 swap

스택 예제 코드

#include <bits/stdc++.h>

using namespace std;

stack<int> s;

int main(void) {
    // 삽입(5) - 삽입(10) - 삽입(3) - 삽입(22) - 삭제() - 삽입(1) - 삽입(4) - 삭제
    s.push(5);
    s.push(10);
    s.push(3);
    s.push(22);
    s.pop();
    s.push(1);
    s.push(4);
    s.pop();
    // 스택의 최상단 원소부터 출력
    while (!s.empty()) {
        cout << s.top() << ' '; // 출력 후
        s.pop(); // 삭제
    }
}

---

02. 큐

큐 (Queue) 👉 대기줄, 선입선출

큐 기본 함수

• q.push(element) : 큐에 데이터 추가
• q.pop() : 큐의 front 데이터 삭제
• q.front() : 큐의 최상위 데이터 반환
• q.back() : 큐의 마지막 데이터 반환
• q.size() : 큐의 현재 사이즈 반환
• q.empty() : 큐가 비어있는지 확인
• swap(q1, q2) : 두 개의 큐 swap

큐 예제 코드

#include <bits/stdc++.h>

using namespace std;

queue<int> q;

int main() {
    // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
    q.push(5);
    q.push(2);
    q.push(3);
    q.push(7);
    q.pop();
    q.push(1);
    q.push(4);
    q.pop();
    // 먼저 들어온 원소부터 추출
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}

---

03. 우선순위 큐

우선순위큐 (Priority Queue) 👉 우선순위에 따라 정렬된 큐, 우선순위가 높은 것이 top을 유지하도록 설계되어 있다.

우선순위 큐 기본 함수

• pq.push() : 우선순위 큐에 원소 삽입, 비교 함수에 따라 내부 정렬된다.
• pq.pop() : 제일 높은 우선순위 값 삭제
• pq.top()
• pq.empty()
• pq.size()

우선순위큐 예제 코드

내림차순 (기본)

#include <bits/stdc++.h>

using namespace std;

priority_queue<int> pq;

int main(void) {
    pq.push(5);
    pq.push(10);
    pq.push(3);
    pq.push(7);
    while (!pq.empty())
    {       
        cout << pq.top() << ' ';
        pq.pop();
    }   
}

출력 👉 10 7 3 5 내부에서 자동 정렬된 것을 알 수 있음!! 내림차순

오름차순

#include <bits/stdc++.h>

using namespace std;

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

int main(void) {
    pq.push(5);
    pq.push(10);
    pq.push(3);
    pq.push(7);
    while (!pq.empty())
    {       
        cout << pq.top() << ' '; 
        pq.pop();
    }   
}

출력 👉 3 5 7 10 오름차순 정렬, greater<int> 추가

연산자 오버로딩, 비교함수 선언

#include <bits/stdc++.h>

using namespace std;
// 절대값이 더 작은 값에 우선순위를 높게 주고, 절대값이 같다면 더 작은 값에 우선순위를 높게 준다.
struct compare { 
    bool operator() (int a, int b) {
        if(abs(a) > abs(b))
            return true;
        else if (abs(a) == abs(b))
            if (a > b)
                return true;
            else 
                return false;
        return false;
    }
};

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

int main() {
    pq.push(50);
    pq.push(-41);
    pq.push(-50);
    pq.push(-100);
    pq.push(500);
    pq.push(41);

    while (!pq.empty())
    {       
        cout << pq.top() << ' ';
        pq.pop();
    }   
    return 0;
}

---

04. 덱 (deque)

덱 deque (Double Ended Queue) 👉 앞, 뒤에서 삽입 & 삭제 가능!

덱 기본 함수

• dq.push_back : 뒤에서 원소 추가
• dq.pop_back : 뒤에서 원소 삭제
• dq.push_front : 앞에서 원소 추가
• dq.pop_front : 앞에서 원소 삭제
• dq.insert(위치, 값) : 중간에 값 추가 dq.insert(dq.begin() + 2, 100)
• dq.erase(위치, 값) : 중간의 값 삭제 dq.erase(dq.begin() + 2)
• dq.front() : 덱의 첫 번째 원소
• dq.back() : 덱의 마지막 원소
• dq.size() : 덱의 현재 사이즈 반환
• dq.begin()
• dq.clear() : 모든 원소 삭제
• dq.rbegin() : 역방향으로 첫 번째 원소의 반복자를 반환

덱의 원소 접근

• dq[n] : n번째 원소
• dq.at(n) : n번째 원소

덱 예제 코드

#include <bits/stdc++.h>

using namespace std;

deque<int> dq;

int main() {
    dq.push_front(100);
    dq.push_back(45);
    dq.push_back(20);
    dq.push_front(11);

    for (int i = 0; i < dq.size(); i++)
    {
        cout << dq[i] << ' ';
    }

    return 0;
}