큐(queue)
by Frinee이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.
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)
블로그의 정보
프리니의 코드저장소
Frinee