C언어 원형큐

(C언어 원형 큐에서 넘어옴)

1 개념[ | ]

Circular Queue, 원형 큐
  • C언어 원형 큐 구현

2 예시[ | ]

  • 10개의 값을 가지는 큐를 생성한다.
  • 큐가 가득 찰 때까지 0부터 채운다.
  • 가득찬 큐를 출력하면서 비운다.
  • 참고1) 큐는 rear로 값을 넣고 front로 값을 뺀다.
  • 참고2) 큐가 비었을 때는 rear와 front가 같은 값을 가지고, 큐가 가득 찼을 때는 rear+1이 front와 같은 값을 가진다.
#include <stdio.h>
#include <stdlib.h>

typedef struct { 
	int a;
} nodeType;

typedef struct {
	int size;
	int front; 
	int rear; 
	nodeType *nodes;
} queueType;

void createQueue(queueType **queue, int size)
{
	*queue = (queueType *)malloc(sizeof(queueType));
	
	(*queue)->front = 0;
	(*queue)->rear = 0;
	(*queue)->size = size;
	
	(*queue)->nodes = (nodeType *)malloc(sizeof(nodeType) * (size + 1));
}

void enQueue(queueType *queue, int a)
{
	int pos = queue->rear;
	
	if (queue->size == queue->rear)
		queue->rear = 0;
	else
		queue->rear++;

	queue->nodes[pos].a = a;
}

int deQueue(queueType *queue)
{
	int pos = queue->front;

	if (queue->size == queue->front)
		queue->front = 0;
	else
		queue->front++;

	return queue->nodes[pos].a;
}

int isFull(queueType *queue)
{
	int curSize, front, rear;

	if (queue->rear < queue->front)
		rear = queue->rear + queue->size + 1;
	else
		rear = queue->rear;

	front = queue->front;

	curSize = rear - front;

	if (curSize == queue->size)
		return 1;
	else 
		return 0;
}

int isEmpty(queueType *queue)
{
	if (queue->front == queue->rear)
		return 1;
	else
		return 0;
}

int main()
{
	int i = 0;
	queueType *queue;
	createQueue(&queue, 10);

	while (!isFull(queue)) {
		enQueue(queue, i++);
	}
	
	while (!isEmpty(queue)) {
		printf("%d\t", deQueue(queue));
	}
}

3 같이 보기[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}