자료구조 - 큐

큐

큐는 FIFO 구조로 First In First Out, 선입선출, 먼저 삽입된것이 먼저 출력되는 구조입니다.

큐에서 출력될 자료를 가리키고 있는 포인터를 front(head)라고 하고,

삽입될 위치를 가리키고 있는 포인터를 rear(tail)라고 합니다.

 

큐도 스택구조와 마찬가지로 삽입과 출력을 할수있는데요,

삽입하는것을 put, 출력하는것을 get으로 구현합니다.

 

큐는 일회성이라는것이 특징입니다.

 

아래 큐의 동작과정을 보시면 알겠지만,

한번 사용된 공간은 다시 사용하지 않아서 큐의 구조는 일회성이라는 단점이 있습니다.

 

 

Put(A)

put(B)

get(A)

get(B)

put(C)

					(rear)
		(rear)	(rear)	(rear),(front)	[C](front)
	(rear)	[B]	[B](front)
(front),(rear)	[A](front)	[A](front)

 

 

 

 

하지만 위에서말한 선형큐의 단점을 보환하여 만들어진게

바로 환형(원형)큐 인데요,

 

위의 그림과 같은 구조로 보시면 됩니다.

 

큐의 마지막 위치까지 도달했을시 처음 주소로 돌아가

다시 자료를 삽입하는 구조로 이루어져 있습니다.

 

 

이런 큐를 어디다 사용하나?

큐의 자료구조는 웹사이트,컴퓨터,프로그래밍 등 어디에나 있습니다.

 

Buffer!

동영상을 재생하실때 흔히보시는 버퍼링!

이것이 바로 큐 구조로 이루어져 있는것입니다.

 

버퍼링 작업을 하여 큐에 동영상 데이터를 저장하고 플레이어를 통해 큐의 앞부분부터 재생하고,

만약 버퍼링 작업이 재생속도보다 느려서 큐에 저장된 데이터가 없으면,

재생을 멈추고 다시 버퍼링을 하게 됩니다.

 

또, CPU 의 처리과정, 프린트에 문서작성, 스트림 버퍼등 다양한곳에 쓰이고 있습니다.

 

큐는 순차적인 업무처리를 위해 다음할일을 기억해두는 자료구조,장치 라고만

기억하시면 될듯합니다.

 

 

 

아래는 환형 큐 구조를 코딩해본것입니다.

한번 보면서 공부해보시는것도 도움이 되실거에요

#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)

int main(){
 int queue[5];
 int *front = queue;
 int *rear = queue;
 char command[10];
 int input;
  while (1){
   printf("input the command\n");
   scanf(" %s", command);
   printf("\n");

   if (!strcmp("push",command)){

    if (front == &queue[0]){
     if (&queue[4] == rear){
      printf("queue is overflow!\n");
      continue;
     }
    }else if (front - 1 == rear){
      printf("queue is overflow!\n");
      continue;
    }
    printf("Enter the input data\n");
     scanf("%d", &input);
     printf("\n\n");
     *rear = input;
     if (rear == &queue[4]){
      rear = &queue[0];
     }
     else{
      rear++;
     }
   }
   else if (!strcmp("pop", command)){
    if (rear == front){
     printf("\nQueue is underflow!\n");
     continue;
    }
     printf("\n\n pop the data : %d \n\n", *front);
     *front = 0;
     if (front == &queue[4]){
      front = &queue[0];
     }
     else{
      front++;
     }
   }
   else if (!strcmp("exit", command)){
    break;
   }
  }
  return 0;
}

 

동작과정

 

 

 

 

 

 

 

아래는 좀더 환형큐를 이해하기 쉽도록 눈으로 볼수있게

 코딩해놓은 소스입니다.

#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)

int main(){
 int queue[5] = { 0, };
 int *front = queue;
 int *rear = queue;
 char command[10];
 int input;
 printf("-- is front, - is rear\n");
  while (1){
   scanf(" %s", command);
   printf("\n");

   if (!strcmp("push",command)){

    if (front == &queue[0]){
     if (&queue[4] == rear){
      printf("queue is overflow!\n");
      continue;
     }
    }else if (front - 1 == rear){
      printf("queue is overflow!\n");
      continue;
    }
     scanf("%d", &input);
     printf("\n\n");
     *rear = input;
     if (rear == &queue[4]){
      rear = &queue[0];
     }
     else{
      rear++;
     }
   }
   else if (!strcmp("pop", command)){
    if (rear == front){
     printf("\nQueue is underflow!\n");
     continue;
    }
     printf("\n\n pop the data : %d \n\n", *front);
     *front = 0;
     if (front == &queue[4]){
      front = &queue[0];
     }
     else{
      front++;
     }
   }
   else if (!strcmp("exit", command)){
    break;
   }

 

   printf("          ");
   if (front ==&queue[0]){
    printf("-- ");
   }
   else{
    printf("   ");
   }
   if (queue[0] == 0){
    printf("○");
   }
   else{
    printf("●");
   }
   if (rear == &queue[0]){
    printf(" -");
   }
   else{
    printf("  ");
   }
   printf("\n\n");

   printf("     ");
   if (front == &queue[4]){
    printf("-- ");
   }
   else{
    printf("   ");
   }
   if (queue[4] == 0){
    printf("○");
   }
   else{
    printf("●");
   }
   if (rear == &queue[4]){
    printf(" -");
   }
   else{
    printf("  ");
   }
   printf("  ");
   if (front == &queue[1]){
    printf("-- ");
   }
   else{
    printf("   ");
   }
   if (queue[1] == 0){
    printf("○");
   }
   else{
    printf("●");
   }
   if (rear == &queue[1]){
    printf(" -");
   }
   else{
    printf("  ");
   }
   printf("\n\n");
   printf("       ");
   if (front == &queue[3]){
    printf("-- ");
   }
   else{
    printf("   ");
   }
   if (queue[3] == 0){
    printf("○");
   }
   else{
    printf("●");
   }
   if (rear == &queue[3]){
    printf("-");
   }
   else{
    printf(" ");
   }
   if (front == &queue[2]){
    printf("--");
   }
   else{
    printf("  ");
   }
   if (queue[2] == 0){
    printf("○");
   }
   else{
    printf("●");
   }
   if (rear == &queue[2]){
    printf(" -");
   }
   else{
    printf("  ");
   }
   printf("\n");
  }
  return 0;
}