顺序堆栈的三种类定义

花了两个星期，断断续续，终于坚持把数据结构学起来了，现在总结了一下，把源程序也记录下来，以后可以常看看。

 

方法一：将data表示成指向数据类型为结构体datatype的指针变量，top为栈顶元素的下标。

 

class Stack
{private:
  DataType *data;
  int maxSize; //栈最大容量即大小，一旦定义是不变的
  int top;
 public:
//创建空栈
  void SetStack(int n);
//栈存在则栈被销毁
  void FreeStack();
//栈存在则返回栈的元素个数,即栈的长度
  int StackSize();
//判断栈是否为空
  bool StackEmpty();
//判断栈是否为满
  bool StackFull();
//栈存在且非空则返回栈的栈顶元素
  DataType Peek();
//栈存在则插入元素item为新的栈顶元素
  void Push(DataType item);
//栈存在且非空则删除栈的栈顶元素并用e返回其值
  DataType Pop(DataType e);
//栈存在则清为空栈
  void ClearStack();
// 栈的遍历
  void StackTraverse(void (*visit)(DataType *));
};

栈内函数的实现，最主要的是初始化栈和进栈，退栈。
void Stack::SetStack(int n)
{data=new DataType[n];
 if(data==NULL)
  {cout<<"overflow!\n";exit(1);}
 maxSize=n;
 top=-1;
}
void Stack::FreeStack()
{free(data);}

int Stack::StackSize()
{return(top+1);}

bool Stack::StackEmpty()
{if(top==-1) return true;
 return false;
}
bool Stack::StackFull()
{if(top==maxSize-1) return true;
 return false;
}
DataType Stack::Peek()
{if(top==-1)
  {cerr<<"栈已空!\n";exit(1);exit(1);}
 return(data[top]);
}
void Stack::Push(DataType item)
{if(top==maxSize-1)
  {cerr<<"栈已满!\n";;exit(1);}
 top++;
 data[top]=item;
}
DataType Stack::Pop(DataType e)
{if(top==-1)
  {cerr<<"栈已空!\n";exit(1);}
 top--;
 return data[top+1];
}
void Stack::ClearStack()
{top=-1;}

void Stack::StackTraverse(void (*visit)(DataType *))
{while(top!=-1){
   visit(data);top--;}
}

 

 

方法二：将base表示为指向数据结构体selemtype的指针变量，top为指向栈顶元素的指针变量。

优势：不会出现站满现象，栈大小动态变化。

class SqStack
{private:
  SElemType *base;
  SElemType *top;
  int stacksize;//栈当前大小，随着入栈元素的增加而增加，是变化的。
 public:
//构造一个空栈S
  Status InitStack(SqStack  **S);
//栈存在则栈被销毁
  Status DestroyStack();
//栈存在则清为空栈
  Status ClearStack();
//栈存在则返回true,否则false
  bool StackEmpty();
// 栈存在则返回栈的元素个数,即栈的长度
  int StackLength();
//栈存在且非空则返回栈的栈顶元素
  SElemType GetTop();
// 栈存在则插入元素e为新的栈顶元素
  Status Push(SElemType e);
// 栈存在且非空则删除栈的栈顶元素并用e返回其值
  SElemType Pop(SElemType *e);
// 栈的遍历
  void StackTraverse(void (*visit)(SElemType *));
};

Status SqStack::InitStack(SqStack **S)
{ (*S)=(SqStack *) malloc(sizeof(SqStack));
  (*S)->base=(SElemType *)malloc(STACKSIZE *sizeof(SElemType));
  if(!(*S)->base)exit(OVERFLOW);
  (*S)->top=(*S)->base;
  (*S)->stacksize=0;
  return 1;}

Status SqStack::DestroyStack()
{free(base);return 1;}

Status SqStack::ClearStack()
{stacksize=0;return 1;}

bool SqStack::StackEmpty()
{ if(stacksize==0) return true;
  else return false;
}
int SqStack::StackLength()
{ return stacksize;}
SElemType SqStack::GetTop()
{ if(top==base)
   {cerr<<"空栈!\n";exit(1);}
  return *(top-1);
}
Status SqStack::Push(SElemType e)
{ *(top++)=e;stacksize++;
  return 1;
}
SElemType SqStack::Pop(SElemType *e)
{ if(top==base)
   {cerr<<"空栈!\n";exit(1);}
  *e=*--top;
  stacksize--;
  return *e;
}
void SqStack::StackTraverse(void (*visit)(SElemType *))
{while(top!=base){
   stacksize--;visit(--top);}}

top指向是下一个元素，所以它总是指向空的元素。

方法三（数组表示）：stack表示类型为elemtype的数组，top为栈顶元素的下标，排序，mark==1升序，mark==-1降序，mark==0无序

const int LEN=40;
class Stack
{private:
  ElemType stack[LEN];
  int top;
 public:
//构造函数
  Stack(){top=0;}
//析构函数
  ~Stack(){}
//创建有序或无序栈
  void CreateStack(int m=LEN,int mark=0);
//清空栈
  void ClearStack();
//检查栈是否为空
  bool StackEmpty();
//读取栈顶元素
  ElemType Peek();
//向栈中插入元素
  void Push(const ElemType&,int m=LEN);
//从栈中删除元素
  ElemType Pop();
//检查栈是否已满
  bool StackFull(int m=LEN);
//栈的输出
  void StackPrint(int m=LEN);
};

//创建有序或无序栈
 void Stack::CreateStack(int n，int m,int mark)
 {ElemType x,a[LEN];

 int i,j;

 srand(n);由随机函数产生数组
  for(int i=0;i  for(int i=0;i  {int k=i;
   for(int j=i+1;j    if(a[k]>a[j]) k=j;
   if(k!=i)
   {x=a[k];a[k]=a[i];a[i]=x;}}
  for(int i=0;i  if(mark==1) Push(a[m-1-i]);//升序
  else
   if(mark==-1) Push(a[i]);//降序
   else Push(rand()%100);//无序
 }
//清空栈
 void Stack::ClearStack() {top=0;}
//检查栈是否为空
 bool Stack::StackEmpty() {return top==0;}
//读取栈顶元素
 ElemType Stack::Peek()
 {if(top==0) {cerr<<"栈为空!"<      exit(1);}
   return stack[top];
 }
//向栈中插入元素
 void Stack::Push(const ElemType& item,int m)
 {if(top==m) {
   cerr<<"栈已满!"<  top++;
  stack[top]=item;
 }
//从栈中删除元素
 ElemType Stack::Pop()
 {if(top==0) {
   cerr<<"栈为空!"<   top--;
   return stack[top+1];
 }
//检查栈是否已满
 bool Stack::StackFull(int m)
 {return top==m;}
//栈的输出
 void Stack::StackPrint(int m)
 {for(int i=0;i   cout< }

三种方法各有千秋，我看好方法三，