7. 큐(Queue)

deepTree·2024년 11월 21일
자료구조

자료구조

목록 보기
4/9

1. 큐의 이해와 ADT 정의

1-1. 큐의 이해

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

1-2. 큐의 ADT 정의

🔻 핵심 연산

  • enqueue: 큐에 데이터를 넣는 연산
  • dequeue: 큐에서 데이터를 꺼내는 연산
  • 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. 큐의 배열 기반 구현

2-1. 큐의 구현에 대한 논리

  • enqueue
    • F/R: 큐의 머리/꼬리
    • R이 그 다음을 가리키고, 그 자리에 새 데이터가 저장된다.
      enqueue
  • dequeue
    • F 자리에 데이터를 삭제하고, F를 오른쪽으로 이동시킨다.
    • 다만, 배열의 크기가 한정적이기에 배열의 끝에 R이 위치할 경우 더 이상 enqueue 할 수 없다.
      → 원형 큐를 이용한다.(R과 F가 배열의 끝에 도달하면 맨 앞(0)으로 이동시킨다.)

2-2. 원형 큐(Circular Queue)의 소개

  • 배열의 머리와 끝을 연결한 구조를 원의 형태로 바라본다.
    circular-queue
  • 원형 큐의 단순한 연산의 문제점 c-enqueue c-dequeue
    • 큐가 꽉찬 경우나 텅 빈 경우나 F가 R보다 한 칸 앞 선 위치를 가리킨다.
      • F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

🔻 해결책

배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉찬 것으로 간주한다.

  • enqueue
    • R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 저장된 데이터를 저장한다.
  • dequeue
    • F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.
  • 큐의 특성
    • 원형 큐가 텅 빈 상태: F = R
    • 원형 큐가 꽉 찬 상태: F = (R + 1) % (배열길이)

2-3. 원형 큐의 구현

  • 헤더 파일의 정의
    #ifndef __C_QUEUE_H__
#define __C_QUEUE_H__

#define TRUE	1
#define FALSE	0

#define QUE_LEN	100
typedef int Data;

typedef struct _cQueue
{
	int front;	// F
	int rear;		// R
	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);

#endif
    • 큐의 멤버: front, rear
  • 초기화 및 empty
    • 초기화
      void QueueInit(Queue * pq)	// 텅 빈 경우 front와 rear은 동일위치 가리킴
{
	pq->front = 0; // front/rear 모두 0으로 초기화
	pq->rear = 0;
}
    • empty
      int QIsEmpty(Queue * pq)
{
	if(pq->front == pq->rear)	// 큐가 텅 비었다면
		return TRUE;
	else
		return FALSE;
}
  • 큐의 다음 위치에 해당하는 인덱스 값 반환
    int NextPosIdx(int pos)
{
	return (pos+1) % QUE_LEN;
}
  • enqueue, dequeue, peek
    • enqueue
      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가 가리키는 곳에 데이터 저장
}
    • dequeue
      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가 가리키는 데이터 반환
}
    • peek
      Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->queArr[NextPosIdx(pq->front)];
}

2-4. 원형 큐의 실행

#include <stdio.h>
#include "CircularQueue.h"

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

	return 0;
}
  • 실행 결과
    1 2 3 4 5

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

3-1. 연결 리스트 기반 큐의 헤더파일 정의

큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다.

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

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

typedef struct _lQueue
{
	Node * front;	// F
	Node * rear;	// R
} 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);

#endif
  • 큐의 멤버: front/rear

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

lq-first

  • 초기화 및 empty
    • 초기화
      void QueueInit(Queue * pq)
{
	pq->front = NULL;
	pq->rear = NULL;
}
      • front/rear 모두 NULL로 초기화시킨다.
    • empty
      int QIsEmpty(Queue * pq)
{
	if(pq->front == NULL)	// F에 NULL이 저장되면 큐가 빈 것이다.
		return TRUE;
	else
		return FALSE;
}
      • 📌 연결 리스트 기반의 큐가 비었다면, F에 NULL이 저장된다.

  • enqueue, dequeue, peek

    • Enqueue

      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/rear 모두 새 노드를 가리킨다.
		pq->rear = newNode;
	}
	else	// 두 번째 이후의 노드 추가라면
	{
		pq->rear->next = newNode;	// 마지막 노드가 새 노드를 가리키게 한다.
		pq->rear = newNode;	// rear가 새 노드를 가리키게 한다.
	}
}

    • dequeue

      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;
}
      • F가 다음 노드를 가리키게 한다.
      • F가 이전에 가리키던 노드를 소멸시킨다.
      • 소멸시킨 데이터를 반환

    • peek

      Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->front->data;
}

