//问题描述：
// 假设以顺序存贮结构实现一个双向栈，即在一维存贮空间中存在着两个栈，
//它们的栈底分别设在数组的两个端点。试编写实现这个双向栈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;
}
评论