«   2018/12   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Statistics Graph
관리 메뉴

언제나 휴일

[디딤돌 자료구조와 알고리즘] 5.3.1 큐(QUEUE) 설계 본문

언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘

[디딤돌 자료구조와 알고리즘] 5.3.1 큐(QUEUE) 설계

언제나 휴일 언제나휴일 2016.05.23 17:03

5.3.1 큐(QUEUE) 설계




 여기에서는 연결리스트를 큐로 감싸(Wrapping)하여 선입선출(FIFO, First In First Out)방식으로 자료를 보관 및 꺼내기 동작을 제공하도록 설계할게요.

#include "LinkedList.h"

typedef LinkedList EHQueue;

 

 큐를 설계할 때 내부에 자료를 보관하는 저장소를 배열로 만드는 방법도 있는데 이미 만들어진 연결리스트를 이용하여 자료를 보관하게 정의하면 저장소의 한계가 없는 큐를 만들 수 있습니다. 물론 메모리의 한계까지 없는 것은 아닙니다. 일반적으로 대학에서 배우는 큐는 자료를 보관하는 저장소를 정적 크기의 배열로 정의하는 큐를 배우고 꽉 찼을 때의 처리에 관한 고민을 합니다. 특히 이 문제를 원형 큐 형태로 만들어 문제를 해결하는데 자료를 저장하는 저장소를 이미 만들어진 연결리스트를 이용하면 구현을 단순화할 수 있습니다.

 

 특히 대학교에서 다루는 큐는 저장소를 정적 배열로 정의하기 때문에 자료를 보관할 인덱스 rear와 자료를 꺼낼 인덱스 front를 기억하고 있어야 합니다. 하지만 여기에서 만드는 큐는 저장소를 이미 작성한 연결리스트를 이용하기 때문에 이와 같은 멤버를 별도로 기억할 필요가 없습니다. 연결리스트에는 head tail이 있어서 tail 앞에 자료를 보관하고 head 뒤에서 꺼내면 자연스럽게 선입선출(FIFO) 방식으로 자료를 보관 및 꺼낼 수 있습니다.

 

 동적으로 큐를 생성하는 함수와 동적으로 생성한 큐를 제거하는 함수를 제공합시다.

 EHQueue *New_EHQueue();

void Delete_EHQueue(EHQueue *ehq);

 

 큐에 자료를 보관하는 함수와 큐에 보관한 자료를 꺼내는 함수를 제공합시다.

void EHQueue_Put(EHQueue *ehq, Element data);

Element EHQueue_Get(EHQueue *ehq);

 

 마지막으로 큐가 빈 상태인지 확인하는 함수를 제공합시다.

int EHQueue_IsEmpty(EHQueue *ehq);

EHQueue.h

//EHQueue.h

#pragma once

#include "LinkedList.h"

 

typedef LinkedList EHQueue;

 

EHQueue *New_EHQueue();

void Delete_EHQueue(EHQueue *ehq);

void EHQueue_Put(EHQueue *ehq, Element data);

Element EHQueue_Get(EHQueue *ehq);

int EHQueue_IsEmpty(EHQueue *ehq);


관련 게시글

[디딤돌 자료구조와 알고리즘] 5.3 큐(QUEUE)

[디딤돌 자료구조와 알고리즘] 5.3.2 큐 구현 , 5.3.3 큐 테스트


큐 실습 소스 및 헤더 파일

큐.zip


다양한 큐 구현

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 크기 고정, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 모든 공간 사용, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 공간을 동적으로 생성, 정수 보관, C 언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 동적 생성, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 자동으로 확장, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 공간 자동으로 할당, 동적 데이터 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 큐 - 연결리스트 이용, C언어 소스

3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]

3.5 큐를 이용한 스케쥴러 시뮬레이션 [디딤돌 자료구조와 알고리즘 with C++]



0 Comments
댓글쓰기 폼