자료구조 큐(QUEUE)-선형큐,원형큐,연결리스트,덱

안녕하세요 꼬로미입니다

자료구조 큐(QUEUE)에 대한 포스팅입니다

큐(QUEUE)

먼저 들어온 데이터가 먼저 나가는 자료구조

선입 선출(FIFO : First-In First-Out)

스택과 마찬가지로 프로그래머의 도구이며 많은 알고리즘에서 사용됨

서비스를 받는 대기열에 사용(공항에서 비행기들, 은행에서 대기열)

삽입은 큐의 후단에서, 삭제는 전단에서

enqueue(q, e)            큐의 뒤에 요소를 추가

dequeue(q)                큐의 앞에 있는 요소를 반환한 다음 삭제

배열을 이용한 큐

선형 큐(linear queue)

배열을 선형으로 사용해 큐를 구현

삽입을 계속하기 위해 요소들을 이동시켜야함

문제점이 많아 사용되지 않음

* 초기에 front와 rear는 -1을 가르킴

원형큐

배열을 원형으로 사용해 큐를 구현

* 항상 front는 비어있어야 함

* Enqueue 명령시 FULL인지 확인하는 절차 필요

   (r+1) % MAX_SIZE = f 이면 값을 넣을 수 없음 (Queue FULL 발생)

* Dequeue 명령시 (f==r)이면 (Queue EMPTY 발생)

공백상태와 포화상태

공백상태 : front == rear

포화상태 : front % M == (rear+1)%M

공백상태와 포화상태를 구별하기 위해 하나의 공간은 항상 비워둠

공백 상태 검출 함수

int is_empty(QueueType *q) { return (q->front == q->rear); }

포화 상태 검출 함수

int is_full(QueueType *q) { return ((q->rear+1) % MAX_QUEUE_SIZE == q->front); }

삽입 함수

void enqueue(QueueType *q, element item) {    if( is_full(q) )  error("큐가 포화상태입니다"); q->rear = (q->rear+1) % MAX_QUEUE_SIZE; q->queue[q->rear] = item; }

삭제 함수

element dequeue(QueueType *q)  {      if( is_empty(q) ) error("큐가 공백상태입니다"); q->front = (q->front+1) % MAX_QUEUE_SIZE; return q->queue[q->front]; }

연결된 큐(linked queue)

front포인터는 삭제와 관련되며 rear 포인터는 삽입

front는 연결 리스트 맨앞의 요소를 가르키며, rear 포인터는 맨 뒤에 있는 요소를 가르킴

큐에 요소가 없는 경우 front와 rear는 NULL

연결리스트로 구현된 큐

덱(deque, Double-ended queue)

큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결 리스트 사용

일반적으로 Queue Full이 생기지 않음, 메모리가 가득차면 Full

덱에서 삽입연산은 연결리스트의 연산과 유사하며

헤드포인터 대신 head와 tail 포인터 사용

앞을 가르키는 주소, 뒤를 가르키는 주소

동작되는 원리가 복잡복잡 헷갈리네요ㅎㅎ

간단한 이론에 대한 정리였습니다

읽어주셔서 감사합니다 ^^*