キュー

目的

配列の末尾に要素の追加、削除を$O(1)$で行うデータ構造です。この実装ではバッファサイズを固定しています。事前にバッファのサイズが分からないときは、要素数に対してある閾値外になったときは配列を新しく取り直すという機能を付ける必要があります。

計算量

$O(1)$

使い方

void init(integer n)
バッファサイズをnとする
integer poll()
末尾の要素をreturnし、末尾の要素は削除
integer peek()
末尾の要素をreturn
void put(integer v)
末尾にvを追加
logical is_empty()
配列が空のときtrue、空でないときfalseをreturn

ソースコード

module que_module
    implicit none

    type que
        private
        integer::s=1,t=1
        integer,allocatable::contents(:)
    contains
        procedure::is_empty
        procedure::poll
        procedure::peek
        procedure::put
    end type que

    interface que
        module procedure init
    end interface

contains

    type(que) function init(n)
        integer::n
        allocate(init%contents(n))
    end function init

    logical function is_empty(q)
        class(que)::q
        logical::ret
        ret=((q%s).eq.(q%t))
        is_empty=ret
    end function is_empty

    integer function poll(q)
        class(que)::q
        poll=q%contents(q%s)
        q%s=q%s+1
    end function poll

    integer function peek(q)
        class(que)::q
        peek=q%contents(q%s)
    end function peek

    subroutine put(q,v)
        class(que)::q
        integer::v
        q%contents(q%t)=v
        q%t=q%t+1
    end subroutine put

end module que_module