数据结构：栈

顺序栈就是以数组作为存储结构，我们一般需要申明一个结构体里面一个存放栈顶指针一个存放栈底指针。

下面是它的算法实现。

#include <iostream>
#define MAXSIZE 100
using namespace std;
typedef struct  
{
    //结构体定义了三个变量
    //一个是栈顶指针，一个是栈底指针
    int *base;
    int *top;
    int stacksize;
}sqstack;
//栈的初始化
bool InitStack(sqstack &s)
{
    //初始化一个空栈，然后让栈顶指针指向栈底
    s.base=new int[MAXSIZE];
    if(!s.base) return false;
    s.top=s.base;
    *s.top++=1;
    *s.top++=2;
    *s.top++=3;
    s.stacksize=MAXSIZE;
    return true;
}
//入栈
bool Push(sqstack &s,int e)
{
    //判断栈是否满了
    if(s.top-s.base==s.stacksize) return false;
    //注意s.top其实不是存储的栈顶元素，它在栈顶元素的上面一个，所以是先赋值后加
    *s.top++=e;
    return true;
}
//出栈
bool Pop(sqstack &s,int &e)
{
    if(s.top==s.base) return false;
    //出栈就是把栈顶元素先减1然后在赋值
    e=*--s.top;
    return true;
}
//打印栈内容
void PrintStack(sqstack s)
{
    int a=s.top-s.base;//有多少元素可以通过两个地址相减就可以得到（相减是得到差多少元素）
    while(a--) cout  << s.base[a]<<endl;
}
//取栈顶元素
bool GetTop(sqstack s,int &e)
{
    if(s.top==s.base) return false;
    e=*--s.top;
    return true;
}
int main()
{	
    sqstack *s=new sqstack;
    if(InitStack(*s))   cout<<"初始化成功！"<<endl;
    PrintStack(*s);
    if(Push(*s,4)) cout<<"入栈成功！"<<endl;
    PrintStack(*s);
    int e=0;
    if(Pop(*s,e)) cout <<"出栈值为："<<e<<endl;
    PrintStack(*s);
    if(GetTop(*s,e)) cout <<"栈顶值为："<<e<<endl;
    system("pause");
}

链栈的实现  下面是它的示意图

#include <iostream>
#define MAXSIZE 100
using namespace std;
typedef struct  StackNode
{
    //定义了栈的结构体，一个存数据，一个存指针
    int data;
    struct  StackNode *next;
}StackNode,*LinkStack;
//链栈的初始化
bool InitStack(LinkStack &s)
{
    //这里s其实就是栈顶指针，指向栈顶元素
    s=NULL;
    return true;
}
//链栈的入栈
bool Push(LinkStack &s,int e)
{
    LinkStack p=new StackNode;
    //入栈就是自己申请一块空间然后让s指向块空间
    //这块空间指向原来s指向的那块空间
    p->data=e;
    p->next=s;
    s=p;
    return true;
}
//打印链栈
bool PrintStack(LinkStack s)
{
    if(s==NULL) return false;
    LinkStack p=s;
    while(p)
    {
        cout<<p->data<<endl;
        p=p->next;
    }
    cout<<"-----------------"<<endl;
}
//遍历输出链表
void TravelList(LinkStack p)
{
    if(p==NULL) return;
    else
    {
        cout<<p->data;
        TravelList(p->next);
    }
}
//链栈的出栈
bool Pop(LinkStack &s)
{
    //出栈就是s指向s原来指向的空间的next指针
    if(s==NULL) return false;
    LinkStack p=s;
    p=s;
    s=p->next;
    delete p;
    return true;
}
int main()
{	
    LinkStack *s=new LinkStack;
    if(InitStack(*s)) cout<<"初始化成功！"<<endl;
    Push(*s,3);
    Push(*s,2);
    Push(*s,1);
    TravelList(*s);
    Pop(*s);
    PrintStack(*s);
    system("pause");
}