スタック構造

スタック構造とは

 スタック構造とは、最後に入れたデータが最初に出ていくようなデータ構造のことで、コンピュータの中では割合頻繁に使われるデータ構造の一つです。
 ここでは、リストを利用してスタック構造のリストを利用する方法を考えます。

push操作

 まず、リストに項目を追加する操作を考えます。
 beginning of theListを使う事で、簡単にリストの頭に値を追加する事ができます。

set theList to {}
pushItem(theList, 3)
pushItem(theList, 4)
pushItem(theList, 5)

theList
-->{5, 4, 3}

on pushItem(theList, theItem)
	set beginning of theList to theItem
end pushItem

pop操作

 次に、リストから項目を取り出す操作を考えます。
 rest of theListで最初の項目を除いたリストの残りを得る事ができるので、それを利用して、項目の数を減らしています。
 また、項目が残っていない場合に-1を返すようにしています。

set theList to {2, 5, 6}
set theItem to popItem(a reference to theList)

{theItem, theList}
--> {2, {5, 6}}

on popItem(ref2List)
	if (count ref2List) = 0 then return -1
	
	set tmp to first item of ref2List
	set contents of ref2List to rest of ref2List
	return tmp
end popItem

オブジェクトにしてはどうだろう

 スタック構造のデータを頻繁に使うとなると、いっそオブジェクトにした方が面倒が無いと思います。
 オブジェクト属性としてリストを抱えておけばスクリプトの見通しがいいし、大域変数では無いので変数の衝突を避ける事もできます。
 もちろん、複数のスクリプトオブジェクトを作った場合、各々の属性は独立していますからデータとして問題なく使えます。
 以下のスクリプトでは、ハンドラ呼び出しによる定義を使い、pushItem/popItem/getNumberの命令が使えるようになっています。

set xObj to makeStack({1, 2, 3})
set yObj to makeStack({1, 2, 3})

tell xObj
	set theItem to popItem()
	pushItem(5)
	pushItem(4)
	set n to getNumber()
end tell

{{theItem, n, theList_ of xObj}, {popItem() of yObj, getNumber() of yObj, theList_ of yObj}}
--> {{1, 4, {4, 5, 2, 3}}, {1, 2, {2, 3}}}

on makeStack(initList)
	script
		property theList_ : initList
		
		on pushItem(theItem)
			set beginning of theList_ to theItem
		end pushItem
		
		on popItem()
			if (count theList_) = 0 then return -1
			
			set tmp to first item of theList_
			set theList_ to rest of theList_
			return tmp
		end popItem
		
		on getNumber()
			number of theList_
		end getNumber
	end script
end makeStack

 ここではスタック構造を取り上げてみましたが、AppleScriptは用途に応じて適切なデータ構造とそれに対する命令を作る事ができるようになっています。
 既に用意されている値やオブジェクトに不満を感じたら、このように自作してしまうのも手です。プログラム本のなかにはデータ構造だけを解説した書籍もあるくらいで、なかなかに奥が深いジャンルであります。


2000-07-02 -2002-01-06