1、栈定义

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

2、栈的特性

先进后出

3、栈的结构及实现

3.1顺序栈

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

  顺序栈是顺序存储结构实现的栈，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈操作的特殊性，还必须附设一个位置指针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<<"栈顶到栈底元素依次为："<<endl;
	for(int i=top;i>=0;i--)
		cout<<Sstack[i]<<" ";
	cout<<endl;
}

void menu(){
    cout<<"1.进栈"<<endl;
    cout<<"2.出栈"<<endl;
    cout<<"3.获取栈顶元素"<<endl;
    cout<<"4.栈置空"<<endl;
    cout<<"5.由栈顶到栈底依次输出栈元素"<<endl;
    cout<<"6.退出"<<endl;
} 

void function(int num,SeqStack *ss){
    switch(num){
        int x;
        case 1:
        	cout<<"请输入进栈元素值，多个值以空格分隔，-1为结束标志："<<endl;
            cin>>x;
            while(x!=-1){
            	ss->push(x);
            	cin>>x;
            }
            cout<<endl;
            break;
        case 2:
            cout<<"出栈栈顶元素："<<endl;
            ss->pop(x);
            cout<<x<<endl;
            cout<<"栈内元素有："<<endl;
            ss->print();
            break;
        case 3:
            cout<<"栈顶元素为："<<endl;
            ss->getTop(x);
            cout<<x<<endl; 
            cout<<endl;
            break;
        case 4:
            ss->makeEmpty();
            cout<<"栈已置空"<<endl;
            cout<<endl;
            break; 
        case 5:
        	ss->print();
            cout<<endl;
        	break;
        default:
            exit(0);
    }
}

int main(int argc, char** argv) 
{
	cout<<"学号+姓名第4周顺序栈："<<endl;
    SeqStack *ss=new SeqStack;
    int num;
    while(true){
        menu();
        cin>>num;
        function(num,ss);
    } 
    delete ss;
    return 0; 
}

 顺序栈的功能实现

#include <iostream>
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<<"栈顶到栈底元素依次为："<<endl;
	for(int i=top;i>=0;i--)
		cout<<Sstack[i]<<" ";
	cout<<endl;
}

void menu(){
    cout<<"1.进栈"<<endl;
    cout<<"2.出栈"<<endl;
    cout<<"3.获取栈顶元素"<<endl;
    cout<<"4.栈置空"<<endl;
    cout<<"5.由栈顶到栈底依次输出栈元素"<<endl;
    cout<<"6.退出"<<endl;
} 

void function(int num,SeqStack *ss){
    switch(num){
        int x;
        case 1:
        	cout<<"请输入进栈元素值，多个值以空格分隔，-1为结束标志："<<endl;
            cin>>x;
            while(x!=-1){
            	ss->push(x);
            	cin>>x;
            }
            cout<<endl;
            break;
        case 2:
            cout<<"出栈栈顶元素："<<endl;
            ss->pop(x);
            cout<<x<<endl;
            cout<<"栈内元素有："<<endl;
            ss->print();
            break;
        case 3:
            cout<<"栈顶元素为："<<endl;
            ss->getTop(x);
            cout<<x<<endl; 
            cout<<endl;
            break;
        case 4:
            ss->makeEmpty();
            cout<<"栈已置空"<<endl;
            cout<<endl;
            break; 
        case 5:
        	ss->print();
            cout<<endl;
        	break;
        default:
            exit(0);
    }
}

int main(int argc, char** argv) 
{
	cout<<"学号+姓名第4周顺序栈："<<endl;
    SeqStack *ss=new SeqStack;
    int num;
    while(true){
        menu();
        cin>>num;
        function(num,ss);
    } 
    delete ss;
    return 0; 
}