Chapter07 큐(Queue)

2018/01/02 - [프로그래밍/자료구조] - Chapter06 스택(Stack)

07-1 큐의 이해와 ADT 정의

큐(Queue)의 이해

"먼저 들어간 것이 먼저 나온다!"

'선입선출 방식의 자료구조', 'FIFO(First-In, First-Out) 구조의 자료구조'

큐의 ADT 정의

큐의 핵심 연산은 enqueue(큐에 데이터를 넣는 연산),. dequeue(큐에서 데이터를 꺼내는 연산) 두 가지이다.

큐 자료구조의 ADT

void QueueInit(Queue *pq);

- 큐의 초기화를 진행한다.

- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.

int QIsEmpty(Queue *pq);

- 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void Enqueue(Queue *pq, Data data);

- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue *pq);

- 저장순서가 가장 앞선 데이터를 삭제한다.

- 삭제된 데이터는 반환이 된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue *pq);

- 저장순서가 가장 앞선데이터를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

07-2 큐의 배열 기반 구현

큐는 스택과 큰 차이를 보이지 않지만, 스택과 달리 고민할 것이 몇 가지 더 있다.

큐의 구현에 대한 논리

F(Front)큐의 머리, R(Rear) 큐의 꼬리를 사용해서 enqueue, dequeue를 처리한다.

큐의 특성 두가지

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

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

원형 큐(Circular Queue)의 구현

배열 기반의 큐라 하면 대부분의 경우 원형 큐를 의미한다.

07-03 큐의 연결 리스트 기반 구현

연결 리스트를 기반으로 구현하는 경우는 배열보다 신경 쓸 부분이 적다.

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

LisBaseQueue.h

/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/
#define TRUE	1
#define FALSE	0

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
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);

ListBaseQueue.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

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

int QIsEmpty(Queue *pq) {
	if (pq->front == NULL) {
		return TRUE;
	}
	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) {
	if (QIsEmpty(pq)) {
		printf("Queue is empty.");
		exit(1);
	}
	Node *temp = pq->front;
	Data retData = temp->data;
	pq->front = pq->front->next;
	free(temp);

	return retData;

}
Data QPeek(Queue *pq) {
	if (QIsEmpty(pq)) {
		printf("Queue is empty.");
		exit(1);
	}

	return pq->front->data;
}

ListBaseQueueMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "ListBaseQueue.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/

int main(void) {
	// Queue 초기화
	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));
	}
	printf("\n");
	return 0;
}

07-5 덱(Deque)의 이해와 구현

덱의 이해와 ADT의 정의

"덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조!"

deque은 double-ended queue를 줄여서 표현한 것으로, 양방향으로 넣고 뺄 수 있다.

덱의 핵심 함수는 앞으로 넣기, 뒤로 넣기, 앞에서 빼기, 뒤에서 빼기 총 네 가지의 기능이다.

덱자료구조의 ADT

void DequeInit(Deque *pdeq);

- 덱의 초기화를 진행한다.

- 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.

int DQIsEmpty(Deque *pdeq);

- 덱이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

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

- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.