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).