顺序栈的C++实现

栈是一种类似于线性表的数据结构,不过栈比线性表更具有局限性,因为它只能从一个方向上进行添加删除元素(节点)的操作,而且每一次只能对栈顶这个元素进行操作.
由于栈这种数据结构的特点,对于在线性表中常用的例如设定当前位置,向前向后,以及开头以及结尾的定位操作在栈中变得没有任何意义,因为我们永远只能访问到栈顶值.不过由于这样,栈这种结构的实现变得比线性表要简单得多.
同线性表类似,栈的创建可以用顺序栈,以及链式栈来实现,不过在此我们仅介绍顺序栈的实现方法,从下面的代码中可以看出,它的实现是非常简单的.在此我们先创建一个纯虚类Stack,它包含了栈结构的典型操作,而真正实现栈的AStack类却以该类作为基类进行定义.

Stack.h文件:
////////////////////////////////////////////////////////////////////////////
//Stack.h文件,用于创建一个Stack纯虚类,它封装了"栈"这种数据结构的操作.
//栈是一种常用的数据结构,不过它每次只能从特定的方向添加或删除一个元素(节点),
//所以在任何状态下,我们只能得到或操作栈顶的元素.由于这个原因,实现栈比实现顺
//序要容易得多.在计算机中,栈具有很广泛的用途,而人们把栈也称为后进先出数据结
//构.
////////////////////////////////////////////////////////////////////////////
template <class type>
class Stack
{
public:
 virtual void Clear() =0;  //清空栈中的所有数据,即初始化.
 virtual bool Push(const type&) =0; //入栈.
 virtual bool Pop(type&) =0;  //出栈.
 virtual bool TopValue(type&) =0; //获取栈顶值.
 virtual int Length() const =0;  //返回栈中的元素个数.
};

AStack.h文件:
////////////////////////////////////////////////////////////////////////////
//AStack.h文件,栈的顺序表方式实现.
////////////////////////////////////////////////////////////////////////////
#include "Stack.h"
template <class type>
class AStack :public Stack<type>  //创建AStack类,它公有继承于Stack类.
{
public:
 AStack(int);
 ~AStack();
 void Clear();
 bool Push(const type&);
 bool Pop(type&);
 bool TopValue(type&);
 int Length() const;
private:
int size;    //栈的最大长度
 int top;    //它表示一个索引,即栈顶第一个空闲位置的索引.
 type *listArray;   //栈数据结构的起始地址.
};

AStack.cpp文件:
////////////////////////////////////////////////////////////////////////////
// AStack.cpp文件,它用于实现AStack类中的成员函数,以及对栈这种数据结构的使用
//方法的演示.
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include "AStack.h"
using namespace std;
template <class type>
AStack<type>::AStack(int sz)
{
 size=sz;     //最大元素个数.
 top=0;      //第一个空间闲位置为0,说明此时为空栈.
 listArray=new type[size];   //创建一块内存,用于存放栈中的数据.
}
template <class type>
AStack<type>::~AStack()
{
 delete [] listArray;    //释放栈的内存.
}
template <class type>
void AStack<type>::Clear()
{
 top=0;      //第一个空闲位置为0,说明此时为空栈.
}
template <class type>
bool AStack<type>::Push(const type &val)
{
 if(top==size)
  return false;    //如果栈满,那么返回false,表示不能添加.
 listArray[top++]=val;    //从栈顶插入一个元素,并使栈顶加1.
 return true;     //从栈顶位置添加元素成功.
}
template <class type>
bool AStack<type>::Pop(type &val)
{
 if(top)
 {
  val=listArray[--top];
  return true;    //如果栈不空,那么弹出栈顶值.
 }
 return false;     //否则返回false,表示栈空.
}
template <class type>
bool AStack<type>::TopValue(type &val)
{
 if(top)
 {
  val=listArray[top-1];
  return true;    //返回栈顶值.
 }
return false;
}
template <class type>
int AStack<type>::Length() const
{
 return top;     //返回实际在栈中的元素个数.
}
/////////////////////////////////////////////////////////////////////////////////
//下面的代码用于测试栈式数据结构的所有功能.
/////////////////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
 AStack<int> val(20);
 int value,len;
 val.Push(1);
 val.Push(2);
 val.Push(3);     //将三个数值压栈.
 len=val.Length();
 for(int i=0;i<len;i++)
 {
  val.Pop(value);
  cout<<value<<"  ";   //三个数值出栈并输出.
 }
 cout<<endl;
 val.Clear();     //清空栈.
 val.Push(1);
 val.Push(2);
 val.Push(3);
 val.Push(4);     //将四个数值压栈.
 len=val.Length();    //返回栈中保存的元素个数.
 for(int i=0;i<len;i++)
 {
  val.TopValue(value);   //得到栈顶值.
  cout<<value<<"  ";   //输出
  val.Pop(value);    //弹出栈顶值.
  cout<<value<<"  ";   //输出.
 }
 cout<<endl;
 return 0;
}
从上面可以看出,顺序栈的实现远远比顺序表的实现更加简单,在计算机中有大量的数据结构用栈或者以它为基础实现了很多的应用.

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1757.html 转载请保留链接。