Queue

Queue 를 구현해 보았다.

Queue 는 FIFO 구조로 가장 먼저들어온 요소가 가장 먼저 나가게 된다.

그렇다보니 주로 Buffer 에서 자주 사용된다. Buffer 는 먼저 들어온 요소를 먼저 처리해야 하기 때문이다.

펌웨어의 경우 Task ISR 에서 Queue 라는 buffer 를 생성하여, 여러 Interrupt 에 따른 Signal 이 발생하였을 때

여러 Signal 을 Queue Buffer 에 저장해 두어 처리해 나아간다.

그렇게 해당 Task 는 Signal 을 받아 wait_Sig 에서 탈출하여 해당 Task 의 루틴을 동작하게 된다.

 

일반적인 Queue 의 경우 단점은 rear 이 메모리 끝에 도착했을 때, 데이터가 넉넉히 비어있음에도 불구하고 더 이상 삽입 할 수 없는 상황이 벌어진다.

이럴경우는 원형큐를 구현하면 말그래도 원형으로 꼬리를 물고 있음으로 메모리가 비어있다면 언제든 삽입이 가능하다.

 

아래 코딩은 구조체를 사용한 단순 Queue 를 만들어보았다. 아주 단순하게..

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

#define QUEUE_SIZE 10

typedef struct
{
	char data[QUEUE_SIZE];
	int front, rear;
}QueueType;

QueueType *CreateQueue()
{
	QueueType *NewQueue = (QueueType *)malloc(sizeof(QueueType));
	NewQueue->front = 0;
	NewQueue->rear = 0;

	return NewQueue;
}

bool Empty(QueueType *Q)
{
	if (Q->front == Q->rear)
	{
		printf("Queue Buffer is Empty\n");
		return 1;
	}
	else return 0;
}

bool Full(QueueType *Q)
{
	if (Q->rear == QUEUE_SIZE - 1)
	{
		printf("Queue Buffer is Full\n");
		return 1;
	}
	else return 0;
}

void PrintQueue(QueueType *Q)
{
	if (Empty(Q)) return;

	int i = Q->front;
	while (i != Q->rear)
	{
		printf("%3c", Q->data[i++]);
	}	
	printf("\n");
}

void enQueue(QueueType *Q, char strData)
{
	if (Full(Q)) return;

	Q->data[Q->rear++] = strData;
}

void deQueue(QueueType *Q)
{
	if (Empty(Q)) return;

	Q->data[Q->front++];
}

int main(void)
{
	QueueType *Q = CreateQueue();

	PrintQueue(Q);

	enQueue(Q, 'A');
	enQueue(Q, 'B');
	enQueue(Q, 'C');
	PrintQueue(Q);

	enQueue(Q, 'D');
	enQueue(Q, 'E');
	enQueue(Q, 'F');
	PrintQueue(Q);

	deQueue(Q);
	deQueue(Q);
	deQueue(Q);
	PrintQueue(Q);
	
	enQueue(Q, 'G');
	enQueue(Q, 'H');
	enQueue(Q, 'I');
	PrintQueue(Q);

	free(Q);
	getchar();

	return 0;
}

Queue 의 구현 결과