덱이란? (DEQUE)

덱(deque) 은 double-ended queue 의 줄임말로서 큐의 front 와 rear 에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용되지 않는다. 원형 큐와 덱은 공통점이 많은데, 원형 큐를 확장하면 덱도 손쉽게 구현할 수 있다. 덱도 원형 큐와 같이 front 와 rear 를 사용한다. 따라서 큐에서 사용한 배열 data 와 front, rear 를 그대로 사용하면 되고 추가적인 데이터는 필요 없다.

덱에서 새롭게 추가된 연산에는 delete_rear(), add_front(), get_rear() 가 있다. get_rear() 가 가장 간단한데 공백상태가 아닌 경우 rear 가 가리키는 항목을 반환하면 된다. delete_rear() 와 add_front() 에서는 원형 큐에서와 다르게 반대 방향의 회전이 필요하다. front 나 rear 를 감소시켜야 하는데 만약 음수가 되면 MAX_QUEUE_SIZE 를 더해줘야 한다. 따라서 front 나 rear 는 다음과 같이 변경된다.

front <- (front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
rear <- (rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include <malloc.h>
#include <string.h>

#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
  int front;
  int rear;
  element data[MAX_QUEUE_SIZE];
} DequeType;

//오류 함수
void error(char *message)
{
  fprintf(stderr,"%s\n",message);
  exit(1);
}

//초기화 함수
void init_deque(DequeType *q) {
  q->front = q->rear;
}

//공백 상태 검출 함수
int is_empty(DequeType *q)
{
    return (q->front == q->rear);
}

//원형큐 출력 함수
void deque_print(DequeType *q)
{
  printf("DEQUE(front=%d rear=%d) = ",q->front, q->rear);
    if (!is_empty(q)) {
        int i = q->front;
        do {
            i = (i+1)%(MAX_QUEUE_SIZE);
            printf("%d | ",q->data[i]);
            if (i == q->rear)
                break;
        } while (i != q->front);
    }
    printf("\n");
}
//포화 상태 검출 함수
int is_full(DequeType *q)
{
  return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}


//삽입함수
void add_rear(DequeType *q, element item)
{
  if (is_full(q))
    error("큐가 포화상태입니다");
    q->rear = (q->rear + 1)%MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

//삭제 함수
element delete_front(DequeType *q)
{
  if (is_empty(q))
    error("큐가 공백상태입니다");
    q->front = (q->front + 1)%MAX_QUEUE_SIZE;
    return q->data[q->front];
}


element get_front(DequeType *q)
{
  if (is_full(q))
    error("큐가 공백상태입니다");
  return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}

element get_rear(DequeType *q)
{
  if (is_full(q))
    error("큐가 공백상태입니다");
  return q->data[q->rear];
}

void add_front(DequeType *q, element val)
{
  if (is_full(q))
    error("큐가 포화상태입니다");
  q->data[q->front] = val;
  q->front = (q->front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}


element delete_rear(DequeType *q)
{
  int prev = q->rear;
  if (is_empty(q))
    error("큐가 공백상태입니다");
    q->rear = (q->rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}

int main()
{
  DequeType queue;
  
  init_deque(&queue);
 
  for (int i = 0; i < 3; i++) {
    add_front(&queue, i);
    deque_print(&queue);
  }

  for (int i = 0; i < 3; i++) {
    delete_rear(&queue);
    deque_print(&queue);
  }

  return 0;
}

result

DEQUE(front=4 rear=0) = 0 | 
DEQUE(front=3 rear=0) = 1 | 0 | 
DEQUE(front=2 rear=0) = 2 | 1 | 0 | 
DEQUE(front=2 rear=4) = 2 | 1 | 
DEQUE(front=2 rear=3) = 2 | 
DEQUE(front=2 rear=2) =

front 와 rear 가 어느 방향으로 동작하는지 잘 확인해야 한다. (아래 사진 보고 잘 이해)(시계방향인지 반시계방향인지)