[C++] std::deque & std:stack

deque

 deque (double-ended queue)는 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 유연한 컨테이너이다. 이 컨테이너는 다양한 작업을 지원하며, 각각의 작업은 특정한 시간 복잡도를 가진다.

---

1. push_front: deque의 시작 부분에 요소를 추가한다. 시간 복잡도는 일반적으로 상수 시간(O(1))이다.
2. push_back: deque의 끝 부분에 요소를 추가한다. 이 작업 역시 상수 시간(O(1))이 소요된다.
3. pop_back: deque의 끝 부분에서 요소를 제거한다. 상수 시간(O(1))이 걸린다.
4. pop_front: deque의 시작 부분에서 요소를 제거한다. 이 작업도 상수 시간(O(1))이 소요된다.
5. erase: deque 내의 특정 위치에 있는 요소를 제거한다. 시간 복잡도는 선형 시간(O(n))이다. 제거하는 요소 뒤에 있는 모든 요소들을 한 칸씩 앞으로 이동해야 하기 때문이다.

예제 코드를 한 번 살펴보자.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    // push_front 사용
    dq.push_front(1);
    dq.push_front(2);

    // push_back 사용
    dq.push_back(3);
    dq.push_back(4);

    // deque 출력
    std::cout << "Deque after push_front and push_back: ";
    for (int n : dq)
        std::cout << n << ' ';
    std::cout << '\n';

    // pop_front 사용
    dq.pop_front();

    // pop_back 사용
    dq.pop_back();

    // deque 출력
    std::cout << "Deque after pop_front and pop_back: ";
    for (int n : dq)
        std::cout << n << ' ';
    std::cout << '\n';

    // erase 사용
    dq.erase(dq.begin());

    // 수정된 deque 출력
    std::cout << "Deque after erase: ";
    for (int n : dq)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

 

앞서 언급했듯, deque는 배열 기반과 연결 리스트 기반 컨테이너가 섞여 있는 형태이며, 각각의 장점을 적당히 가지고 있다.

 

이는 순서대로 처리되어야 하는 대기열과 같은 경우에 많이 사용된다.

---

stack

 

 stack은 후입선출(LIFO, Last-In First-Out) 방식으로 작동하는 컨테이너 어댑터이다.

 

stack은 요소가 추가되고 제거되는 순서가 엄격하게 제한되어 있어, 새로운 요소는 항상 컨테이너의 "top"에 추가되며, 요소를 제거할 때도 "top"에서만 이루어진다. 이러한 특성 때문에 stack은 일련의 요소를 역순으로 처리하거나, 데이터가 후입선출 방식으로 관리되어야 할 때 유용하다.

 

stack은 기본적으로 세 가지 주요 작업을 지원한다:

1. push: 이 함수는 새로운 요소를 stack의 맨 위에 추가한다. 시간 복잡도는 일반적으로 상수 시간(O(1))이다.
2. pop: 이 함수는 stack의 맨 위에 있는 요소를 제거한다. 단, 제거된 요소는 반환되지 않는다. 시간 복잡도 역시 상수 시간(O(1))이다.
3. top: 이 함수는 stack의 맨 위에 있는 요소에 접근할 수 있도록 한다. 이 요소는 제거되지 않고, 단순히 참조만 제공된다. 시간 복잡도는 상수 시간(O(1))이다.

예제 코드를 한번 보자.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stk;

    // push 사용
    stk.push(1);
    stk.push(2);
    stk.push(3);

    // top 사용
    std::cout << "Top element: " << stk.top() << '\n';

    // pop 사용
    stk.pop();
    std::cout << "Top element after pop: " << stk.top() << '\n';

    // stack이 비어 있는지 확인
    if (!stk.empty()) {
        std::cout << "Stack is not empty.\n";
    }

    return 0;
}

 

stack은 간단하면서도 효율적인 데이터 구조로, 다양한 상황에서 유용하게 사용될 수 있다.

---

std::queue도 있긴 하지만 stack의 LIFO이 아닌 FIFO을 지원한다는 점을 제외하고는 거의 동일하게 동작하기 때문에 따로 다루지 않으려고 한다.

 

stack과 queue 모두 기본적으로 std::deque를 기본 컨테이너로 사용한다.