(2) Queue

Queue : FIFO(First In First Out) 구조를 가진 자료구조

<front, rear, enqueue, dequeue, circular queue>

front : 큐의 첫번째 원소

rear : 큐의 마지막 원소

enqueue : 큐에 데이터를 삽입하는 작업

dequeue : 큐에서 데이터를 꺼내오는 작업

circular queue : dequeue를 실행한 후 큐의 앞부분이 비어있어도 데이터를 삽입할 수 없는 문제점이 발생한다. 이 문제점을 해결하기 위해서 다음과 같이 queue의 front와 rear를 연결한 형태의 queue

array를 이용한 queue 구현

#define	MAX_SIZE 10
#define	boolean	unsigned char
#define	true	1
#define	false	0

typedef char Element;

// Global queue
Element queue[MAX_SIZE];
int front = 0;
int rear = 0;

void addq(Element e); 
Element deleteq();
void queue_show(); 

#include 
#include 
#include 
#include "arrayqueue.h"

void main () {

	char	c, e;

	printf("*********** Command **********\n");
	printf("+: AddQ c, -: DeleteQ, \n");
	printf("S: Show, Q: Quit \n");
	printf("******************************\n");

	while (1) {
		printf("\nCommand> ");
		c = getch();
		putch(c);
		c = toupper(c);

		switch (c) {
			case '+' : 
				e = getch();
				putch(e);
				addq(e);
				break;
			case '-' : 
				e = deleteq(); 
				printf("\n %c ", e);
				break;
			case 'S' : 
				queue_show(); 
				break;
			case 'Q' : printf("\n");
					   exit(1);
			default  : break;
		}
	}
}

void addq(Element e) 
{
	if (front == (rear+1)%MAX_SIZE) {
		printf ("\n Queue is full !!! \n");
		return;
	}
	rear = (rear+1)%MAX_SIZE;
	queue[rear] = e;
}

Element deleteq() 
{
	if (front == rear) {
		printf ("\n Queue is empty !!! \n");
		return NULL;
	}
	front = (front+1)%MAX_SIZE;
	return queue[front];
}

void queue_show() 
{
	int	i;

	if (front == rear) {
		printf ("\n Queue is empty !!! \n");
		return;
	}

	printf ( "\n" );
	// front+1에서 rear까지 circular 차례로 프린트 
	for (i=front; i!=rear; i = (i+1)%MAX_SIZE) 
		printf ( "%2c", queue[(i+1)%MAX_SIZE] );
	printf ( "\n" );
}

arrayqueue.cpp

arrayqueue.h