제5 장 Cach é 알고리즘 과 데이터 구조 대기 열 원리

글 목록

제5 장 Cach é 알고리즘 과 데이터 구조 대기 열 원리

대열

데이터 실현

링크 실현

입단

출전

링크 대기 열 구체 적 실현

노드 클래스

링크 대기 열 류

호출

제5 장 Cach é 알고리즘 과 데이터 구조 대기 열 원리
대열
대기 열 은 선형 데이터 구조 로 스 택 의 선 입 후 출 과 달리 대기 열 에 있 는 요 소 는 먼저 들 어 갈 수 밖 에 없습니다.대열 의 출구 끝 을 맞은편 이 라 고 하고 대열 의 입구 끝 을 대열 의 끝 이 라 고 한다.
데이터 구현
적수
대열 의 후미
1
3
4
5
6
9
링크 구현
적수
대열 의 후미
1
3
4
5
6
9
null
대열 에 들어가다
입 대 는 새로운 요 소 를 대열 에 넣 는 것 입 니 다. 팀 의 끝 에 만 요 소 를 넣 을 수 있 습 니 다. 새로운 요소 의 다음 위 치 는 팀 의 끝 이 됩 니 다.예 를 들 어 7 입단.
적수
대열 의 후미
1
3
4
5
6
7
9
대열 에 나가다
출 대 작업 은 요 소 를 대열 에서 옮 기 는 것 입 니 다. 머리 쪽 에서 만 요 소 를 제거 할 수 있 습 니 다. 출 대 요소 후의 요 소 는 새로운 열 머리 가 될 것 입 니 다.예 를 들 어 3 팀 을 나 간다.
적수
대열 의 후미
1
4
5
6
7
9
링크 대기 열 구체 적 실현
노드 클래스

Class PHA.YX.Arithmetic.LinkedQueue.Node Extends %RegisteredObject
{

Property next As PHA.YX.Arithmetic.LinkedQueue.Node;

Property element;

Method %OnNew(next As PHA.YX.Arithmetic.LinkedQueue.Node, element) As %Status [ Private, ServerOnly = 1 ]
{
	s $this.next = next
	s $this.element = element
	Quit $$$OK
}

Method getNext() As PHA.YX.Arithmetic.LinkedQueue.Node
{
	q ..next
}

Method setNext(next As PHA.YX.Arithmetic.LinkedQueue.Node)
{
	s $this.next = next
}

Method getElement() As PHA.YX.Arithmetic.LinkedQueue.Node
{
	q ..element
}

Method setElement(element)
{
	s $this.element = element
}

}

링크 큐 클래스

Class PHA.YX.Arithmetic.LinkedQueue Extends %RegisteredObject
{

Property front As PHA.YX.Arithmetic.LinkedQueue.Node;

Property rail As PHA.YX.Arithmetic.LinkedQueue.Node;

Property size As %Integer [ InitialExpression = 0 ];

Method isEmpty() As %Boolean
{
	q $s(..size = 0 : $$$YES, 1 : $$$NO)
}

Method addQueue(ele)
{
	i ..size = 0 d
	.s ..front = ##class(PHA.YX.Arithmetic.LinkedQueue.Node).%New("",ele)
	.s ..rail = ..front
	.s ..size = ..size + 1
	e  d
	.s s = ##class(PHA.YX.Arithmetic.LinkedQueue.Node).%New("",ele)
	.d ..rail.setNext(s)
	.s ..rail = s
	.s ..size = ..size + 1
}

Method deleteQueue()
{
	i ..isEmpty() d
	.throw ##class(PHA.COM.MOB.Exception).%New("      ！")
	s ele = ..front.getElement()
	s ..front = ..front.next
	s ..size = ..size - 1
	q ele
}

}

호출

/// w ##class(PHA.YX.Arithmetic).LinkedQueue()
ClassMethod LinkedQueue()
{
	#dim linkedQueue as PHA.YX.Arithmetic.LinkedQueue = ##class(PHA.YX.Arithmetic.LinkedQueue).%New()
	d linkedQueue.addQueue(1)
	d linkedQueue.addQueue("a")
	d linkedQueue.addQueue(2)
	w linkedQueue.deleteQueue(),!
	w linkedQueue.deleteQueue(),!
	d linkedQueue.addQueue("b")
	w linkedQueue.deleteQueue(),!
	w linkedQueue.deleteQueue(),!
	q ""
}

DHC-APP>w ##class(PHA.YX.Arithmetic).LinkedQueue()
1
a
2
b