Last active
March 16, 2016 13:24
-
-
Save wang-zhijun/d3c9c170cdc15a62f0cc to your computer and use it in GitHub Desktop.
ErlangのQueue実装 ref: http://qiita.com/ColdFreak/items/eb3bc54f0db5b42db544
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-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. | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment