자료구조 큐(Queue) 기초 개념정리

큐(Queue)란

큐는 스택과 같은 자료구조로서 스택과의 유일한 차이는 먼저들어간 데이터가 먼저 나오는 구조입니다. 이 구조는 비유하자면 먼저 들어간 차가 먼저 나오는 터널이 있다. 

FIFO(First-In, First-Out): 선입선출 

큐 역시 스택과 마찬가지로 배열 또는 연결리스트를 기반으로한 구현이 가능하다.

---

Queue의 ADT

QueueInit: 제일 먼저 호출해야하는 함수로서 큐의 초기화를 수행한다.

QIsEmpty: 큐가 비었는지 확인하는 함수이다. 비었으면 TRUE, 비어있지않으면 FALSE를 반환한다.

Enqueue: 큐에 데이터를 저장하는 함수로서 매개변수로 전달받은 데이터를 저장한다. 스택의 push와 같은 역활이다.

Dequeue: 가장 앞선 데이터를 삭제하는 함수로서, 삭제된 데이터를 반환한다. 스택의 pop과 같은 역활이다.

QPeek: 가장 앞선 데이터를 반환한다. (삭제X)

배열을 기반으로 구현한 큐

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1		
#define FALSE 0
#define LEN 100		//배열의 길이 선언
typedef int Data;

typedef struct _cQueue		//구조체 큐 선언
{
	int front;		//front는 먼저 들어온 데이터를 반환할때 가리키게 된다.
	int rear;		//rear는 데이터를 삽입할때 사용된다.
	Data queArr[LEN];
}CQueue;

typedef CQueue Queue;

void QueueInit(Queue* pq)		//큐 초기화함수
{
	pq->front = 0;
	pq->rear = 0;
}

int QIsEmpty(Queue* pq)		//큐가 비었는지 확인한다. 
{
	if (pq->front == pq->rear)		//front와 rear가 같다는것은 같은곳을 가리키고 있는것이기때문에 비어있는것이다.
		return TRUE;
	else
		return FALSE;
}

int NextPosIdx(int pos)		//이 함수는 가득찬 경우를 확인하는 경우와 데이터를 삽입 및 삭제할때 front 와 rear의 위치변경을 위한 함수
{
	if (pos == LEN - 1)
		return 0;
	else
		return pos + 1;
}

void Enqueue(Queue* pq, Data data)		//데이터를 삽입하는 함수이다.
{
	if (NextPosIdx(pq->rear) == pq->front)
	{	
		printf("큐가 가득찼습니다.");
		exit(1);
	}

	pq->rear = NextPosIdx(pq->rear);
	pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue* pq)		//데이터를 삭제하는 함수이다.
{
	if (QIsEmpty(pq))
	{	
		printf("큐가 비었습니다.");
		exit(1);
	}
	pq->front = NextPosIdx(pq->front);
	return pq->queArr[pq->front];
}

Data QPeek(Queue* pq)	//데이터를 보여주는 함수이다.
{
	if (QIsEmpty(pq))
	{
		printf("큐가 비었습니다.");
		exit(1);
	}
	return pq->queArr[NextPosIdx(pq->front)];
}

int main()
{
	Queue queue;
	QueueInit(&queue);

	Enqueue(&queue, 1);		//1, 2, 3 삽입
	Enqueue(&queue, 2);
	Enqueue(&queue, 3);

	while (!QIsEmpty(&queue))		//while문을 사용하여 큐의 모든 데이터를 반환
	{
		printf("%d ", Dequeue(&queue));
	}

	return 0;
}

front와 rear가 각각 필요한 이유는 Enqueue함수와 Dequeue함수가 수행되는 위치가 각각 다르기 때문이다.

 

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