数据结构 双向链表(副堆栈)的实现

class fl.lang.ClsError extends Error {
 var cls:String;
 function ClsError(_cls:String, msg:String) {
  cls = _cls;
  message = msg;
 }
 function toString() {
  return (name+":\n\tclass : "+cls+"\n\tmessage : "+message);
 }
}

import fl.lang.ClsError;
class fl.util.Stack extends fl.Obj {
 private var data:Array;
 //数据
 private var right:Number;
 //MAX指针
 public function get length() {
  //堆栈的长度
  return (right);
 }
 public function clone():Stack {
  var result:Array = data.slice(0, right);
  return new Stack(result);
 }
 public function Stack(arr:Array) {
  //构造函数 ，arr :一个1维数组
  data = new Array();
  if (arr) {
   data = arr.slice();
   right = arr.length-1;
   return;
  }
  right = 0;
 }
 public function search(key:Object):Boolean {
  for (var i = 0; i<right; i++) {
   if (data[i] == key) {
    return true;
   }
  }
  return false;
 }
 public function init():Void {
  //初始化
  data.splice(0);
  right = 0;
 }
 public function get isEmpty():Boolean {
  //判断是否为空
  if (right == 0) {
   return (true);
  }
  return (false);
 }
 public function push(obj:Object):Void {
  //入栈
  data.push(obj);
  right ++;
 }
 public function pop():Object {
  //出栈
  if (!isEmpty) {
   right--;
   return (data[right]);
  }
  throw new ClsError("Stack", "pop is empty");
 }
 public function getTop():Object {
  //返回顶端
  return (data[right]);
 }
 public function dispose():Void {
  //释放内存
  data.splice(right);
 }
 public function trace():Void {
  //打印堆栈
  trace("Trace Stack-----");
  for (var i = 0; i<right; i++) {
   trace("\tItem "+i+" : "+data[i]);
  }
  trace("/Trace Stack");
 }
}

