[자료구조] c언어로 큐, 원형 큐 구현하기

profile image pIutos 2022. 11. 3. 14:10

큐(Queue)란?

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 선입선출(FIFO: First-In First-Out)한다는 특징이 있고, 매표소나 계산대의 대기열을 생각해보면 이해하기 쉬울 것이다.
이번 글에서는 큐와 큐의 더 발전된 형태인 원형 큐도 구현해 보겠다.

큐 타입 구조체 정의 및 초기화 함수

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

#define SIZE 100

typedef char element;

typedef struct
{
  element data[SIZE];
  int rear, front;
} QueueType;

void init(QueueType *Q)
{
  Q->rear = Q->front = -1;
}

큐의 요소에 해당하는 data 배열과, 큐의 가장 앞과 뒤에 해당하는 front, rear이 포함된 QueueType 구조체를 선언한다.

에러체크함수 is_empty(), is_full()

에러체크함수 is_empty는 아무것도 차있지 않은 상태, 즉 front와 rear가 같은지 살핀다.

is_full은 큐가 가득 차있는 상태인 rear가 size -1이 같은지 살핀다. -1을 하는 이유는 큐 data 배열은 0부터 시작하기때문이다.

int is_empty(QueueType *Q)
{
  return Q->front == Q->rear;
}

int is_full(QueueType *Q)
{
  return Q->rear == SIZE - 1;
}

삽입함수 enqueue()

삽입을 하기위해 rear을 한칸 움직이고, 데이터를 한칸 움직인 공간에 삽입한다.

void enqueue(QueueType *Q, element e)
{
  if (is_full(Q))
    printf("Overflow\n");
  else
  {
    Q->rear++;

    Q->data[Q->rear] = e;
  }
}

삭제함수 dequeue()

가장 먼저 들어온 데이터부터 삭제해야하므로 front를 한칸 움직이고 데이터를 return한다.

element dequeue(QueueType *Q)
{
  if (is_empty(Q))
  {
    printf("Empty\n");
    return 0;
  }
  else
  {
    Q->front++;
    return Q->data[Q->front];
  }
}

큐 출력함수 print()

void print(QueueType *Q)
{
  printf("Front Pos : %d\n, Rear Pos : %d\n", Q->front, Q->rear);
  for (int i = Q->front + 1; i <= Q->rear; i++)
  {
    printf("[%c] ", Q->data[i]);
  }
  printf("\n");
}

 

큐의 단점?

큐를 사용하면 할수록 front가 뒤로 밀려나게 되므로 마지막 공간의 front와 Rear가 같아지게 되어 삭제된 front 앞의 공간(이전에 할당된 공간)은 쓸 수 없게 된다.

원형 큐(Circular Queue)

큐의 이미 사용한 앞 공간은 쓸수 없다는 단점을 보완하기 위해 원형 큐를 사용할 수 있다. 원형 큐를 구현하기 위해서는 앞서 구현한 큐에서 일부 코드만 수정하면 된다.

에러체크함수 is_empty(), is_full()

is_empty함수는 큐의 코드와 동일하고, is_full함수는 공백 상태와 구분하기 위해서 한 칸 비워둔다. 그리고 원형큐를 구현하기 위해서는 나머지 모듈러 연산이 필요하다.(front == rear + 1을 전체 size로 나눈 나머지)

한 칸 비워두지 않으면 0번 index에 front==rear인 경우 공백 상태와 포화 상태가 중복되어서 구분할 수 없기 때문이다.

int is_empty(QueueType *Q)
{
  return Q->front == Q->rear;
}

int is_full(QueueType *Q)
{
  return Q->front == (Q->rear + 1) % SIZE;
}

삽입함수 enqueue()

삽입함수는 rear를 1만큼 증가시킨 값과 size와의 나머지로 설정하고 데이터를 저장한다.

예를들어 현재 rear가 4이고, size가 8이라면 (4 + 1) % 8 = 5번 인덱스, rear가 7이라면 (7 + 1) % 8 = 0번 인덱스에 위치한다.

void enqueue(QueueType *Q, element e)
{
  if (is_full(Q))
    printf("Overflow\n");
  else
  {
    Q->rear = (Q->rear + 1) % SIZE;

    Q->data[Q->rear] = e;
  }
}

