큐(Queue)

어느 한쪽으로는 데이터의 입력이 이루어지고, 다른 한 쪽에서 데이터의 삭제가 이루어지는 구조. 
선입선출(FIFO; First-In First-Out)구조라고도 함.
큐를 표현하기 위한 조건
- 전위 포인터(front pointer) : 큐의 실제 위치보다 1이 작은 위치를 가리킨다.
- 후위 포인터(rear pointer) : 큐에 마지막으로 삽입된 원소를 가리킨다
- 큐의 공백조건 : front = rear
- overflow 조건 : rear >= n(큐가 원소를 저장할 수 있는 개수)
- 초기 조건 : front = rear = 0 

// Queue.cpp 배열을 이용하여 구현

#include <stdio.h>

#include <stdlib.h>

#define MAX 5

typedef struct {

int key; // 큐의 구조

} element;

element queue[MAX]; // 큐 구조 배열 선언

int rear = -1; // queue를 가동할 index 변수

int front = -1;

void InsertQ(element item);

element DeleteQ();

void queue_full(element item);

element queue_empty();

void main()

{

int n, i;

element item;

while(1)

{

printf("\n 1. Insert 2. Delete (stop : otherwise) = ");

scanf("%d", &n);

switch(n)

{

case 1:

printf("\nInsert item = ");

scanf("%d", &item);

InsertQ(item);

break;

case 2:

printf("\nDelete item = %d", DeleteQ());

break;

default : exit(0);

}

// 현재 queue내용 출력

printf("\n\nQueue List");

for(i=front+1; i<=rear; i++)

{

printf("\nQueue[%d] = %d", i, queue[i]);

}

}

}

void InsertQ(element item)

{

// queue의 공간이 가득차면, overflow 함수 호출

if(rear == (MAX-1))

{

queue_full(item);

return;

}

queue[++rear] = item;

return;

}

element DeleteQ()

{

// queue의 공간에 자료가 없다면, empty 함수 호출

if(front==rear)

{

return queue_empty();

}

//큐의 자료를 삭제(front의 내용을 반환)

return queue[++front];

}

void queue_full(element item)

{

// 빈 공간이 있으면 앞쪽으로 자료를 이동하여 최적화시킴

int i;

// front쪽에도 빈 공간이 없으면 가득찼다는 메시지 출력

if(front==(-1))

{

printf("Queue is Full!");

return;

}

rear = rear-front;

for(i=0; i<rear; i++)

queue[i] = queue[++front];

front = -1;

queue[rear] = item;

return;

}

element queue_empty()

{

element err;

err.key = NULL;

printf("Queue is Empty !!");

return (err);

}