[자료구조] 덱(Deque)

 

덱

• 양쪽 끝에서 삽입, 삭제가 가능한 자료구조

그림 첨부 

 

덱 성질

• 원소 추가 : O(1)
• 원소 제거 : O(1)
• 제일 앞/뒤 원소 확인 : O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 불가능 (C++의 STL deque에서는 인덱스로 원소 접근 가능)

 

덱 구현

마찬가지로 배열로 구현할 수 있다. 배열 크기는 넉넉하게 잡으면 된다. 

큐와 똑같이 head, tail가 필요하다. 

head는 가장 앞 원소의 인덱스를 이고, tail은 가장 뒤 원소의 인덱스+1이다. 

head, tail 초기값은 배열의 중앙 인덱스 값으로 둔다. 왜냐하면 시작 지점을 0으로 두었을 경우 head가 왼쪽으로 확장할 수 없다. 

그림 첨부

 

head의 시작 지점이 0이고 push_front가 발생한다면, 0이전은 -1인데 배열은 음수를 인덱스로 가질 수가 없다. 

그림 첨부

 

tail도 마찬가지다. tail의 시작 지점을 배열의 가장 끝 인덱스로 두면, 배열의 인덱스 범위를 벗어나게 되어 에러가 난다. 

그림 첨부

 

따라서 head, tail의 시작 지점은 배열의 중간으로 둬야 한다. 

그림 첨부

 

이렇게 배열의 중간에 head, tail을 두면 이런식으로 원소들이 채워질 수 있다. 

그림 첨부 

 

코드

internal class Program
{
    public const int MX = 1000005;
    public static readonly int[] dat = new int[2 * MX + 1];
    public static int head = MX;
    public static int tail = MX;

    public void push_front(int x)
    {
        dat[--head] = x;
    }

    public void push_back(int x)
    {
        //dat[++tail] = x;
        dat[tail++] = x;
    }

    public void pop_front()
    {
        head++;
    }

    public void pop_back()
    {
        tail--;
    }

    public int front()
    {
        return dat[head];
    }

    public int back()
    {
        //return dat[tail];
        return dat[tail - 1];
    }

    public void test()
    {

    }

    static void Main(string[] args)
    {
        Program pg = new Program();

        pg.test();
    }
}