덱(Deque)

:double-ended queue 줄임말

: 앞, 뒤 모두에서 삽입 및 삭제가 가능한 큐

스택이나 큐보다는 유연하고 링크드 리스트보다는 덜 유연하다
(중간에서 삽입 삭제는 불가능)
원형 큐를 조금 수정해서 만들면 된다

---

덱의 연산

• void push_front()
  : 정수를 덱의 앞에 넣는다

• void push_back()
  : 정수를 덱의 뒤에 넣는다

• int pop_front()
  : 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력
  만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력

• int pop_back()
  : 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력
  만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력

• int size()
  : 덱에 들어있는 정수의 개수를 출력

• int empty()
  : 덱이 비어있으면 1을, 아니면 0을 출력

• int front()
  : 덱의 가장 앞에 있는 정수를 출력
  만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력

• int back()
  : 덱의 가장 뒤에 있는 정수를 출력
  만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력

함수 이름과 설명은 백준 10866에서 가져왔다
https://www.acmicpc.net/problem/10866

---

덱의 구현

이전에 만들었던 원형 큐를 조금 수정해서 만들 것이다
https://velog.io/@seon7129/C%EC%96%B8%EC%96%B4-%ED%81%90queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

기존 원형큐는 push_back와 pop_front이고
이걸 조금 수정해서 push_front와 pop_back만 만들어주면 된다!

---

소스코드

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

typedef struct queue
{
    int front;
    int rear;
    int *data;
    int max;
    int cnt;
}queue;

void qExpand(queue *q);
void enqueue_front(queue *q, int data);
int dequeue_front(queue *q);
void enqueue_back(queue *q, int data);
int dequeue_back(queue *q);

void initQueue(queue *q, int size)
{
    q->data = (int *) malloc(size * sizeof(int));
    if (!q->data)
        return ;
    q->front = size - 1;
    q->rear = size - 1;
    q->max = size;
    q->cnt = 0;
}

int empty(queue *q)
{
    if (q->rear == q->front)
        return (1);
    return (0);
}

int full(queue *q)
{
    if ((q->rear + 1) % q->max == q->front)
        return (1);
    return (0);
}

int front(queue *q)
{
    int first_data;

    first_data = (q->front + 1) % q->max;
    if (!empty(q))
        return (q->data[first_data]);
    return (-1);
}

int back(queue *q)
{
    if (!empty(q))
        return (q->data[q->rear]);
    return (-1);
}

void qExpand(queue *q)
{
    int i;
    int count;
    int *buf;

    buf = (int *) malloc(q->max * sizeof(int));
    count = q->cnt;
    i = 0;
    while (i < count)
    {
        buf[i] = dequeue_front(q);
        i++;
    }
    q->max *= 2;
    q->data = (int *) realloc(q->data, q->max * sizeof(int));
    if (!q->data)
        return ;
    count = q->cnt;
    i = 0;
    while (i < count)
    {
        enqueue_front(q, buf[i]);
        i++;
    }
    free(buf);
}

void enqueue_front(queue *q, int data)
{
    if (!full(q))
    {
        q->data[q->front] = data;
        q->front = (q->front - 1 + q->max) % q->max;
        q->cnt++;
    }
    else
    {
        qExpand(q);
        enqueue_front(q, data);
    }
}

//기존 원형큐
int dequeue_front(queue *q)
{
    if (!empty(q))
    {
        q->front = (q->front + 1) % q->max;
        q->cnt--;
        return (q->data[q->front]);
    }
    return (-1);
}

//기존 원형큐
void enqueue_back(queue *q, int data)
{
    if (!full(q))
    {
        q->rear = (q->rear + 1) % q->max;
        q->data[q->rear] = data;
        q->cnt++;
    }
    else
    {
        qExpand(q);
        enqueue_back(q, data);
    }
}

int dequeue_back(queue *q)
{
    int value;

    if (!empty(q))
    {
        value = q->rear;
        q->rear = (q->rear - 1 + q->max) % q->max;
        q->cnt--;
        return (q->data[value]);
    }
    return (-1);
}

push는 enqueue로 pop은 dequeue로 적었다
왜냐면 이전코드를 복사 붙여넣기 수정했기 때문