비환형큐( Non Circle Queue ) 의 구현과 이해 및 시간복잡도

소개글

스케쥴러, 표준입출력 등에 쓰이는 대표적 자료구조인 큐( Queue ) 중에서 자료의 삽입, 반환시 압축과정( Compression ) 이 필요한 비환형큐 ( Non-Circle Queue ) 의 구현과 시간복잡도를 기술한 보고서입니다.

비환형큐에서 자료삭제 ( 또는 반환 )시에 생기는 전형적인 문제점( queue 의 앞부분은 빈 공간이고, 중간부터 값이 차있는 것 )을 해결하기 위한 압축함수 ( Compress() ) 를 추가하였습니다.

비슷한 자료구조인 환형큐와 삽입, 반환, Full & Empty 를 확인하는 함수만 다를 뿐 구조적으로 같은 형태인 점을 활용해, 환형큐의 헤더파일( Header file : .h ) 를 상속받아 구현하였습니다. 그렇기 때문에, Main 파일의 내용을 조금만 수정하면 비환형큐 뿐만 아니라 환형큐 역시 사용할 수 있습니다.

template class 로 구현되어있기 때문에 어떤 Type 의 자료형이든 그에 합당한 Queue 를 생성할 수 있도록 하였으며, 출력시, 어느값이 제일 오래된 값이고 어느값이 제일 최근에 입력된 값인지 확인할 수 있도록 구현하였습니다.

동적할당방식을 사용하기 때문에 Queue 객체 생성시 Queue 의 크기를 마음대로 조절할 수 있으며, 그에 따른 메모리 관리에도 철저히 신경쓴 프로그램입니다.

컴파일 실행환경

Microsoft Visual Stdio C++ ( ENG Ver. )

압축파일 내 파일목록

CircleQueueHeader.h
DebugBuildLog.htm
Debugmt.dep
DebugNon Circle Queue.exe.intermediate.manifest
DebugNonCircleQueue.exe.intermediate.manifest
DebugNonCircleQueue.obj
DebugNonCircleQueueMain.obj
DebugQueue-no circle.exe.intermediate.manifest
DebugQueue.exe.intermediate.manifest
Debugvc90.idb
Debugvc90.pdb
NonCircleQueue.cpp
NonCircleQueueHeader.h
NonCircleQueueMain.cpp
Queue.vcproj
Queue.vcproj.PRION-LAPTOP.Prion.user
Queue.vcproj.PRION.Microsoft.user
Queue.vcproj.PRION.Teolex.user
Queue.vcproj.Teolex-PC.Teolex.user
Queue.vcproj.송지훈.Microsoft.user
Queue.vcproj.송지훈.Prion.user
ReleaseBuildLog.htm
Releasemt.dep
ReleaseNon Circle Queue.exe.intermediate.manifest
ReleaseNonCircleQueue.obj
ReleaseNonCircleQueueMain.obj
Releasevc90.idb
Releasevc90.pdb
Non Circle Queue의 구현과 이해 및 시간복잡도.docx

전체 목록 보기

참고 자료

없음