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