/*************************************************************************
*双向链表
*v 1.0
*player 7
*2006/1/2
/************************************************************************/
import fl.lang.ClsError;
import fl.util.Stack;
class fl.util.LinkList extends fl.Obj {
 /*
 *存放数据
 *data[i]={value:数据， next:右指针， previous:左指针}
 *data[0].last=null
 *data[max].next=null
 */
 private var data:Array;
 private var closeList:Stack; //已删除的下标的集合
 private var first:Number;  //开始指针
 private var last:Number;  //结束指针
 private var _length:Number;  //链表的长度
 public function get length():Number {
  return _length;
 }
 /*
 *构造函数
 *LinkList(一个1维数组)
 *LinkList()
 */
 public function LinkList(arr:Array) {
  closeList = new Stack();
  data = new Array();
  if (arr) {   //LinkList(一个1维数组)
   var arrLen:Number = arr.length;
   for (var i:Number = 0; i < arrLen; i++) {
    data.push({value:arr[i], next:i + 1, previous:i - 1});
   }
   first = 0;
   last = arrLen - 1;
   data[first].previous = null;
   data[last].next = null;
   _length = arrLen;
   return;
  }
       //LinkList()
  first = last = 0;
 }
 /*
 *得到index处的值
 *get(index)
 */
 public function get(index:Number):Object {
  if (index >= _length || index < 0) {
   throw new ClsError("LinkList", "get index is outside");
  }
  var pos:Number = find(index);
  return data[pos].value;
 }
 /*
 *设置index处的值
 *set(index,value)
 */
 public function set(index:Number, value:Object):Void {
  if (index < 0) {
   throw new ClsError("LinkList", "set index is outside");
  }
  //当超界时                                                             
  if (index >= _length) {
   var len:Number = index - _length + 2;
   var pos:Number = last;
   for (var i:Number = 1; i < len; i++) {
    data[i + pos] = {value:undefined, next:i + pos + 1, previous:i + pos - 1};
   }
   data[index].value = value;
   data[index].next = null;
   data[last].next = _length;
   last = index;
   _length = index + 1;
   return;
  }
  var pos:Number = find(index);
  data[pos].value = value;
 }
 /*
 *出栈
 *pop()
 */
 public function pop():Object {
  if (_length == 0) {
   //当链表为空时
   throw new ClsError("LinkList", "pop this is empty");
  }
  //不为空时                            
  try {
   return data[last].value;
  } finally {
   closeList.push(last);
   last = data[last].previous;
   _length--;
  }
 }
 /*
 *入栈
 *pop()
 */
 public function push(value:Object):Void {
  var pos:Number = getPos();
  data[pos] = {value:value, next:null};
  data[pos].previous = last;
  data[last].next = pos;
  last = pos;
  _length++;
 }
 /*
 *从头插入
 *shift()
 */
 public function shift():Object {
  if (_length == 0) {
   //当链表为空时
   throw new ClsError("LinkList", "shift this is empty");
  }
  //不为空时                            
  try {
   return data[first].value;
  } finally {
   closeList.push(first);
   first = data[first].next;
   _length--;
  }
 }
 /*
 *从头删除
 *unshift()
 */
 public function unshift(value:Object):Void {
  var pos:Number = getPos();
  data[pos] = {value:value, previous:null};
  data[pos].next = first;
  data[first].previous = pos;
  first = pos;
  _length ++;
 }
 /*
 *查找一个对象
 *search()
 */
 public function search(key:Object):Boolean {
  var pos:Number = first;
  var i:Number = _length;
  while (-- i) {
   if(data[pos].value == key) {
    return true;
   }
   pos = data[pos].next;
  }
  return false;
 }
 /*
 *在index增加一个值
 *addItem(index, value)
 */
 public function addItem(index:Number, value:Object):Void {
  if (!index) throw new ClsError("LinkList", "addItem index is null");
  var pos:Number = find(index);                                             
  switch (pos) {
  case first :
   unshift(value);
   break;
  case last :
   push(value);
   break;
  default :
   var newPos:Number;
   try {
    newPos = Number(closeList.pop());
   } catch (e) {
    newPos = data.length;
   }
   data[newPos] = {value:value, previous:pos, next:data[pos].next};
   data[pos].next = newPos;
   data[data[newPos].next].previous=newPos
   _length ++;
  }
 }
 /*
 *在index删除一个值
 *removeItem(index)
 */
 public function removeItem(index:Number):Void {
  if (!_length) throw new ClsError("LinkList", "removeItem this is empty");
  if (!index) throw new ClsError("LinkList", "removeItem index is null");
  var pos:Number = find(index);                                     
  switch (pos) {
  case first :
    pop();
  break;
  case last :
    shift();
  break;
  default :
   var previous:Number = data[pos].previous;
   var next:Number = data[pos].next;
   data[previous].next = next;
   data[next].previous = previous;
   closeList.push(pos);
   _length --;
  }
 }
 /*
 *从index开始，向后查找
 *indexOf(key,index)
 */
 public function indexOf(key:Object,index:Number):Number {
  if (!key) throw new ClsError("LinkList", "indexOf key is null");
  if (!index) index = 0;
  var pos:Number = first;
  for (var i:Number = 0; i < index; i++) {
    pos = data[pos].next;
  }
  for (var i:Number=_length-index; i>0; i--) {
   if(key == data[pos].value) return pos;
   pos = data[pos].next;
  }
 }
 /*
 *从index开始，向前查找
 *lastIndexOf(key,index)
 */
 public function lastIndexOf(key:Object,index:Number):Number {
  if (!key) throw new ClsError("LinkList", "lastIndexOf key is null");
  if (!index) index = 0;
  var pos:Number = last;
  for (var i:Number = 0; i < index; i++) {
    pos = data[pos].previous;
  }
  for (var i:Number=_length-index; i>0; i--) {
   if(key == data[pos].value) return pos;
   pos = data[pos].previous;
  }
 }
 //克隆
 public function clone():LinkList {
  var result:LinkList=new LinkList();
  var pos:Number=first
  for (var i=0; i<_length; i++) {
   result.push(data[pos].value);
   pos=data[pos].next;
  }
  return result;
 }
 public function toString():String {
  return toArray().toString();
 }
 public function join(separator:String):String {
  return toArray().join(separator);
 }
 public function toArray():Array {
  var result:Array = new Array();
  var pos:Number = first;
  var i:Number = _length;
  while (--i) {
   result.push(data[pos].value);
   pos = data[pos].next;
  }
  return result;
 }
 //得到一个空地址
 private function getPos():Number {
  var result:Number
  try { result = Number(closeList.pop()); }
  catch (e) { result = data.length; }
  return result;
 }
 //得到第index的下标
 private function find(index:Number):Number {
  var pos:Number;                                             
  if (index > _length / 2) {
   //从后向前   
   var pos = last;
   for (var i:Number = _length - index - 1; i > 0; i--) {
    pos = data[pos].previous;
   }
  }else{
   //从前向后                                                            
   var pos = first;
   for (var i:Number = 0; i < index; i++) {
    pos = data[pos].next;
   }
  }
  return pos;
 }
}