[C][Python] 덱 (Deque ; Double-Ended Queue)

덱, Deque, Double-Ended queue,

이름에서 알 수 있듯이 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐임을 알 수 있다

(큐는 선입선출만 가능)

 

그러나 스택과 큐와 마찬가지로 데이터를 중간에 삽입, 삭제는 용이하지 않다

 

 

->

pushFront() : Front 에서의 삽입

pushBack() : Back 에서의 삽입

popFront() : Front 에서의 삭제

popBack() : Back 에서의 삭제

 

---

 

1. 배열을 이용한 코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>

int deque[20000];
int back = 10000;
int front = 10000;

int main()
{
    int num;
    char str[12];

    scanf("%s", str);

    if(str[1] == 'u')
    {
        if(str[5] == 'f') // push_front
        {
            scanf("%d", &num);
            deque[front--] = num;
        }
        else // push_back
        {
            scanf("%d", &num);
            deque[++back] = num;
        }
    }
    else if(str[1] == 'o')
    {
        if(str[4] == 'f') // pop_front
        {
            if(front == back)
                printf("%d\n", -1);
            else
            {
                printf("%d\n", deque[front+1]);
                deque[++front] = 0;
            }
        }
        else // pop_back
        {
            if(front == back)
                printf("%d\n", -1);
            else
            {
                printf("%d\n", deque[back]);
                deque[back--] = 0;
            }
        }
    }
    else if(str[0] == 's') // size
    {
        printf("%d\n", back-front);
    }
    else if(str[0] == 'e') // empty
    {
        if(back == front)
            printf("%d\n", 1);
        else
            printf("%d\n", 0);
    }
    else if(str[0] == 'f') // front
    {
        if(back == front)
            printf("%d\n", -1);
        else
            printf("%d\n", deque[front+1]);
    }
    else // back
    {
        if(back == front)
            printf("%d\n", -1);
        else
            printf("%d\n", deque[back]);
    }

    return 0;
}

 

다음과 같이 배열의 중간값에서 back, front 값을 시작하여 구현할 수 있다

 

반면에, 다음과 같이 보통의 스택, 큐와 같이 -1에서 시작하여 구현할 수도 있다

 

#include <stdio.h>
#include <stdlib.h>

int deque[10001];
int back = -1;

void pushFront(int num);
void pushBack(int num);
void popFront();
void popBack();

int main()
{
    int num;
    char str[12];
    
    scanf("%s", str);

    if(str[1] == 'u')
    {
        if(str[5] == 'f') // push_front
        {
            scanf("%d", &num);
            pushFront(num);
        }
        else // push_back
        {
            scanf("%d", &num);
            pushBack(num);
        }
    }
    else if(str[1] == 'o')
    {
        if(str[4] == 'f') // pop_front
            popFront();
        else // pop_back
            popBack();
    }
    else if(str[0] == 's') // size
    {
        printf("%d\n", back+1);
    }
    else if(str[0] == 'e') // empty
    {
        if(back == -1)
            printf("%d\n", 1);
        else
            printf("%d\n", 0);
    }
    else if(str[0] == 'f') // front
    {
        if(back == -1)
            printf("%d\n", -1);
        else
            printf("%d\n", deque[0]);
    }
    else // back
    {
        if(back == -1)
            printf("%d\n", -1);
        else
            printf("%d\n", deque[back]);
    }

    return 0;
}

void pushFront(int num)
{
    for(int i=back ; i>=0 ; i--)
    {
        deque[i+1] = deque[i];
    }
    deque[0] = num;
    back++;
}

void pushBack(int num)
{
    deque[++back] = num;
}

void popFront()
{
    if(back == -1)
        printf("%d\n", -1);
    else
    {
        printf("%d\n", deque[0]);

        for(int i=0 ; i<back ; i++)
        {
            deque[i] = deque[i+1];
        }

        deque[back--] = 0;
    }
}

void popBack()
{
    if(back == -1)
        printf("%d\n", -1);
    else
    {
        printf("%d\n", deque[back]);
        deque[back--] = 0;
    }
}

 

