hahahia

큐(Queue) 본문

Data Structure

큐(Queue)

hahahia 2012. 3. 2. 23:56
어느 한쪽으로는 데이터의 입력이 이루어지고, 다른 한 쪽에서 데이터의 삭제가 이루어지는 구조. 
선입선출(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);

'Data Structure' 카테고리의 다른 글

Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
스택(stack)  (0) 2012.02.19
Comments