C++ 数据结构与算法----栈的功能实现

 栈（stack）是限定仅在表的一端进行插入、删除操作的线性表，允许插入和删除的一端称为栈顶（Top），表的另一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。

先进后出

 栈作为一种特殊的线性表，在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。我们称顺序存储的栈为顺序栈，链式存储的栈为链栈。

  顺序栈是顺序存储结构实现的栈，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈，top=maxsize-1为满栈。（maxsize表示最大长度）

顺序栈的存储结构的进栈和出栈过程如下图：

 3.1.2顺序栈的实现

（1）构造函数

SeqStack::SeqStack()
{
    top=-1;
    RSize=maxSize;
    Sstack=new T[RSize];
    if(Sstack==NULL)
    {
    	cout<<"分配内存失败，退出";
    	exit(1);
    }
}

（2）析构函数

SeqStack::~SeqStack()
{
	if(Sstack!=NULL)
    	delete[] Sstack;
}

（3）入栈操作

void SeqStack::push(T x)
{ 
    if(isFull()) 
        overflow();
    Sstack[++top]=x;
}

（4）出栈操作

bool SeqStack::pop(T& x)
{ 
    if(isEmpty())
        return false;
    x=Sstack[top--];
    return true;
}

（5）获栈顶操作

bool SeqStack::getTop(T& x)
{ 
    if(isEmpty())
        return false;
    x=Sstack[top];
    return true;
}

（6）判空操作

bool SeqStack::isEmpty()
{
    return (top==-1)?true:false;
}

（7）判满操作

bool SeqStack::isFull()
{
    return (top==RSize-1)?true:false;
}

（8）计算元素个数操作

int SeqStack::getSize()
{
    return top+1;
}

（9）置栈空操作

void SeqStack::makeEmpty()
{ 
    top=-1;
}

（10）由栈顶到栈底依次输出元素

void SeqStack::print()
{
	cout<<"栈顶到栈底元素依次为："<=0;i--)
		cout<>x;
            while(x!=-1){
            	ss->push(x);
            	cin>>x;
            }
            cout<pop(x);
            cout<print();
            break;
        case 3:
            cout<<"栈顶元素为："<getTop(x);
            cout<makeEmpty();
            cout<<"栈已置空"<print();
            cout<>num;
        function(num,ss);
    } 
    delete ss;
    return 0; 
}

 顺序栈的功能实现

#include 
using namespace std;
#define maxSize 50
typedef int T;
//顺序栈
class SeqStack{
	private:
        T *Sstack;//栈使用内存首地址
        int top;//栈顶指针
        int RSize;//栈分配元素个数
        void overflow();
    public:
        SeqStack();
        ~SeqStack();
        void push(T x);
        bool pop(T& x);
        bool getTop(T& x);
        bool isEmpty();
        bool isFull();
        int getSize();
        void makeEmpty();
        void print();
};


//构造
SeqStack::SeqStack()
{
    top=-1;
    RSize=maxSize;
    Sstack=new T[RSize];
    if(Sstack==NULL)
    {
    	cout<<"分配内存失败，退出";
    	exit(1);
    }
}
//析构
SeqStack::~SeqStack()
{
	if(Sstack!=NULL)
    	delete[] Sstack;
}
//栈溢出时扩大栈容量
void SeqStack::overflow()
{
	if(Sstack!=NULL)
	{
	    T *newArray=new T[RSize+20];
	    if(newArray!=NULL)
	    {
		    for(int i=0;i<=top;i++)
		    {
		        newArray[i]=Sstack[i];
		    }
		    RSize+=20;
		    delete []Sstack;
		    Sstack=newArray;
	    }
	}
}
//进栈
void SeqStack::push(T x)
{ 
    if(isFull()) 
        overflow();
    Sstack[++top]=x;
}
//出栈
bool SeqStack::pop(T& x)
{ 
    if(isEmpty())
        return false;
    x=Sstack[top--];
    return true;
}
//获取栈顶元素
bool SeqStack::getTop(T& x)
{ 
    if(isEmpty())
        return false;
    x=Sstack[top];
    return true;
}
//栈是否空
bool SeqStack::isEmpty()
{
    return (top==-1)?true:false;
}
//栈是否满
bool SeqStack::isFull()
{
    return (top==RSize-1)?true:false;
}
//栈实际元素个数
int SeqStack::getSize()
{
    return top+1;
}
//置栈空
void SeqStack::makeEmpty()
{ 
    top=-1;
}
//由栈顶到栈底依次输出栈元素
void SeqStack::print()
{
	cout<<"栈顶到栈底元素依次为："<=0;i--)
		cout<>x;
            while(x!=-1){
            	ss->push(x);
            	cin>>x;
            }
            cout<pop(x);
            cout<print();
            break;
        case 3:
            cout<<"栈顶元素为："<getTop(x);
            cout<makeEmpty();
            cout<<"栈已置空"<print();
            cout<>num;
        function(num,ss);
    } 
    delete ss;
    return 0; 
}