登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

顺序结构实现双向栈  

2006-02-23 21:48:07|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
//问题描述:
// 假设以顺序存贮结构实现一个双向栈,即在一维存贮空间中存在着两个栈,
//它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作:
//初始化initstack(tws)入栈push(tws,i)和出栈pop(tws,i)的算法,其中
//i为0或1,用以分别指示设在数组两端的两个栈。

数组实现的双向栈
测试文件

///////////////////////////
//以下为用数组实现的双向栈的类定义
//数组实现的双向栈.h
//用数组实现的双向栈

enum DirectionFlag
{
R,L
};
template<class DataType>
class dstack
{
private:
unsigned sizepp;//空间再分配时的空间增量
private:
typename DataType* pdata;
unsigned size;//记录当前空间的大小
int l_top;
int r_top;
public:
dstack(unsigned InitSize=64,unsigned SizePlus=16):l_top(-1),r_top(InitSize),size(InitSize),sizepp(SizePlus)
{
pdata=new typename DataType[size];
}
~dstack()
{
delete []pdata;
}
public:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Push(const typename DataType& data,DirectionFlag flag)
{
if(flag==R)//在右边的栈中压入
{
return RightPush(data);
}
else//flag==L 在左边压栈
{
return LeftPush(data);
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Pop(const DirectionFlag flag)
{
if(flag==R)//右边弹栈
{
return RightPop();
}
else//在左边弹栈
{
return LeftPop();
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
typename DataType& Top(const DirectionFlag flag)
{
if(flag==R)
return RightTop();
else
return LeftTop();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Clear()
{
l_top=-1;
r_top=size;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Empty()
{
return (RightEmpty()&&LeftEmpty());
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Empty(const DirectionFlag flag)
{
if(flag==R)
return RightEmpty();
else
return LeftEmpty();
}
public:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool RightPush(const typename DataType& data)
{
if(r_top-l_top>=2)//还有空间剩余
{
--r_top;
pdata[r_top]=data;
return true;
}
else
{
if(re_alloc()==false)
return false;
--r_top;
pdata[r_top]=data;
return true;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool LeftPush(const typename DataType& data)
{
if(r_top-l_top>=2&&l_top>=0&&r_top<size)//还有空间剩余且在合法的范围内
{
++l_top;
pdata[l_top]=data;
return true;
}
else
{
if(re_alloc()==false)
return false;
++l_top;
pdata[l_top]=data;
return true;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool LeftPop()
{
if(!LeftEmpty())
{
--l_top;
return true;
}
else
{
return false;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool RightPop()
{
if(!RightEmpty())
{
++r_top;
return true;
}
else
{
return false;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
typename DataType& RightTop()
{
return pdata[r_top];
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
typename DataType& LeftTop()
{
return pdata[l_top];
}

bool LeftEmpty()
{
return l_top<0;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool RightEmpty()
{
return r_top>=size;
}

private:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool re_alloc()
{
typename DataType* temp=new typename DataType[size+sizepp];
if(temp==NULL)//空间分配失败
{
return false;
}
for(int i(0);i<=l_top;++i)
temp[i]=pdata[i];
for(i=size-1;i>=r_top;--i)
temp[i+sizepp]=pdata[i];
size+=sizepp;
r_top+=sizepp;

delete []pdata;
pdata=temp;
return true;
}
};

//////////////////////////
//以下为测试文件

//3_15.cpp
#include<iostream>
#include"数组实现的双向栈.h"

using namespace std;

int main()
{
dstack<int> s1(3,1);
if(s1.Empty(R)!=true&&s1.Empty(L)!=true)
cout<<"wrong1"<<endl;
else
cout<<"ok1"<<endl;
//////////////////////////////
cout<<"以下将输出 0 ~ 7"<<endl;
s1.Push(0,L);cout<<s1.Top(L)<<' ';
s1.Push(1,L);cout<<s1.Top(L)<<' ';
s1.Push(2,L);cout<<s1.Top(L)<<' ';
s1.Push(3,L);cout<<s1.Top(L)<<' ';
s1.Push(4,L);cout<<s1.Top(L)<<' ';
s1.Push(5,L);cout<<s1.Top(L)<<' ';
s1.Push(6,L);cout<<s1.Top(L)<<' ';
s1.Push(7,L);cout<<s1.Top(L)<<endl;
////////////////////////////////
s1.Pop(L);
if(s1.Top(L)!=6)
cout<<"wrong1-1"<<endl;
else
cout<<"ok1-1"<<endl;
////////////////////////////////
if(s1.Empty(L)!=false||s1.Empty(R)!=true)
cout<<"Wrong2"<<endl;
else
cout<<"ok2"<<endl;
//////////////////////////
while(s1.Empty(L)!=true)
{
s1.Pop(L);
}
if(s1.Empty(L)!=true)
cout<<"wrong3"<<endl;
else
cout<<"ok3"<<endl;
/////////////////////////////
s1.Push(8,R);
if(s1.Top(R)!=8)
cout<<"wrong4"<<endl;
else
cout<<"ok4"<<endl;
/////////////////////////////////
s1.Clear();
if(s1.Empty()!=true)
cout<<"wrong5"<<endl;
else
cout<<"ok5"<<endl;
return 0;
}
  评论这张
 
阅读(1569)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018