4. 덱의 이해와 구현

4-1. 덱(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);
      • head에 데이터를 저장
    • void DQAddLast(Deque * pdeq, Data data);
      • tail에 데이터를 저장
    • Data DQRemoveFirst(Deque * pdeq);
      • head에 위치한 데이터를 반환 및 소멸
    • Data DQRemoveLast(Deque * pdeq);
      • tail에 위치한 데이터를 반환 및 소멸
    • Data DQGetFirst(Deque * pdeq);
      • head에 위치한 데이터를 소멸하지 않고 반환
    • Data DQGetLast(Deque * pdeq);
      • tail에 위치한 데이터를 소멸하지 않고 반환

4-2. 덱의 구현

  • 헤더 파일의 정의 2-way-list

    • ‘양방향 연결 리스트’를 기반으로 덱을 구현한다.
      - Data DQRemoveLast(Deque * pdeq); : tail에 위치한 노드를 삭제하는 데 용이하다.
      - 기존의 양방향 연결 리스트와 달리 포인터 변수 tail을 둬서 리스트의 꼬리를 가리킨다.

      #ifndef __DEQUE_H__
#define __DEQUE_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);
int DQIsEmpty(Deque * pdeq);

void DQAddFirst(Deque * pdeq, Data data);
void DQAddLast(Deque * pdeq, Data data);

Data DQRemoveFirst(Deque * pdeq);
Data DQRemoveLast(Deque * pdeq);

Data DQGetFirst(Deque * pdeq);
Data DQGetLast(Deque * pdeq);

#endif
  • 초기화 및 empty
    • 초기화
      void DequeInit(Deque * pdeq)	// head,tail 모두 NULL로 초기화
{
	pdeq->head = NULL;
	pdeq->tail = NULL;
}
    • empty
      int DQIsEmpty(Deque * pdeq)
{
	if(pdeq->head == NULL)	// head가 NULL이면 비어있는 덱이다.
		return TRUE;
	else
		return FALSE;
}
  • 원소 추가
    • DQAddFirst
      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;	// 덱의 첫 번째 원소로 표시
}
    • DQAddLast
      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;	// 덱의 마지막 원소로 표시
}
  • 원소 제거
    • DQRemoveFirst
      Data DQRemoveFirst(Deque * pdeq)
{
	Node * rnode = pdeq->head;	// 삭제할 노드
	Data rdata = pdeq->head->data;	// 삭제할 노드가 지닌 값 저장

	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	pdeq->head = pdeq->head->next;	// head 위치를 오른쪽으로 옮김
	free(rnode);

	if(pdeq->head == NULL)	// 덱이 비어 있음(초기화)
		pdeq->tail = NULL;
	else
		pdeq->head->prev = NULL;	// 첫 번째 원소임을 의미

	return rdata;
}
    • DQRemoveLast
      Data DQRemoveLast(Deque * pdeq)
{
	Node * rnode = pdeq->tail;	// 삭제할 노드
	Data rdata = pdeq->tail->data;	// 삭제할 노드가 지닌 값 저장

	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	pdeq->tail = pdeq->tail->prev;	// tail 위치를 왼쪽으로 옮김
	free(rnode);

	if(pdeq->tail == NULL)	// 덱이 비어 있음(초기화)
		pdeq->head = NULL;
	else
		pdeq->tail->next = NULL;	// 마지막 원소임을 의미

	return rdata;
}
  • 원소 조회
    • DQGetFirst
      Data DQGetFirst(Deque * pdeq)
{
	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	return pdeq->head->data;
}
    • DQGetLast
      Data DQGetLast(Deque * pdeq)
{
	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	return pdeq->tail->data;
}

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

profile
deepTree
매일 노력하는 초보 개발자입니다.
이전 포스트

6. 스택(stack)

다음 포스트

8. 트리(Tree)

0개의 댓글