<div class="warning"> 여기사 사용된 그림및 플래쉬 자료에 대한 저작권은 전북대학교 박순철 교수님께 있습니다.

각각의 플래쉬는 파란색의 PUSH및 POP버튼을 클릭하면 작동합니다. </div>

Queue#

queue는 한쪽 끝에서는 데이터를 쌓기만 하고 반대쪽에서는 데이터를 제거만 하는 형태의 자료구조이다. 선입선출(FIFO) 이라는 먼저 들어온 데이터가 먼저 나가는 형태의 알고리즘을 사용한다.

Linear Queue#

다음은 Linear Queue를 나타내는 그림이다. 새로운 데이터의 삽입은 rear pointer에서 발생한다. 데이터의 삭제는 front pointer에서 일어나며 Queue자체가 고정적인 위치를 가지는 형태라고 볼수 있다.

1.jpg

Linear Queue에서의 데이터 삽입

2-1.jpg

2-2.jpg

Linear Queue에서의 데이터 삭제

3-1.jpg

3-2.jpg

Linear Queue에서 full상태인지 체크

4-1.jpg

4-2.jpg

Linear Queue에서 빈 상태인지 체크

5.jpg

다음은 Linear Queue에 데이터를 쌓는 작업이 push와 데이터를 다시 빼내는 작업인 pop에 대한 것을 보여준다.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/queue/flash/queue_linear.swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/queue/flash/queue_linear.swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

Linear Queue는 고정된 위치를 가지기 때문에 full상태인 overflow가 될 가능성이 있다. 이를 위해서 사용할 수 있는 방법은 Moving Queue와 Circular Queue를 사용하는 방법이 있다.

Moving Queue#

6-1.jpg

6-2.jpg

Moving Queue의 장점과 단점

  • 장점 : Queue에서 발생하는 overflow를 해결할수 있다.
  • 단점 : 가용공간을 만들기 위해 많은 원소들을 이동시켜야 하는 많은 시간적인 손실을 초래한다. ⇒ 해결 방법 : 환상 큐 방식

Circular Queue#

입력하기

E 라는 데이터를 입력한다.

7.jpg

8.jpg

F 라는 데이터를 입력한다.

9.jpg

10.jpg

Circular Queue에서 full 상태인지 체크. Front pointer와 Rear pointer가 같으면 full 상태.

11.jpg

Circular Queue에서 삭제

12.jpg

13.jpg

Circular Queue에서 빈 상태인지 체크. Front pointer와 Rear pointer가 같으면 빈 상태.

14.jpg

여기서 Front pointer와 Rear pointer가 같은 경우에는 full상태일수도 있고 빈 상태일수도 있다. 즉 Front pointer와 Rear pointer가 같은 경우 이 상태가 full상태인지 빈 상태인지를 구분할수 있는 방법이 필요하다.

큐가 가득찬 경우와 비어있는 경우를 구분하는 방법

15.jpg

16.jpg

동작방식을 보자.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/queue/flash/queue_circular.swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/queue/flash/queue_circular.swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
1.jpg 26.3 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
10.jpg 25.5 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
11.jpg 26.4 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
12.jpg 25.2 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
13.jpg 24.9 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
14.jpg 23.7 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
15.jpg 23.7 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
16.jpg 26.2 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
2-1.jpg 20.7 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
2-2.jpg 17.9 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
3-1.jpg 17.0 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
3-2.jpg 19.6 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
4-1.jpg 17.4 kB 1 16-Jul-2007 16:26 DongGukLee
jpg
4-2.jpg 15.3 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
5.jpg 14.6 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
6-1.jpg 17.6 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
6-2.jpg 19.0 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
7.jpg 30.5 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
8.jpg 25.3 kB 1 16-Jul-2007 16:27 DongGukLee
jpg
9.jpg 30.7 kB 1 16-Jul-2007 16:27 DongGukLee
« This page (revision-5) was last changed on 16-Jul-2007 16:38 by DongGukLee  
G’day (anonymous guest) My Prefs

Referenced by
Basic

JSPWiki v2.8.4