큐(queue)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 큐의 이해와 ADT 정의

• 선입선출의 자료구조 (FIFO: First In First Out)
• 큐의 ADT 정의

void QueueInit(Queue * pq);
- 큐의 초기화를 진행한다
- 큐 생성 후 제일 먼저 호출되는 함수

int QIsEmpty(Queue * pq);
- 큐가 빈 경우 TRUE, 아닌 경우 FALSE

void Enqueue(Queue *pq, Data data);
- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장

Data Dequeue(Queue *pq);
- 저장순서가 가장 앞선 데이터를 삭제
- 삭제된 데이터는 반환
- 본 함수의 호출을 위해서는 데이터가 존재

Data QPeek(Queue *pq)
- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않음
- 본 함수의 호출을 위해서는 데이터가 존재

2. 큐의 배열 기반 구현

2.1. 큐의 구현 논리

• 스택과는 다른 점이 앞에서 꺼내느냐 밖에 없다고 생각할 수 있지만 생각보다 차이가 있음
• enqueue

• dequeue

2.2. 원형 큐의 이해

• R과 F를 회전시켜 큐를 구성하는 방식

• 원형 큐의 enqueue와 dequeue

• F와 R의 위치로 가득 찬 경우와 빈 경우를 구분할 수 없음
• 그래서 배열을 가득 채우지 않고 배열의 길이가 N인 경우 데이터가 N-1개가 채워졌을 때 가득 찬 것으로 가정함
• 큐 구현 시의 연산
  • enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에 R이 가리키는 위치에 데이터를 저장
  • dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸
• 큐의 상태
  • 가득 찬 상태: R이 가리키는 위치의 앞을 F가 가리킨다.
  • 텅 빈 상태: F와 R이 동일한 위치를 가리킨다.

2.3. 원형 큐의 구현

• 헤더파일

#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);

• 큐 구현 코드

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

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

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);
	}
	
	pq->rear = NextPosIdx(pq->rear); // rear을 한 칸 이동
	pq->queArr[pq->rear] = data;  // rear이 가리키는 곳에 데이터 저장
}

Data Dequeue(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);	
	}
	
	pq->front = NextPosIdx(pq->front);  // front를 한 칸 이동
	return pq->queArr{pq->front];  // front가 가리키는 데이터 반환
	
}

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);		
	}
	
	return pq->queArr[NextPosIdx(pq->front)];
}

 

3. 큐의 연결 리스트 기반 구현

3.1. 연결 리스트 기반 큐의 헤더파일

typedef int Data;

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

typedef struct _lQueue
{
	int front;
	int 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);

3.2. 연결 리스트 기반 큐의 구현

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;  // front가 새 노드를 가리키게 하고
		pq->rear = newNode;   // rear도 새 노드를 가리키게 한다
	}
	else
	{
		pq->rear->next = newNode;  // 마지막 노드가 새 노드를 가리키게 하고
		pq->rear = newNode;  // rear가 새 노드를 가리키게 한다.
	}
}

• F가 다음 노드를 가리키게 한다.
• F가 이전에 가리키던 노드를 소멸시킨다.

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;  // 삭제할 노드의 다음 노드를 front가 가리킴
	
	free(delNode);
	return retData;
}

 

4. 덱(Deque)의 이해와 구현

4.1. 덱의 이해와 ADT 정의

• 덱의 기능
  • 앞으로 넣기
  • 뒤로 넣기
  • 앞에서 빼기
  • 뒤에서 빼기
• 덱 자료구조의 ADT

void DequeInit(Deque *pdeq);
- 덱의 초기화를 진행
- 덱 생성 후 제일 먼저 호출

int DQisEmpty(Deque *pdeq);
- 덱이 빈 경우 TRUE, 그렇지 않은 경우 FALSE 반환

void DQAddFirst(Deque *pdeq, Data data);
- 덱의 머리에 데이터를 저장, data로 전달된 값을 저장함

void DQAddLast(Deque *pdeq, Data data);
- 덱의 꼬리에 데이터를 저장, data로 전달된 값을 저장함

Data DQRemoveFirst(Deque *pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸

Data DQRemoveLast(Deque *pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸

Data DQGetFirst(Deque *pdeq);
- 덱의 머리에 위치한 데이터를 반환

Data DQGetLast(Deque *pdeq);
- 덱의 꼬리에 위치한 데이터를 반환

4.2. 덱의 구현

• 덱의 구현에 사용할 양방향 연결 리스트 구조

void DequeInit(Deque *pdeq)
{
	pdeq->head = NULL;
	pdeq->tail = NULL;
}

int DQisEmpty(Deque *pdeq)
{
	if(pdeq->head == NULL)  // head가 NULL이면 빈 덱
		return TRUE;
	else
		return FALSE;
}

void DQAddFirst(Deque *pdeq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	
	newNode->next = pdeq->head;
	
	if(DQisEmpty(pdeq))
		pdeq->tail = newNode;
	else
		pdeq->head->prev = newNode;
	
	newNode->prev = NULL;
	pdeq->head = newNode;
}

void DQAddLast(Deque *pdeq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prev = pdeq->tail;
	
	if(DQisEmpty(pdeq))
		pdeq->head = newNode;
	else
		pdeq->tail->next = newNode;
	
	newNode->next = NULL;
	pdeq->tail = newNode;
}

Data DQRemoveFirst(Deque *pdeq)
{
	Node * rnode = pdeq->head;
	Data rdata;
	if(DQIsEmpty(pdeq)){....}
	rdata = pdeq->head->data;
	
	pdeq->head = pdeq->head->next;
	free(rnode);
	
	if(pdeq->head == NULL)
		pdeq->tail = NULL;
	else
		pdeq->head->prev = NULL;
	
	return rdata;
}
- 덱의 머리에 위치한 데이터를 반환 및 소멸

Data DQRemoveLast(Deque *pdeq);
{
	Node * rnode = pdeq->tail;
	Data rdata;
	if(DQIsEmpty(pdeq)){....}
	rdata = pdeq->tail->data;
	
	pdeq->tail = pdeq->tail->prev;
	free(rnode);
	
	if(pdeq->tail == NULL)
		pdeq->head = NULL;
	else
		pdeq->tail->next = NULL;
	
	return rdata;
}

Data DQGetFirst(Deque *pdeq)
{
	if(DQIsEmpty(pdeq)){....}
	return pdeq->head->data;
}

Data DQGetLast(Deque *pdeq);
{
	if(DQIsEmpty(pdeq)){....}
	return pdeq->tail->data;
}

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)