큐

큐의 정의

 

큐는 먼저들어간 데이터가 먼저 나오고, 나중에 나온 데이터가 나중에 나오는 자료구조이다.

 

큐는 운영체제 관점에서 보면 프로세스나 스레드의 관리에 활용이 되는 자료구조이다. 이렇듯 운영체제의 구현에도 자료구조가 사용된다. 따라서 운영체제의 이해를 위해서는 자료구조에 대한 이해가 선행되어야 한다.

 

 

큐의 ADT 정의

 

 

ADT를 대상으로 배열기반의 큐 또는 연결리스트 기반의 큐를 구현할 수 있다.

 

 

 

원형큐의 구조

 

아래와 같은상황은 F 와 R이 같은 위치를 가리키는 상태가 텅빈 상태를 나타낸다.

 

enqueue 연산시, R이 가리키는 위치를 한칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다.

 

dequeue연산시, F가 가리키는 위치를 한칸 이동 시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

 

여기서 dequeue 연산 시에도 F가 가리키는 위치를 우선 한칸 이동한다는 사실을 잊으면 안된다. 

 

정리

 

원형큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다.

 

원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.

 

 

원형큐의 헤더

 

 

 

CircularQueue.h

 

#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__

#define TRUE	1
#define FALSE	0

#define QUE_LEN	100
typedef int Data;

typedef struct _cQueue
{
	int front;
	int rear;
	Data queArr[QUE_LEN];
} CQueue;

typedef CQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 

CircularQueue.c

 

#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"

void QueueInit(Queue * pq) //텅빈 경우, front와 rear은 동일 위치 가리킴
{
	pq->front = 0;
	pq->rear = 0;
}

int QIsEmpty(Queue * pq)
{
	if(pq->front == pq->rear)   //큐가 텅 비었다면
		return TRUE;
	else
		return FALSE;
}

/*
 큐의 연산에 의해서 F(front)와 R(rear)이 이동할때
 이동해야 할 위치 를 알려주는 함수!
 원형 큐를 완성하게 하는 실질적인 함수이다!
 위 함수의 정의를 통해서 원형 큐의 나머지 구현은 매우 간단해진다.
 */
int NextPosIdx(int pos)
{
	if(pos == QUE_LEN-1)    //배열의 마지막 요소의 인덱스 값이라면
		return 0;
	else
		return pos+1;
}


void Enqueue(Queue * pq, Data data)
{
	if(NextPosIdx(pq->rear) == pq->front) //큐가 꽉 찼다면
	{
		printf("Queue Memory Error!");
		exit(-1);
	}
    
    //rear을 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치에 데이터 저장
	pq->rear = NextPosIdx(pq->rear);
	pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

    //front를 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치의 데이터 반환
	pq->front = NextPosIdx(pq->front);
	return pq->queArr[pq->front];
}

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->queArr[NextPosIdx(pq->front)];
}

 

main. c

 

#include <stdio.h>
#include "CircularQueue.h"

int main(void)
{
	//큐의 생성 및 초기화
	Queue q;
	QueueInit(&q);

	// 데이터 넣기
	Enqueue(&q, 1);  Enqueue(&q, 2);
	Enqueue(&q, 3);  Enqueue(&q, 4);
	Enqueue(&q, 5);

	// 데이터 꺼내기
	while(!QIsEmpty(&q))
		printf("%d ", Dequeue(&q)); 

	return 0;
}

 

 

 

큐의 연결 리스트 기반 구현

 

초기화

 

 

 

enqueue

 

 

 

 

dequeue 논리

 

 

 

dequeue 정의

 

 

코드

 

ListBaseQueue.h

 

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _lQueue
{
	Node * front;
	Node * rear;
} LQueue;

typedef LQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 

ListBaseQueue.c

 

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"

void QueueInit(Queue * pq)
{
	pq->front = NULL;
	pq->rear = NULL;
}

int QIsEmpty(Queue * pq)
{
	if(pq->front == NULL)
		return TRUE;
	else
		return FALSE;
}

void Enqueue(Queue * pq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->data = data;

	if(QIsEmpty(pq))
	{
		pq->front = newNode;
		pq->rear = newNode;
	}
	else
	{
		pq->rear->next = newNode;
		pq->rear = newNode;
	}
}

Data Dequeue(Queue * pq)
{
	Node * delNode;
	Data retData;

	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	delNode = pq->front;
	retData = delNode->data;
	pq->front = pq->front->next;

	free(delNode);
	return retData;
}

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->front->data;
}

 

 

ListBaseQueueMain.c

 

#include <stdio.h>
#include "ListBaseQueue.h"

int main(void)
{
	
	Queue q;
	QueueInit(&q);


	Enqueue(&q, 1);  Enqueue(&q, 2);
	Enqueue(&q, 3);  Enqueue(&q, 4);
	Enqueue(&q, 5);


	while(!QIsEmpty(&q))
		printf("%d ", Dequeue(&q)); 

	return 0;
}

 

 

Chapter 07 ť(Queue).pdf

1.20MB

Ch07.zip

0.02MB

 

 

 

 

 

참고 : 윤성우의 열혈 자료구조 도서