7. 큐

※ 해당 글은 C언어에 대한 이해를 필요로 합니다. C 언어에 대해 알고 싶으신 분들은 다음 글을 참고하세요

https://ward.tistory.com/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4/C

'프로그래밍 언어/C' 카테고리의 글 목록

 

(1) 큐의 이해와 ADT 정의

 

* 큐의 이해

큐는 먼저 넣은 데이터가 먼저 나오는 자료구조이다.

-> First In First Out(FIFO)

큐

* 큐의 ADT 정의

Operation:

• 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)
  • 저장 순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
  • 본 함수의 호출을 위해서는 데이터가 하나 이생 존재함이 보장되어야 한다.

(2) 큐의 배열 기반 구현

 

* 큐의 구현에 대한 논리

enqueue 연산: 큐의 꼬리를 가리키는 Rear을 다음 칸을 가리키게 하고 그 자리에 새 데이터를 저장한다.

enqueue 연산

dequeue 연산: 큐의 머리를 가리키는 Front를 다음 칸을 가리키게 하고 그 앞의 데이터를 반환한다.

dequeue 연산

배열 기반 큐의 문제: 큐의 dequeue 연산을 수행할 때마다 큐의 용량이 줄어든다.

다음 같은 문제는 원형 큐로 해결할 수 있다.

 

* 원형 큐의 소개

큐의 시작과 끝을 연결하여 Rear와 Front가 순환하게 한다.

이러한 경우 그냥 구현을 하면 큐에 데이터가 꽉 찬 경우와 텅 빈 경우 모두 Front가 Rear보다 한 칸 앞 선 위치를 가리키기 때문에 둘을 Front와 Rear의 위치만 가지고 구별할 수 없다.

따라서 길이가 N인 배열을 큐로 사용하면 데이터가 N - 1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다.

원형 큐

* 원형 큐의 구현

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

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!\n");
		exit(-1);
	}
	pq->rear = NextPosIdx(pq->rear);
	pq->queArr[pq->rear] = data;
}

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

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

 

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

 

* 연결 리스트 기반 큐의 구현 논리

연결 리스트 기반의 스택은 push와 pop이 이뤄지는 위치가 같은 반면, 큐는 enquene와 dequeue가 이뤄지는 위치가 다르다.

 

* 연결 리스트 기반 큐의 구현

#include <stdio.h>
#include <stdlib.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) {
	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!\n");
		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!\n");
		exit(-1);
	}
	return pq->front->data;
}

 

(4) 덱의 이해와 구현

 

* 덱의 이해

덱: 앞과 뒤에서 삽입과 삭제가 가능한 큐이다.

덱

* 덱의 ADT 정의

Operation:

• void DequeInit(Deque* pdeq)
  • 덱의 초기화를 진행한다.
  • 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.
• int DQIsEmpty(Deque* pdeq)
  • 덱이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.
• void DQAddFirst(Deque* pdeq, Data data)
  • 덱의 머리에 데이터를 저장, data로 전달된 값을 저장한다.
• Data DQAddLast(Deque* pdeq)
  • 덱의 꼬리에 데이터를 저장, data로 전달된 값을 저장한다.
• Data DQRemoveFirst(Deque* pdeq)
  • 덱의 머리에 위치한 데이터를 반환 및 소멸한다.
• Data DQRemoveLast(Deque* pdeq)
  • 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.
• Data DQGetFirst(Deque* pdeq)
  • 덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.
• Data DQGetLast(Deque* pdeq)
  • 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.

* 덱의 구현

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

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct _dlDeque {
	Node* head;
	Node* tail;
}DLDeque;

typedef DLDeque Deque;

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

int DQIsEmpty(Deque* pdeq) {
	if (pdeq->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 (QIsEmpty(pdeq)) {
		printf("Queue Memory Error!\n");
		exit(-1);
	}
	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 DQRemoveFirst(Deque* pdeq) {
	Node* rnode = pdeq->tail;
	Data rdata;
	if (QIsEmpty(pdeq)) {
		printf("Queue Memory Error!\n");
		exit(-1);
	}
	rdata = pdeq->tail->data;
	pdeq->tail = pdeq->tail->next;
	free(rnode);
	if (pdeq->tail == NULL)
		pdeq->head = NULL;
	else
		pdeq->tail->next = NULL;
	return rdata;
}

Data DQGetFirst(Deque* pdeq) {
	if (QIsEmpty(pdeq)) {
		printf("Queue Memory Error!\n");
		exit(-1);
	}
	return pdeq->head->data;
}

Data DQGetFirst(Deque* pdeq) {
	if (QIsEmpty(pdeq)) {
		printf("Queue Memory Error!\n");
		exit(-1);
	}
	return pdeq->tail->data;
}

 

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