삭제함수 dequeue()

삽입함수와 마찬가지로 front를 증가시키고 데이터를 return한다.

element dequeue(QueueType *Q)
{
  if (is_empty(Q))
  {
    printf("Empty\n");
    return 0;
  }
  else
  {
    Q->front = (Q->front + 1) % SIZE;
    return Q->data[Q->front];
  }
}

원형큐 출력함수 print()

출력함수 print()는 while문을 통해 i값을 front부터 rear까지 순차적으로 증가시키면서 출력한다.

void print(QueueType *Q)
{
  printf("Front Pos : %d\n, Rear Pos : %d\n", Q->front, Q->rear);
  int i = Q->front; // 제일 앞에있는 원소 바로 하나 전부터 시작
  while (i != Q->rear)
  {
    i = (i + 1) % SIZE;
    printf("[%c]", Q->data[i]);
  }
  printf("\n");
}

전체 코드

큐 (더보기)

더보기 
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

typedef char element;

typedef struct
{
  element data[SIZE];
  int rear, front;
} QueueType;

void init(QueueType *Q)
{
  Q->rear = Q->front = -1;
}

int is_empty(QueueType *Q)
{
  return Q->front == Q->rear;
}

int is_full(QueueType *Q)
{
  return Q->rear == SIZE - 1;
}

void enqueue(QueueType *Q, element e)
{
  if (is_full(Q))
    printf("Overflow\n");
  else
  {
    Q->rear++;

    Q->data[Q->rear] = e;
  }
}

element dequeue(QueueType *Q)
{
  if (is_empty(Q))
  {
    printf("Empty\n");
    return 0;
  }
  else
  {
    Q->front++;
    return Q->data[Q->front];
  }
}

void print(QueueType *Q)
{
  printf("Front Pos : %d\n, Rear Pos : %d\n", Q->front, Q->rear);
  for (int i = Q->front + 1; i <= Q->rear; i++)
  {
    printf("[%c] ", Q->data[i]);
  }
  printf("\n");
}

int main()
{
  QueueType Q;
  init(&Q);
  
  enqueue(&Q, 'A');
  enqueue(&Q, 'B');
  enqueue(&Q, 'C');
  print(&Q);
  printf("[%c] \n", dequeue(&Q));
}

원형 큐 (더보기)

더보기 
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

typedef char element;

typedef struct
{
  element data[SIZE];
  int rear, front;
} QueueType;

void init(QueueType *Q)
{
  Q->rear = Q->front = 0;
}

int is_empty(QueueType *Q)
{
  return Q->front == Q->rear;
}

int is_full(QueueType *Q)
{
  return Q->front == (Q->rear + 1) % SIZE;
}

void enqueue(QueueType *Q, element e)
{
  if (is_full(Q))
    printf("Overflow\n");
  else
  {
    Q->rear = (Q->rear + 1) % SIZE;

    Q->data[Q->rear] = e;
  }
}

element dequeue(QueueType *Q)
{
  if (is_empty(Q))
  {
    printf("Empty\n");
    return 0;
  }
  else
  {
    Q->front = (Q->front + 1) % SIZE;
    return Q->data[Q->front];
  }
}

element peek(QueueType *Q)
{
  if (is_empty(Q))
  {
    printf("Empty\n");
    return 0;
  }
  return Q->data[(Q->front + 1) % SIZE];
}

void print(QueueType *Q)
{
  printf("Front Pos : %d\n, Rear Pos : %d\n", Q->front, Q->rear);
  int i = Q->front; // 제일 앞에있는 원소 바로 하나 전부터 시작
  while (i != Q->rear)
  {
    i = (i + 1) % SIZE;
    printf("[%c]", Q->data[i]);
  }
  printf("\n");
}

int main()
{
  QueueType Q;
  init(&Q);
  
  enqueue(&Q, 'A');
  enqueue(&Q, 'B');
  enqueue(&Q, 'C');
  print(&Q);
  printf("[%c] \n", dequeue(&Q));
}

 

도움이 되었다면 아래 '공감' 버튼을 눌러주세요! 읽어주셔서 감사합니다 :)

저작자표시 비영리 변경금지
'cs/자료구조'의 다른 글
more >