[자료구조] 순차 자료구조를 이용한 큐의 구현.

[자료구조] 순차 자료구조를 이용한 큐의 구현.

1. 선형 큐

1차원 배열을 사용하는 순차 자료구조로 큐를 구현해보자. 이때 배열의 크기는

큐의 크기, 즉 큐에 저장할 수 있는 최대 원소 갯수가 된다. 그리고 배열에 저장

된 원소 중에서, 첫 번째 원소의 인덱스를 저장할 front 변수와 저장된 마지막

원소의 인덱스를 저장할 rear 변수를 사용한다. 초기 공백 큐의 상태는 front 변

수와 rear 변수의 값을 -1로 설정한다.

정리된 소스는 아래와 같다... ( 정말 간단히 구현만 했다. )

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

#define Q_SIZE 100

char queue[Q_SIZE] ;

int front, rear ;

void enQueue( char item)
{
 if(rear == Q_SIZE -1 )
 {
  printf("\nQueue is full!\n" ) ;
  return ;
 }else
 {
  rear++ ;
  queue[rear] = item ;
 }
}

void deQueue()
{
 if( front == rear )
 {
  printf("\nQueue is empty!\n" ) ;
  return ;
 }else
 {
  front++ ;
 }
}

void printfQueue()
{
 printf("Queue : [") ;
 for(int i = front+1; i <= rear ; ++i )
  printf("%3c", queue[i]) ;

 printf(" ] \n") ;
}

void main()
{
 front = -1 ;
 rear = -1 ;

 enQueue('a') ;
 printfQueue() ;

 enQueue('b') ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;

 enQueue('c') ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;

 deQueue() ;
 printfQueue() ;
}

실행해 보면..

위와 같은 결과가 나온다...

하지만 위와 같은 소스는, 배열에 모든 정보가 꽉 찬 이후에는 동작을 하지 않

는다.. 바로 그 것을 해결하기 위해 나온 것이 원형 큐다..

2. 원형 큐

위의 선형 큐와 같은 경우는 rear가 배열의 마지막 위치에 있게 되면 큐에 빈자

리가 있는데도 포화 상태로 인식하고 삽입연산을 수행하지 않는다.

원형 큐는 선형 큐와 마찬가지로 1차원 배열을 사용하는데, 논리적으로 배열의

처음과 끝이 연결되어 있다고, 생각하는 것이다.

원형 큐에서는 초기 공백 상태일 때 front와 rear의 값이 0이 되고, 공백 상태와

포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둔다. 원형 큐에서의

공백 상태는 front = rear 가 된다. rear가 앞으로 이동하면서 원소를 삽입하고,

front는 rear가 이동한 방향으로 따라가면서 원소를 삭제한다. 원형 큐에서는 배

열의 인덱스가 n-1 다음에 다시 0이 되어야 하므로 사용할 인덱스를 정하기 위

해서 나머지 연산자 mod를 사용한다.

원형 큐는 위의 소스를 바탕으로 직접 해보길 바란다.

[자료구조] 순차 자료구조를 이용한 큐의 구현.