[Data Structure] #선형큐(Linear Queue), 원형큐(Circular Queue), 덱(Deque) - C언어

안녕하세요. 이번 시간에는 선형큐, 원형큐 그리고 덱에 대해 알아보겠습니다. 원형큐와 선형큐의 기능은 덱이 모두 가지고 있기 때문에 구현은 덱만 해보도록 하겠습니다.

선형큐(Linear Queue)

일반적으로 많이 알고 있는 1차원 배열을 이용한 자료구조입니다. front, rear를 활용해 삽입, 삭제를 구현합니다.

• front는 첫번째 요소의 인덱스보다 하나 적으며 요소를 삭제할 경우 front를 하나 증가시킵니다.
• rear는 맨 마지막 요소의 인덱스를 가르키며, 삽입할 경우 rear 먼저 +1 증가시킨 후에 요소를 삽입합니다.

원형큐(Circular Queue)

원형큐에서 front와 rear의 역할은 앞서 선형큐에서 설명했던 것과 같습니다. 하지만 front 혹은 rear를 다시 할당할 때 큐의 크기 값으로 나눈 뒤에 할당해야 합니다.

원형큐의 논리적인 모델은 원이지만 물리적으로 메모리에서는 선형으로 구현되어 있기 때문입니다. 사이즈를 넘어가는 주소를 참조하려 하면 다시 처음 주소로 가기 위함이죠.

참고로 현재 요소의 개수를 나타내는 변수를 활용할 수 없다면 자리 1개를 비워야합니다. 그렇지 않으면 요소가 가득찼는지 비었는지를 알 수가 없습니다.

덱(Deque)

덱은 삽입과 삭제 연산을 앞과 뒤에서 자유롭게 할 수 있는 자료구조입니다. 스택과 큐의 연산을 모두 가지고 있기 때문에 좀 더 유연하게 사용할 수 있는 자료구조라고 이해하면 될 것 같습니다.

덱에서도 마찬가지로 front와 rear가 같은 역할을 하며 원형큐에서 쓰이는 연산을 대부분 활용합니다.

다른 점은 front와 rear에 다시 할당할 때 덱의 크기를 더한 뒤에 나눠줘야 합니다. 앞에서 삽입 연산이 이뤄지면 덱이 차지하고 있는 메모리 주소를 벗어날 경우가 있기 때문이죠. 따라서 이를 막기 위함입니다.

front = (front + 덱의 크기) % 덱의 크기
rear = (rear+ 덱의 크기) % 덱의 크기

구현

그럼 c언어로 덱을 구현해봅시다.

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

#define MAX_DEQUE_SIZE 5

typedef struct {
  int front;
  int rear;
  int data[MAX_DEQUE_SIZE];
} Deque;

void init_deque(Deque *q) {
  q->front = q->rear = 0;
}

int is_empty(Deque *q) {
  return (q->front == q->rear);
}

int is_full(Deque *q) {
  return (q->rear + 1) % MAX_DEQUE_SIZE == q->front;
}

void print_deque(Deque *q) {
  printf("front: %d | rear: %d\n", q->front, q->rear);
  if (is_empty(q)) {
    printf("none");
    exit(1);
  }

  int i = (q->front + 1) % MAX_DEQUE_SIZE;

  while(1) {
    printf("%d | ", q->data[i]);
    if (i == q->rear) break;
    i = (i + 1) % MAX_DEQUE_SIZE;
  }
}

void add_rear(Deque *q, int item) {
  if (is_full(q)) {
    printf("deque가 가득찼습니다. rear");
     exit(1);
  }
  q->rear = (q->rear + 1) % MAX_DEQUE_SIZE;
  q->data[q->rear] = item;
}

int delete_rear(Deque *q) {
  if (is_empty(q)) {
    printf("deque가 비었습니다. rear");
     exit(1);
  }
  int prev = q->rear;
  q->rear = (q->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
  return q->data[prev];
}

void add_front(Deque *q, int item) {
  if (is_full(q)) {
    printf("deque가 가득찼습니다. front");
    exit(1);
  }
  q->data[q->front] = item;
  q->front = (q->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
}

int delete_front(Deque *q) {
  if (is_empty(q)) {
    printf("deque가 비었습니다. front");
    exit(1);
  }
  q->front = (q->front + 1) % MAX_DEQUE_SIZE;
  return q->data[q->front];
}

int main(void) {
  Deque deque;
  init_deque(&deque);

  add_front(&deque, 10);
  add_front(&deque, 20);
  add_front(&deque, 30);
  add_front(&deque, 40);
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  add_rear(&deque, 100);
  add_rear(&deque, 200);
  add_front(&deque, 50);
  add_front(&deque, 60);
  print_deque(&deque);

  return 0;
}