덱(Deque)의 구현과 사용

덱(Deque)은 큐의 앞, 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다.

덱은 위 사진 형태의 원형 큐를 조금 확장하면 손쉽게 구현할 수 있다.

앞에서 구현한 원형 큐 코드에서 사용하지 않는 함수를 제거하고 인큐와 디큐 함수를 front와 rear로 나누어 구현하였다.

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

typedef struct {
  int max;
  int num;
  int front;
  int rear;
  int *que;
} IntQueue;

int Initialize(IntQueue *q, int max) {
  q->num = q->front = q->rear = 0;
  if ((q->que = calloc(max, sizeof(int))) == NULL) {
    q->max = 0;
    return -1;
  }
  q->max = max;
  return 0;
}

int Enque_f(IntQueue *q, int x) {
  if (q->num >= q->max)
    return -1;
  else {
    q->num++;
    q->que[--q->front] = x;
    if (q->front == 1)
      q->front = q->max-1;
    return 0;
  }
}


int Enque_r(IntQueue *q, int x) {
  if (q->num >= q->max)
    return -1;
  else {
    q->num++;
    q->que[q->rear++] = x;
    if (q->rear == q->max)
      q->rear = 0;
    return 0;
  }
}

int Deque_f(IntQueue *q, int *x) {
  if (q->num <= 0)
    return -1;
  else {
    q->num--;
    *x = q->que[q->front++];
    if (q->front == q->max)
      q->front = 0;
    return 0;
  }
}

int Deque_r(IntQueue *q, int *x) {
  if (q->num <= 0)
    return -1;
  else {
    q->num--;
    *x = q->que[--q->rear];
    if (q->rear++ == q->max)
      q->rear = 1;
    return 0;
  }
}

int Capacity(const IntQueue *q) { return q->max; }

int Size(const IntQueue *q) { return q->num; }

void Print(const IntQueue *q) {
  for (int i = 0; i < q->num; i++)
    printf("%d\n", q->que[(i + q->front) % q->max]);
}

void Terminate(IntQueue *q) {
  if (q->que != NULL)
    free(q->que);
  q->max = q->num = q->front = q->rear = 0;
}

void main(){
  IntQueue que;
  int value;
  printf("생성할 배열의 크기 : ");
  scanf("%d", &value);
  if(Initialize(&que, value) == -1){
    puts("\n큐 생성 실패");
  }
  while(1){
    int m, x, y; 

    printf("\n현재 데이터 수 : %d / %d\n", Size(&que), Capacity(&que));
    printf("(1)인큐 (2)디큐 (3)출력 (0)종료 : ");
    scanf("%d", &m);

    if(m==0) break;
    switch(m){
      case 1:
        printf("\n인큐\n");
        printf("(1)프론트 (2)리어 : ");
        scanf("%d", &y);
        if(y==1){
          printf("\n데이터 : "); scanf("%d", &x);
          if(Enque_f(&que, x)==-1) puts("\n인큐 실패");
        }else if(y==2){
          printf("\n데이터 : "); scanf("%d", &x);
          if(Enque_r(&que, x)==-1) puts("\n인큐 실패");
        }else printf("없는 번호 입니다.");
        break;

      case 2:
        printf("\n디큐\n");
        printf("(1)프론트 (2)리어 : ");
        scanf("%d", &y);
        if(y==1){
          if(Deque_f(&que, &x) == -1) puts("\n디큐 실패");
          else printf("\n디큐한 데이터 : %d\n", x);
        }else if(y==2){
          if(Deque_r(&que, &x) == -1) puts("\n디큐 실패");
          else printf("\n디큐한 데이터 : %d\n", x);
        }else printf("없는 번호 입니다.");
        break;

      case 3:
        Print(&que);
        break;
    }
  }
  Terminate(&que);
}

생성할 배열의 크기 : 10

현재 데이터 수 : 0 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 1

인큐
(1)프론트 (2)리어 : 1

데이터 : 1

현재 데이터 수 : 1 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 1

인큐
(1)프론트 (2)리어 : 1

데이터 : 2

현재 데이터 수 : 2 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 1

인큐
(1)프론트 (2)리어 : 1

데이터 : 3

현재 데이터 수 : 3 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 1

인큐
(1)프론트 (2)리어 : 2

데이터 : 4

현재 데이터 수 : 4 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 3
3
2
1
4

현재 데이터 수 : 4 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 2

디큐
(1)프론트 (2)리어 : 2

디큐한 데이터 : 4

현재 데이터 수 : 3 / 10
(1)인큐 (2)디큐 (3)출력 (0)종료 : 3
3
2
1

구현할때는 rear 변수가 요소를 대입할 위치, front 변수가 첫 번째 요소의 위치라는 점을 유의하며 Enque_f와 Deque_r만 추가하니 크게 어려운 점은 없었다.

이때 위치를 유의하며 줄였던 값을 다시 늘리는 부분을 주의해야한다.

int Deque_r(IntQueue *q, int *x) {
  if (q->num <= 0)
    return -1;
  else {
    q->num--;
    *x = q->que[--q->rear];
    if (q->rear++ == q->max) //줄였던 값을 다시 늘리고 비교해 실행 시 변수의 영향을 받지 않도록 함
      q->rear = 1;
    return 0;
  }
}

또한 철자가 비슷하다고 해서 디큐(De-queue)와 덱(Deque)를 혼동해서는 안된다.

스택과 큐 그리고 덱까지 직접 구현해보고 사용까지 해봤다.

다음 포스트에선 재귀에 대해 다뤄보도록 하겠다.