queue

模块

队列

模块摘要

FIFO队列的抽象数据类型。

描述

该模块以有效的方式提供（双端）FIFO队列。

badarg如果参数类型错误，所有函数都会失败，例如队列参数不是队列，索引不是整数，列表参数不是列表。不正确的列表会导致内部崩溃。超出范围的索引也会导致故障并导致原因badarg。

某些功能在指出的情况下会empty因空队列失败而失败。

表示该模块使用的队列的数据将被其他模块视为不透明。任何假定了格式知识的代码都是在精简的冰上运行。

所有的操作有（1）运行时间摊销O，除了filter/2，join/2，len/1，member/2，split/2有O（N）。为了最大限度地减少队列操作构建垃圾量的队列大小，队列不包含显式长度信息，这len/1就是O（n）的原因。如果此特定操作的性能更好，则主叫方很容易追踪其长度。

队列是双向的。队列的精神图片是等待轮到他们的一行人（物品）。队列前端是等待时间最长的项目的结尾。队列尾部是物品开始等待时进入的结局。如果使用列表的心理图片，则前部称为头部，后部称为尾部。

在前面进入并在后面退出是对队列的反向操作。

该模块具有三套接口功能：“原始API”，“扩展API”和“Okasaki API”。

“原始API”和“扩展API”都使用等待项目的心理图片。两者都有反向操作后缀“_r”。

“原始API”项删除功能会将已删除项目和结果队列中的复合词条返回。“扩展API”包含替代函数，只需检查队列结束便可减少垃圾和函数。此外，“冈崎API”功能减少垃圾。

“Okasaki API”的灵感来自Chris Okasaki的“纯功能数据结构”。它将队列视为列表。这个API被许多人视为奇怪并且可以避免。例如，许多反向操作的名称都是词法颠倒的，其中一些具有更多可读性但可能不太容易理解的别名。

原始API

数据类型

queue(Item)

由new/0返回。

queue() =queue(term())

出口

filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item)

类型

按照从前到后的顺序，返回Q2调用Fun(Item)所有项目的队列Q1。

如果Fun(Item)返回true，Item则被复制到结果队列中。如果它返回false，Item则不被复制。如果它返回一个列表，列表元素将被插入而不是Item在结果队列中。

所以，Fun(Item)返回[Item]在语义上等同于返回true，就像返回[]在语义上等价于返回一样false。但是返回一个列表会比返回一个原子构建更多的垃圾。

from_list(L :: Item) -> queue(Item)

L以相同顺序返回包含项目的队列; 该列表的头项目成为队列的前项目。

in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)

插入Item队列后面Q1。返回结果队列Q2。

in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)

插入Item队列的前面Q1。返回结果队列Q2。

is_empty(Q :: queue()) -> boolean()

测试是否Q为空，如果是则返回true，否则返回。

is_queue(Term :: term()) -> boolean()

测试是否Term为队列，如果是则返回true，否则返回false。

join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item)

返回队列Q3是接合的结果Q1和Q2与Q1前面Q2。

len(Q :: queue()) -> integer() >= 0

计算并返回队列的长度Q。

member(Item, Q :: queue(Item)) -> boolean()

返回true如果Item匹配某个元素Q，否则返回false。

new() -> queue()

返回空队列。

out(Q1 :: queue(Item)) ->

{{value, Item}, Q2 :: queue(Item)} |

{empty, Q1 :: queue(Item)}

删除队列前面的项目Q1。返回元组{{value, Item}, Q2}，该元素在哪里Item被删除，并且Q2是结果队列。如果Q1为空，{empty, Q1}则返回元组。

out_r(Q1 :: queue(Item)) ->

{{value, Item}, Q2 :: queue(Item)} |

{empty, Q1 :: queue(Item)}

删除队列后面的项目Q1。返回元组{{value, Item}, Q2}，其中Item的项目被删除，并且Q2是新的队列。如果Q1为空，{empty, Q1}则返回元组。

reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2包含Q1相反顺序项目的队列。

split(N :: integer() >= 0, Q1 :: queue(Item)) ->

{Q2 :: queue(Item), Q3 :: queue(Item)}

拆分Q1为两段。在N前面的项目投入Q2和休息Q3。

to_list(Q :: queue(Item)) -> Item

以相同顺序返回队列中的项目列表；队列的前端项目成为列表的头部。

扩展API

出口

drop(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从前面项目中删除的结果Q1。

empty如果Q1是空的，则不合理。

drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从后面删除项目的结果Q1。

empty如果Q1是空的，则不合理。

get(Q :: queue(Item)) -> Item

返回Item队列的前端Q。

empty如果Q是空的，则不合理。

get_r(Q :: queue(Item)) -> Item

返回Item队列后面Q。

empty如果Q是空的，则不合理。

peek(Q :: queue(Item)) -> empty | {value, Item}

返回元组{value, Item}，其中Item是前面的项目Q，或者empty是否Q为空。

peek_r(Q :: queue(Item)) -> empty | {value, Item}

返回元组{value, Item}，Item后面的项目在哪里Q，或者empty是否Q为空。

冈崎API

出口

cons(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)

插入Item队列头部Q1。返回新的队列Q2。

daeh(Q :: queue(Item)) -> Item

返回队列的尾部项目Q。

empty如果Q是空的，则不合理。

head(Q :: queue(Item)) -> Item

Item从队列头部返回Q。

empty如果Q是空的，则不合理。

init(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从尾部删除项目的结果Q1。

empty如果Q1是空的，则不合理。

lait(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从尾部删除项目的结果Q1。

empty如果Q1是空的，则不合理。

名称lait/1是拼写错误 - 不要再使用它了。

last(Q :: queue(Item)) -> Item

返回队列的尾部项目Q。

empty如果Q是空的，则不合理。

liat(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从尾部删除项目的结果Q1。

empty如果Q1是空的，则不合理。

snoc(Q1 :: queue(Item), Item) -> Q2 :: queue(Item)

插入Item队列的尾部项目Q1。返回新的队列Q2。

tail(Q1 :: queue(Item)) -> Q2 :: queue(Item)

返回Q2从中删除头项目的结果Q1。

empty如果Q1是空的，则不合理。