Juria에서 Que 구현

엉큼하다

"Juria에 Stack 설치"라는 글에서 구현된 Stack은 이전에 추가된 요소를 추출할 수 있는 데이터 구조다.
하지만 낡은 요소의 데이터 구조도 꺼내고 싶다.이른바 queue다.

queue 작업(간단한 설명)

Stack과 마찬가지로 queue의 구성 요소는 다음과 같은 세 가지가 있다.

소자 초기화

요소의 추가

요소 삭제

비어 있는지 확인

그러나 이번 원소의 추가는 배열의 끝에 있고 원소의 추출은 배열의 시작에서 시작되기 때문에queue는 배열과 끝의 요소의 위치 정보 외에 시작의 정보도 필요하다.

이루어지다

우선 초기화입니다.

mutable struct queue{T}
   last :: Int 
   front :: Int 
   length :: Int
   data :: Array{T,1}
   function queue{T}(N::Int) where T
       new(1,1,N+1,Array{T,1}(undef,N+1))  #空か満杯かを区別するために、N+1個の要素を用意
   end 
end

구조체의 구성 요소는last, front, length, data이다.여기에는 다음과 같은 두 가지 방법이 있다.

정의length

어레이를 한 대 확장

둘 다 뒤에 있는 설치를 보면 이유를 알 수 있지만 극단적으로 말하면

요소를 중복 추가하고 삭제하면 index가 계속 증가하기 때문에 억제하기 위해

queue가 비어 있는지 가득 차 있는지 구분하기 위해

네.
그런 다음 요소를 추가합니다.거의 Stack과 마찬가지로 이번에는 last에서 마지막 요소를 배열한 다음 index를 기억했다.
또한 last가 점점 커지는 것을 방지하기 위해last=length 다음 index를 1로 돌려보냅니다.

function push!(q :: queue, sth)
    q.data[q.last] = sth
    q.last = ifelse(q.last == q.length, 1 , q.last+1)
end

요소를 삭제해도 큰 변화가 없다.front 요소를 삭제한 후 다음 요소의 위치는 front+1입니다.마찬가지로 front가 커지는 것을 막기 위해length 여기도 마찬가지로 돌려보냈다.

function pop!(q :: queue)
    if !isempty(q)
        tmp = q.data[q.front]
        q.front = ifelse(q.front == q.length, 1 , q.front+1)
        return tmp
    else
        error("queue is empty")
    end
end

queue가 비어 있는지 마지막으로 확인합니다.이것은 last와 front가 같은 위치인지 확인할 수 있습니다.

function isempty(q :: queue)
    q.last==q.front
end

동작 확인

동작 확인에 다음 코드가 준비되어 있습니다.이번에 실시한 장점은 추가 Char가 가능하다는 것이다.

q = queue{Char}(10)

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

AtCoder 등 사용 시 신중한 차원에서 확인하세요.