Erlang程式设计与问题解决/堆叠与伫列

计算机科学 > 编程 > Erlang程式设计与问题解决

堆叠是让资料先进后出的序列。伫列是让资料先进先出的序列。堆叠与伫列的应用场合非常多。而借由样式匹配，用 Erlang 实现堆叠与伫列相当简单，并且应用广泛。

堆叠

首先，可以建立空堆叠：

-module(stack).
-compile(export_all).

create() ->
    [].

需要添加资料与删除资料的操作：

push(Data, Stack) ->
    [Data|Stack].

pop([]) ->
    {[], []};
pop([Data|Stack]) ->
    {Data, Stack}.

加上一些辅助函数：

is_empty(Stack) ->
    Stack == [].

length(Stack) ->
    erlang:length(Stack).

基本上能直觉地设计。

伫列

仿照堆叠的直觉设计，伫列是：

-module(queue).
-compile(export_all).

create() ->
    [].

enqueue(Data, Queue) ->
    [Data|Queue].

dequeue([]) ->
    {[], []};
dequeue([X|[]]) ->
    {X, []};
dequeue([Data|Queue]) ->
    {D, Q} = dequeue(Queue),
    {D, [Data|Q]}.

is_empty(Queue) ->
    Queue == [].

length(Queue) ->
    erlang:length(Queue).

dequeue/1 的操作速度受到伫列的长度影响。

加强效能的伫列

我们可以用双堆叠来做一个伫列，使得有些时候，伫列资料输出的速度与资料输入的速度对称。

-module(queue).
-export([create/0, enqueue/2, dequeue/1, is_empty/1, length/1]).

% 本模組使用 -export/1 設定句，指定只釋出五個函數。
% 也就是當使用 queue 模組時，只能用 queue:create/0 、
% queue:enqueue/2 、 queue:dequeue/1 、 queue:is_empty/1 、
% queue:length/1 等五個函數。

create() ->
    { stack:create(), stack:create() }.

enqueue(Data, Queue) ->
    {InQ, OutQ} = Queue,
    { stack:push(Data,InQ), OutQ}.

dequeue(Queue) ->
    {InQ, OutQ} = Queue,
    case OutQ of
        [] ->
            {D,S} = stack:pop(reverse(InQ)),
            {D, {[],S}};
        [Data|Q] ->
            {Data, {InQ,Q}}
    end.

reverse(Xs) ->
    reverse(Xs, []).
reverse([], Acc) ->
    Acc;
reverse([X|Xs], Acc) ->
    reverse(Xs, [X|Acc]).

is_empty(Queue) ->
    {InQ, OutQ} = Queue,
    InQ == [] and OutQ == [].

length(Queue) ->
    {InQ, OutQ} = Queue,
    erlang:length(InQ) + erlang:length(OutQ).