Edited at

ErlangのQueue実装

More than 3 years have passed since last update.

-module(fifo_types).

-compile(export_all).

%% 概要
%% キューをシミュレートするためにはスタックとして2つのリストを使います。
%% 片方のリストに新しい要素を保存し、もう片方を使ってキューから要素を
%% 削除します。削除するリストが空の時に要素追加するほうのリストを逆順
%% にして、そちらを削除するリストとします。

%% 2> c(fifo_types).
%% {ok,fifo_types}

%% 18> Q = fifo_types:new().
%% {fifo,[],[]}
%%
%% 19> Q1 = fifo_types:push(Q, 1).
%% {fifo,[1],[]}
%%
%% 20> Q2 = fifo_types:push(Q1, 2).
%% {fifo,[2,1],[]}
%%
%% 21> {Val, Q3} = fifo_types:pop(Q2).
%% {1,{fifo,[],[2]}}
%%
%% 22> {Val1, Q4} = fifo_types:pop(Q3).
%% {2,{fifo,[],[]}}
%%
%% 23> fifo_types:empty(Q4).
%% true
%% 24> fifo_types:empty(Q3).
%% false
-spec new() -> {fifo, [], []}.
new() ->
{fifo, [], []}.

-spec push({fifo, In::list(), Out::list()}, term()) -> {fifo, list(), list()}.
push({fifo, In, Out}, X) -> {fifo, [X|In], Out}.

-spec pop({fifo, In::list(), Out::list()}) -> {term(), {fifo, list(), list()}}.
pop({fifo, [], []}) -> erlang:error('empty fifo');

%% popするときにリストが空になって、Inのほうを逆順して、popに使う
pop({fifo, In, []}) -> pop({fifo, [], lists:reverse(In)});
pop({fifo, In, [H|T]}) -> {H, {fifo, In, T}}.

%% list()は[any()]とほぼ同じで、どちらも空リストを含みます。list()が型として指定
%% されると`[]`と重なります。
-spec empty({fifo, [],[]})-> true;
({fifo, nonempty_list(), nonempty_list()}) -> false.
empty({fifo, [], []}) -> true;
empty({fifo, _, _}) -> false.