[자료구조] 덱(Deque) - 코딩기록

덱

덱은 앞서 포스팅에서 올렸던 스택과 큐를 합친 버전이라고 할 수 있다.

스택이나 큐는 한쪽에서만 삽입과 삭제가 가능했다면 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하게 만든 큐이다. 터널과 비슷하다고 할 수 있다.

덱은 스택이나 큐처럼 사용할 수 있기 때문에 활용도가 높은 자료구조이다.

덱의 구조

덱의 기능

이제 덱STL을 활용해 기능들을 살펴보겠다.

• push_front(x) : 덱의 앞에 x를 추가
• push_back(x) : 덱의 뒤에 x를 추가
• pop_front() : 덱의 원소 중 맨 앞 원소를 삭제
• pop_back() : 덱의 원소 중 맨 뒤 원소를 삭제
• front() : 덱의 맨 앞 원소를 반환
• back() : 덱의 맨 뒤 원소를 반환
• empty() : 덱이 비어있으면 1(true), 비어있지 않으면 0(false)를 반환
• size() : 덱의 원소 개수(사이즈) 반환

 

소스 코드를 통해 다시 살펴보자

 

#include <iostream>
#include <deque>//덱 라이브러리
using namespace std;
//dq라는 int형 덱을 선언하는 방법
deque <int> dq;

int main()
{
    dq.push_front(1); //덱의 앞에 1 삽입

    dq.push_back(3); //덱의 뒤에 3 삽입

    dq.push_front(2); //덱의 앞에 2 삽입

    dq.push_back(4); //덱의 뒤에 4 삽입

    cout<<dq.size()<<"\n"; //덱의 원소 개수 반환

    for(int i=0;i<4;i++)
    {
        cout<<dq.front()<<' ';
        dq.pop_front();
    } //덱에 있는 원소를 앞에서부터 출력
    
    cout<<"\n"<<dq.empty(); //덱이 비어있다면 1출력
    return 0;
}

 

이 소스코드를 작동시키면

4

2 1 3 4

1

다음과 같이 출력된다.

 

덱을 활용한 간단한 문제를 풀어보며 감을 잡고 싶다면 백준 10866번을 풀어보는 것을 추천한다.

https://www.acmicpc.net/problem/10866

10866번: 덱