처음 코드와의 차이점은

 

초기 back 값을 -1로 하였기 때문에,

 

Front에서 push나 pop을 할 때에

 

뒷 배열 인자들을 모두 뒤로 밀거나(push 할 때에), 앞으로 당겨야 한다는 것(pop 할 때에)이다

 

---

 

2. 다음은 링크드 리스트(Linked List)를 이용한 덱 코드이다

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int num;
    struct node *prev;
    struct node *next;
}Node;

Node *front;
Node *back;
int size = 0;

void pushFront(int num);
void pushBack(int num);
void popFront();
void popBack();
int isEmpty();

int main()
{
    front = (Node *)malloc(sizeof(Node));
    front = NULL;
    back = (Node *)malloc(sizeof(Node));
    back = NULL;

    int num;
    char str[12];
    
    scanf("%s", str);

    if(str[1] == 'u')
    {
        if(str[5] == 'f') // push_front
        {
            scanf("%d", &num);
            pushFront(num);
        }
        else // push_back
        {
            scanf("%d", &num);
            pushBack(num);
        }
    }
    else if(str[1] == 'o')
    {
        if(str[4] == 'f') // pop_front
            popFront();
        else // pop_back
            popBack();
    }
    else if(str[0] == 's') // size
        printf("%d\n", size);

    else if(str[0] == 'e') // empty
        printf("%d\n", isEmpty());

    else if(str[0] == 'f') // front
    {
        if(isEmpty() == 1)
            printf("%d\n", -1);
        else
            printf("%d\n", front->num);
    }
    else // back
    {
        if(isEmpty() == 1)
            printf("%d\n", -1);
        else
            printf("%d\n", back->num);
    }

    return 0;
}

void pushFront(int n)
{
    Node *now = (Node *)malloc(sizeof(Node));
    now->num = n;
    now->prev = NULL;
    now->next = NULL;

    if(isEmpty() == 1)
    {
        front = now;
        back = now;
    }
    else
    {
        front->prev = now;
        now->next = front;
        front = now;
    }

    size++;
}

void pushBack(int n)
{
    Node *now = (Node *)malloc(sizeof(Node));
    now->num = n;
    now->prev = NULL;
    now->next = NULL;

    if(isEmpty() == 1)
    {
        front = now;
        back = now;
    }
    else
    {
        back->next = now;
        now->prev = back;
        back = now;
    }

    size++;
}

void popFront()
{
    if(isEmpty() == 1)
    {
        printf("-1\n");
    }
    else
    {
        Node *temp = front;

        front = temp->next;

        printf("%d\n", temp->num);
        free(temp);
        
        if(front == NULL)
            back = NULL;
        else
            front->prev = NULL;

        size--;
    }
}

void popBack()
{
    if(isEmpty() == 1)
    {
        printf("-1\n");
    }
    else
    {
        Node *temp = back;

        back = temp->prev;

        printf("%d\n", temp->num);
        free(temp);
        
        if(back == NULL)
            front = NULL;
        else
            back->next = NULL;

        size--;
    }
}

int isEmpty()
{
    if(size == 0)
        return 1;
    else
        return 0;
}

 

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

 

---

 

이를 파이썬에서 덱은 다음과 같이 collections 모듈의 deque를 이용할 수 있다

from collections import deque

q = deque([4, 5, 6])
q.append(7)
q.append(8)
print(q)
# deque([4, 5, 6, 7, 8])
print(q.popleft())
# 4
print(q.popleft())
# 5
print(q)
# deque([6, 7, 8])

내부적으로 linked list를 사용하고 있기 때문에

popleft(), appendleft(x) 모두 O(1)의 시간 복잡도를 가지고

i번째 데이터 접근에는 O(N)의 시간 복잡도를 가진다

---

+ 큐는 다음과 같이 queue 모듈의 Queue 클래스를 사용한다

from queue import Queue

q = Queue()
q.put(4)
q.put(5)
q.put(6)
print(q.get())
# 4
print(q.get())
# 5
print(q.get())
# 6

이 역시 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간 복잡도를 가진다