Erlang Queue

 ]}
  7 >  queue:  in (f,v( 6  )).
{[f,e,d,c,b],[a]}
  8 >  queue:  in (g,v( 7  )).
{[g,f,e,d,c,b],[a]}
  9 >

出队列通常复杂度也是咋O(1),最差的情况是O(len(Q));对于RearList和FrontList都有数据的情况下,取出一个数据元素仅仅是从FrontList中取出头元素,所以时间复杂度也是1.如果恰好取出了FrontList的最后一个元素,就要做前后端数据元素的转移.

%% O( 1  ) amortized, O(len(Q)) worst case
  out  ({[],[]}=Q) ->
    {empty,Q}  ;
  out  ({[V],[]}) ->
    {{value,V},{[],[]}}  ;
  out ({[Y| In  ],[]}) ->
    [V|  Out ] =  lists: reverse( In  , []),
    {{value,V},{[Y],  Out }} ;
  out ({ In ,[V]}) when is_list( In  ) ->
    {{value,V},r2f(  In )} ;
  out ({ In ,[V| Out ]}) when is_list( In  ) ->
    {{value,V},{  In , Out }} ;
  out  (Q) ->
      erlang: error(badarg, [Q]).

 10 >  queue:  out (v( 8  )).  
{{value,a},{[g,f],[b,c,d,e]}}
  11 > {_,R}= queue:  out (v( 8  )).
{{value,a},{[g,f],[b,c,d,e]}}
  12 > {_,R2}= queue:  out  (R).   
{{value,b},{[g,f],[c,d,e]}}
  13 > {_,R3}= queue:  out  (R2).
{{value,c},{[g,f],[d,e]}}
  14 > {_,R4}= queue:  out  (R3).
{{value,d},{[g,f],[e]}}
  15 >

类似的情况还有get方法,大多数情况下复杂度是O(1),最差的情况下需要去RearList的最后一个元素,时间复杂度是O(len(Q)).

%% O( 1  ) since the queue is supposed to be well formed
get({[],[]}=Q) ->
      erlang: error(empty, [Q]) ;
  get({R,F}) when is_list(R), is_list(F) ->
    get(R, F)  ;
  get(Q) ->
      erlang:  error(badarg, [Q]).

get(R, [H|_]) when is_list(R) ->
    H  ;
  get([H], []) ->
    H  ;
  get([_|R], []) -> % malformed queue -> O(len(Q))
      lists: last(R).

逆转整个队列这样的操作时间复杂度也是O(1),因为只需要把前后段两个List互换就可以了;

%% O( 1  )
reverse({R,F}) when is_list(R), is_list(F) ->
    {F,R}  ;
  reverse(Q) ->
      erlang: error(badarg, [Q]).

三种API

queue是双端数据结构.从front端进入,从rear端出.模块的接口比较丰富,分为: "Original API", the "Extended API" and the "Okasaki API".Original API 和 Extended API 接口都可以用队列进出模型去理解,其中进行了reverse操作都会添加"_r"的后缀.

官方文档中的说法:

地址: http://www.erlang.org/doc/man/queue.html

The "Original API" item removal functions return compound terms with both the removed item and the resulting queue. The "Extended API" contain alternative functions that build less garbage as well as functions for just inspecting the queue ends. Also the "Okasaki API" functions build less garbage.

The "Okasaki API" is inspired by "Purely Functional Data structures" by Chris Okasaki. It regards queues as lists. The API is by many regarded as strange and avoidable. For example many reverse operations have lexically reversed names, some with more readable but perhaps less understandable aliases.

Learn you some Erlang的解释:

地址: http://learnyousomeerlang.com/a-short-visit-to-common-data-structures#queues

Original API
The original API contains the functions at the base of the queue concept, including: new/0 , for creating empty queues, in/2 , for inserting new elements, out/1 , for removing elements, and then functions to convert to lists, reverse the queue, look if a particular value is part of it, etc. Extended API
The extended API mainly adds some introspection power and flexibility: it lets you do things such as looking at the front of the queue without removing the first element (see get/1 or peek/1 ), removing elements without caring about them ( drop/1 ), etc. These functions are not essential to the concept of queues, but they're still useful in general. Okasaki API
The Okasaki API is a bit weird. It's derived from Chris Okasaki's Purely Functional Data Structures . The API provides operations similar to what was available in the two previous APIs, but some of the function names are written backwards and the whole thing is relatively peculiar. Unless you do know you want this API, I wouldn't bother with it.

晚安!

More Sharing Services Share | Share on facebook Share on myspace Share on google Share on twitter

分类: Erlang

作者： Leo_wl
　　　　
出处： http://www.cnblogs.com/Leo_wl/
　　　　
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息

查看更多关于Erlang Queue的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did48571

更新时间：2022-09-24 阅读：39次