很久没有更新技术blog了，所以炒下从前的冷饭。这是一个我在过去的项目中设计的数据结构。在一个矢量图浏览器中，需要缓存视图状态（实际上是起始坐标和缩放比例等参数），当用户点击向前，向后视图时，能显示相应的视图。
在过去，我们使用了一个一维的数组来缓存视图参数，但是当数组存满以后，所有缓存数据需要依次被推动前移，最前方的数据被丢弃。（溢出行为倒是有点像队列，只不过使用的时候它还是栈的特点，所以取名还是堆栈）。
为了节约移动堆栈数据时的成本（开销为O（n）），所以想到把一维数组的首尾连接成为圆环，这样当数据已经满时，不需要移动所有里面的数据，只需要把新的数据覆盖掉失效数据即可，这样就可以把时间开销从O(n)降低为O(1)了。
但是由于首尾连接成环形，但是本质上还是一个一维满栈的数据结构，所以必须设置两个指针指示栈的入口和底部的位置。此外由于视图可能回退中某个中间视图，因此还需要另一个指针，指示当前视图的位置。
实际上定义的时候所有缓存是放在一个一维数组中。上面的三个“指针”实际是数组的索引(int32)，分别用top,current,bottom表示。
private MapView[] m_views;
private int m_top;
private int m_current;
private int m_bottom;
由于逻辑上是环形，我们定义以下按照环形展开成直线以后，向左右两个方向移动指针的方法，返回新的索引位置：
在新的数据压入堆栈时，使用下面的Push方法：
当取出前一个视图时，相当于使用“向左后退到”Pop出一个数据，使用下面的GetPreviousView函数：
这里注意和栈不同之处在于，pop出来的数据在数据结构中并没有被丢弃，而是还可以用“向右前进到”继续得到。所以还存在下面的一个GetNextView函数：
以上是这个数据结构类的主要功能函数，但是实际上上面的函数的技巧性不大。我在这个类中写的最难，灵活性最大的一个方法是重设堆栈长度，也就是下面的这个方法，实际上我是花了很多时间和调试才写正确的。当然如果过去的数据全都舍弃，那么这里也就不存在什么问题了。而一旦我想要把现有数据放到新申请的新的长度的数组中时，要花费很多功夫注意复制的细节：所以重设长度时，我把它写成一个方法，而非属性。这样要考虑到的问题是，如果新的长度比现在的长度大，则现在有的数据全部可以有效复制过去，如果小，那么必然要舍弃一小部分。而且要维持现有的几个指针位置正确。
/// <summary>
/// 重新设置新的堆栈深度
/// （这个方法有些复杂，因此写成方法而不是属性）
/// </summary>
/// <param name="length"></param>
public
void
SetLength(
int
length)
{
//如果参数和当前深度相等，或者不合法，则直接返回
if(this.m_views.Length==length || length<=0)
return;
//判断是否处于空栈状态（未进入数据）
if(this.m_current<0)
{
this.m_views=new MapView[length];
return;
}
//先获取以当前位置为分界的previous和next个数
int preCount=this.PreviousViewsCount;
int nextCount=this.NextViewsCount;
//临时数据
MapView view;
//创建一个新长度的temp堆栈
MapView[] temp=new MapView[length];
//因为弹出视图时会变动current指针位置，因此先缓存current指针
int cache_current=this.m_current;
//拷贝当前视图到索引0的位置
temp[0]=this.m_views[this.m_current];
//拷贝【Next】视图
int count1=Math.Min(length-1,nextCount); //需要拷贝的next视图个数
for(int i=1;i<=count1;i++)
{
if(this.GetNextView(out view))
temp[i]=view;
}
//如果还有剩余位置，把【Previous元素】拷贝到当前队列的尾部！
int count2=Math.Min(length-1-count1,preCount);
//弹出视图之前，恢复current指针的位置！！！
this.m_current=cache_current;
for(int i=0;i<count2;i++)
{
if(this.GetPreviousView(out view))
temp[length-1-i]=view;
}
//更新top指针（这里count1肯定大于1）
this.m_top = (count1>0)? count1 : 0;
//更新bottom位置
this.m_bottom= count2>0? length-count2:0;
//更新当前指针位置
this.m_current=0;
//更新堆栈为新建堆栈
this.m_views=temp;
}
上面的方法最开始没有写对，因为也没有开始做后来的视图堆栈演示器，所以有的错误无法发现，直到后来写了演示器，才发现里面的问题，于是改正。
此外这个类还提供的属性有前视图个数，后视图个数，是否满等。
下面是演示器的截图：
在图中是一个用户定义控件，外围的蓝色箭头T表示top，红色的箭头B表示bottom，蓝色块表示current，内围的一个淡蓝色弧形线段表示的是可展开成直线的有效数据（圆头方向表示栈的顶部），现在的堆栈长度为16。
可以改变长度，可以看到改变长度以后的图形：下图中将深度重新设置为8以后，新的指针位置和数据。
下面是演示器的完整代码：包括了VS2003和vs2005的两个解决方案的版本。
http://files.cnblogs.com/hoodlum1980/CircularStackView.rar
在过去，我们使用了一个一维的数组来缓存视图参数，但是当数组存满以后，所有缓存数据需要依次被推动前移，最前方的数据被丢弃。（溢出行为倒是有点像队列，只不过使用的时候它还是栈的特点，所以取名还是堆栈）。
为了节约移动堆栈数据时的成本（开销为O（n）），所以想到把一维数组的首尾连接成为圆环，这样当数据已经满时，不需要移动所有里面的数据，只需要把新的数据覆盖掉失效数据即可，这样就可以把时间开销从O(n)降低为O(1)了。
但是由于首尾连接成环形，但是本质上还是一个一维满栈的数据结构，所以必须设置两个指针指示栈的入口和底部的位置。此外由于视图可能回退中某个中间视图，因此还需要另一个指针，指示当前视图的位置。
实际上定义的时候所有缓存是放在一个一维数组中。上面的三个“指针”实际是数组的索引(int32)，分别用top,current,bottom表示。
private MapView[] m_views;
private int m_top;
private int m_current;
private int m_bottom;
由于逻辑上是环形，我们定义以下按照环形展开成直线以后，向左右两个方向移动指针的方法，返回新的索引位置：
///
<summary>
/// 向右移动指针！
/// </summary>
/// <param name="p"> 指针当前位置 </param>
/// <returns> 指针向右移动一格的位置 </returns>
public int MoveRight( int p)
{
int p2 = p + 1 ;
if (p2 > this .m_views.Length - 1 || p2 < 0 )
p2 = 0 ;
return p2;
}
/// 向右移动指针！
/// </summary>
/// <param name="p"> 指针当前位置 </param>
/// <returns> 指针向右移动一格的位置 </returns>
public int MoveRight( int p)
{
int p2 = p + 1 ;
if (p2 > this .m_views.Length - 1 || p2 < 0 )
p2 = 0 ;
return p2;
}
在新的数据压入堆栈时，使用下面的Push方法：
public
void
Push(MapView mv)
{
// 指针前进
this .m_current = this .MoveRight( this .m_current);
this .m_views[ this .m_current] = mv;
// 判断当前位置是否“追上”了bottom（两个指针位置重叠）
// 注意在初始化时bottom指向0，并且第一次重合时,top为-1，bottom此时不移动
// 即刚刚入栈第一个数据时，三个指针位置重合，此后top和bottom永远不会重合
if ( this .m_current == this .m_bottom && this .m_top >= 0 )
this .m_bottom = this .MoveRight( this .m_bottom);
// 更新队列顶部的位置
this .m_top = this .m_current;
}
{
// 指针前进
this .m_current = this .MoveRight( this .m_current);
this .m_views[ this .m_current] = mv;
// 判断当前位置是否“追上”了bottom（两个指针位置重叠）
// 注意在初始化时bottom指向0，并且第一次重合时,top为-1，bottom此时不移动
// 即刚刚入栈第一个数据时，三个指针位置重合，此后top和bottom永远不会重合
if ( this .m_current == this .m_bottom && this .m_top >= 0 )
this .m_bottom = this .MoveRight( this .m_bottom);
// 更新队列顶部的位置
this .m_top = this .m_current;
}
当取出前一个视图时，相当于使用“向左后退到”Pop出一个数据，使用下面的GetPreviousView函数：
///
<summary>
/// 获取前一个视图数据（向堆栈的bottom方向获取）
/// 【注意】弹出失败时，内部指针不可以移动！
/// </summary>
/// <param name="mv"></param>
/// <returns></returns>
public bool GetPreviousView( out MapView mv)
{
// 设置输出值
mv = this .m_views[ this .m_current];
// 如果当前位置和bottom重合，则无法获取左侧视图
// 注意必须判断有没有视图入栈过，堆栈为空时，current指向-1
if ( this .m_current == this .m_bottom || this .m_current < 0 )
return false ;
else
{
// 弹出成功，因此更新指针位置
this .m_current = this .MoveLeft( this .m_current);
mv = this .m_views[ this .m_current];
return true ;
}
}
/// 获取前一个视图数据（向堆栈的bottom方向获取）
/// 【注意】弹出失败时，内部指针不可以移动！
/// </summary>
/// <param name="mv"></param>
/// <returns></returns>
public bool GetPreviousView( out MapView mv)
{
// 设置输出值
mv = this .m_views[ this .m_current];
// 如果当前位置和bottom重合，则无法获取左侧视图
// 注意必须判断有没有视图入栈过，堆栈为空时，current指向-1
if ( this .m_current == this .m_bottom || this .m_current < 0 )
return false ;
else
{
// 弹出成功，因此更新指针位置
this .m_current = this .MoveLeft( this .m_current);
mv = this .m_views[ this .m_current];
return true ;
}
}
这里注意和栈不同之处在于，pop出来的数据在数据结构中并没有被丢弃，而是还可以用“向右前进到”继续得到。所以还存在下面的一个GetNextView函数：
public
bool
GetNextView(
out
MapView mv)
{
// 设置out参数
mv = this .m_views[ this .m_current];
// 判断当前指针已经是顶部，则无法获取Next数据，当前指针也不向前移动
// 注意初始化时，current和top都指向-1
if ( this .m_current == this .m_top || mv.IsEmpty)
return false ;
else
{
// 获取成功，指针向前移动一格
this .m_current = this .MoveRight( this .m_current);
mv = this .m_views[ this .m_current];
return true ;
}
}
{
// 设置out参数
mv = this .m_views[ this .m_current];
// 判断当前指针已经是顶部，则无法获取Next数据，当前指针也不向前移动
// 注意初始化时，current和top都指向-1
if ( this .m_current == this .m_top || mv.IsEmpty)
return false ;
else
{
// 获取成功，指针向前移动一格
this .m_current = this .MoveRight( this .m_current);
mv = this .m_views[ this .m_current];
return true ;
}
}
以上是这个数据结构类的主要功能函数，但是实际上上面的函数的技巧性不大。我在这个类中写的最难，灵活性最大的一个方法是重设堆栈长度，也就是下面的这个方法，实际上我是花了很多时间和调试才写正确的。当然如果过去的数据全都舍弃，那么这里也就不存在什么问题了。而一旦我想要把现有数据放到新申请的新的长度的数组中时，要花费很多功夫注意复制的细节：所以重设长度时，我把它写成一个方法，而非属性。这样要考虑到的问题是，如果新的长度比现在的长度大，则现在有的数据全部可以有效复制过去，如果小，那么必然要舍弃一小部分。而且要维持现有的几个指针位置正确。
/// <summary> /// 重新设置新的堆栈深度 /// （这个方法有些复杂，因此写成方法而不是属性） /// </summary> /// <param name="length"></param>
public
void
SetLength(
int
length)
{
//如果参数和当前深度相等，或者不合法，则直接返回 if(this.m_views.Length==length || length<=0) return; //判断是否处于空栈状态（未进入数据） if(this.m_current<0) { this.m_views=new MapView[length]; return; } //先获取以当前位置为分界的previous和next个数 int preCount=this.PreviousViewsCount; int nextCount=this.NextViewsCount; //临时数据 MapView view; //创建一个新长度的temp堆栈 MapView[] temp=new MapView[length]; //因为弹出视图时会变动current指针位置，因此先缓存current指针 int cache_current=this.m_current; //拷贝当前视图到索引0的位置 temp[0]=this.m_views[this.m_current]; //拷贝【Next】视图 int count1=Math.Min(length-1,nextCount); //需要拷贝的next视图个数 for(int i=1;i<=count1;i++) { if(this.GetNextView(out view)) temp[i]=view; } //如果还有剩余位置，把【Previous元素】拷贝到当前队列的尾部！ int count2=Math.Min(length-1-count1,preCount); //弹出视图之前，恢复current指针的位置！！！ this.m_current=cache_current; for(int i=0;i<count2;i++) { if(this.GetPreviousView(out view)) temp[length-1-i]=view; } //更新top指针（这里count1肯定大于1） this.m_top = (count1>0)? count1 : 0; //更新bottom位置 this.m_bottom= count2>0? length-count2:0; //更新当前指针位置 this.m_current=0; //更新堆栈为新建堆栈 this.m_views=temp; }
上面的方法最开始没有写对，因为也没有开始做后来的视图堆栈演示器，所以有的错误无法发现，直到后来写了演示器，才发现里面的问题，于是改正。
此外这个类还提供的属性有前视图个数，后视图个数，是否满等。
下面是演示器的截图：
在图中是一个用户定义控件，外围的蓝色箭头T表示top，红色的箭头B表示bottom，蓝色块表示current，内围的一个淡蓝色弧形线段表示的是可展开成直线的有效数据（圆头方向表示栈的顶部），现在的堆栈长度为16。
可以改变长度，可以看到改变长度以后的图形：下图中将深度重新设置为8以后，新的指针位置和数据。
下面是演示器的完整代码：包括了VS2003和vs2005的两个解决方案的版本。
http://files.cnblogs.com/hoodlum1980/CircularStackView.rar
