堆栈的实现之顺序存储，链式存储

  栈的顺序存储结构由一个一维数组和一个记录栈顶元素位置的变量组成，
    另外还可以用一个变量来存储堆栈的最大容量Maxsize

/**
    栈的顺序存储结构由一个一维数组和一个记录栈顶元素位置的变量组成，
    另外还可以用一个变量来存储堆栈的最大容量Maxsize
*/

/**
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define error -1
const int Maxsize = 100;
typedef int ElementType;
typedef int Position;
typedef struct SNode * PtrToSNode;
struct SNode
{
    ElementType *Data;
    Position Top;
    int Maxsize;
};
typedef PtrToSNode Stack;
Stack CreateStack(int Maxsize);
bool IsFull(Stack S);
bool Push(Stack S,ElementType X);
bool IsEmpty(Stack S);
ElementType Pop(Stack S);
int main()
{
    Stack S=CreateStack(Maxsize);
    for(int i=1;i<50000000;i+=i)
        Push(S,i);
    for(int i=0,T=S->Top;i<=T+5;++i)
    {
        auto tem=Pop(S);
        if(tem!=error)
            printf("%d ",tem);
    }
    return 0;
}

Stack CreateStack(int Maxsize)
{
    Stack S=(Stack) malloc(sizeof(SNode));
    S->Data=(ElementType *) malloc(Maxsize * sizeof(ElementType));
    S->Top=-1;
    S->Maxsize=Maxsize;
    return S;
}

bool IsFull(Stack S)
{
    return (S->Top==S->Maxsize-1);
}

bool Push(Stack S,ElementType X)
{
    if(IsFull(S))
    {
        printf("堆栈满\n");
        return false;
    }
    else
    {
        S->Data[++(S->Top)]=X;
        return true;
    }
}

bool IsEmpty(Stack S)
{
    return (S->Top==-1);
}

ElementType Pop(Stack S)
{
    if(IsEmpty(S))
    {
        printf("堆栈空\n");
        return error;
    }
    else
    {
        return (S->Data[(S->Top)--]);
    }
}
*/

 堆栈的链式存储实现：

/**
    堆栈的链式存储实现：
*/


#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define error NULL
typedef int ElementType;
const ElementType inf=1e9;
typedef struct SNode * PtrToLNode;
//  这里的位置就是数组的整型下标，从0开始，前面提到的位序是指第几个，从1开始
struct SNode
{
    ElementType data;
    PtrToLNode next;
};
typedef PtrToLNode Position;
typedef PtrToLNode Stack;

Stack CreateStack();
bool IsFull(Stack S);
bool Push(Stack S,ElementType X);
bool IsEmpty(Stack S);
ElementType Pop(Stack S);

int main()
{
    Stack S=CreateStack();
    for(int i=1;i<50000000;i+=i)
        Push(S,i);
    while(!IsEmpty(S))
    {
        auto tem=Pop(S);
        if(tem!=inf)
            printf("%d ",tem);
    }
    return 0;
}

//带头结点的堆栈
Stack CreateStack()
{
    Stack S;
    S=(Stack) malloc(sizeof(SNode));
    S->next=NULL;
    return S;
}

bool Push(Stack S,ElementType X)
{
    Position Temcell;
    Temcell=(PtrToLNode) malloc(sizeof(SNode));
    Temcell->data=X;
    Temcell->next=S->next;
    S->next=Temcell;
    return true;
}

bool IsEmpty(Stack S)
{
    return (S->next==NULL);
}

ElementType Pop(Stack S)
{
    Position FirstCell;
    ElementType TopElem;
    if(IsEmpty(S))
    {
        printf("堆栈空\n");
        return inf;
    }
    else
    {
        FirstCell=S->next;
        TopElem=FirstCell->data;
        S->next=FirstCell->next;
        free(FirstCell);
        return TopElem;
    }
}