ActionScript入門Wiki - 配列と連結リストによるスタックの実装

トップページ > アルゴリズム > 配列と連結リストによるスタックの実装

概要

スタックは先に入れたものを後から取り出すという決まりがあるデータ構造です。
(逆にいうと、後に入れたものを先に取り出すデータ構造)

積み重なった食器の出し入れを思い浮かべてもらうと分かりやすいと思います。

スタックの命令は少なくとも以下の二つが用意されています。

データの追加を行うpush()
データの取り出しを行うpop()

プログラム

配列によるスタック操作

var stack:Array = [];
stack.push("あ"); // "あ"
stack.push("い"); // "あ", "い"
stack.push("う"); // "あ", "い", "う"
 
stack.pop(); // "あ", "い"
stack.pop(); // "あ"

配列ではpush()とpop()が実装されているので、配列をスタックとして利用することが可能です。

連結リストによるスタック操作

連結リストを利用してスタックを実装することが出来ます。
下記コードでは、片方向リストであるLinkedListクラスを利用してスタックを実装しています。

Node.as

package
{
	public class Node
	{
		public var next:Node;
		public var value:*;
 
		public function Node(value:*)
		{
			this.value = value;
		}
	}
}

スタックにはどんなデータでも格納できるようにするため、NodeクラスのvalueをObject型に変更します。

Stack.as

package
{
	public class Stack
	{
		private var list:LinkedList;
 
		public function Stack()
		{
			list = new LinkedList();
		}
 
		public function push(data:*):void
		{
			list.insertFirst(new Node(data));
		}
 
		public function pop():*
		{
			if (empty())
			{
				return null;
			}
			else
			{
				var node:Node = list.getNode(0);
				list.remove(node);
				return node.value;
			}
		}
 
		public function empty():Boolean
		{
			return list.empty;
		}
	}
}

Main.as

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var stack:Stack = new Stack();
			stack.push(0);
			stack.push("1");
			stack.push(new Sprite());
 
			trace(stack.pop()); // [object Sprite]
			trace(stack.pop()); // 1
			trace(stack.pop()); // 9
			trace(stack.pop()); // null
		}
	}
}

Rubyスクリプト

class Stack
  def initialize
    @list = LinkedList.new
  end
 
  def push(data)
    @list.insertFirst Node.new(data)
  end
 
  def pop
    if @list.empty?
      return nil
    else
      node = @list[0]
      @list.remove(node)
      return node.value
    end
  end
 
  def empty?
    return @list.empty?
  end
end
 
stack = Stack.new
stack.push [1, 2, 3]
stack.push "あ"
stack.push 999
 
p stack.pop # 999
p stack.pop # "\u3042"
p stack.pop # [1, 2, 3]
p stack.pop # nil

リンク元(0)

添付ファイル

s1.png