栈的顺序存储实现及链式存储实现

顺序存储实现

#include <stdlib.h>
#include <stdlib.h>
#define size 100
typedef int ElemType;
typedef struct stack{
    ElemType s[size];
    int top;
}stack;
void Init(stack **S)//初始化
{
    *S=(stack *)malloc(sizeof(stack));
    (*S)->top=0;
}
int push(stack *S,ElemType e)//入栈
{
    if(S->top==size)
    {
        printf("栈已满！\n");
        return 0;
    }
    S->s[++S->top]=e;//从s[1]开始存储
    return 1;
}
int pop(stack *S,ElemType *e)//出栈
{
    if(S->top==0)
    {
        printf("栈已空！\n");
        return 0;
    }
    *e=S->s[S->top--];
    return 1;
}
int main()
{
    stack *S;
    Init(&S);
    for(int i=0;i<=9;i++)
    {

        push(S, i);
        printf("%d ",i);
    }
    printf("\n");
    int x;
    for(int i=0;i<=9;i++)
    {
        pop(S,&x);
        printf("%d ",x);
    }
    return  0;
}

链式存储实现

#include <stdlib.h>
#include <stdlib.h>
#define size 100
typedef int ElemType;
typedef struct StackNode {//链的结点结构体定义
    ElemType data;
    struct StackNode *next;
}StackNode,*StackNodePtr;

typedef struct LinkStack{
    StackNodePtr top;//指向当前栈顶结点的指针
    int count;//当前栈中的元素个数
}LinkStack;

void Init(LinkStack *S)
{
    S=(LinkStack*)malloc(sizeof(LinkStack));
    S->top=NULL;
    S->count=0;
}
int push(LinkStack *S,ElemType e)
{
    StackNode *node;//创建一个新的栈元素结点
    node=(StackNode*)malloc(sizeof(StackNode));
    node->data=e;
    node->next=S->top;//新结点的指针指向底部的结点,最底部的结点的next为null
    S->top=node;//栈顶指针指向新的栈顶结点
    S->count++;
    return 1;
}
int pop(LinkStack *S,ElemType *e)
{
   if(S->count==0)
   {
       printf("栈已空\n");
       return 0;
   }
   *e=S->top->data;//*e保存栈顶元素
   StackNodePtr p;
   p=S->top;//将当前栈顶结点赋给指针p
   S->top=S->top->next;
   free(p);
   S->count--;
    return 1;

}
int main()
{
     LinkStack *S;
    Init(&S);
    for(int i=0;i<=9;i++)
    {

        push(S, i);
        printf("%d ",i);
    }
    printf("\n");
    int x;
    for(int i=0;i<=9;i++)
    {
        pop(S,&x);
        printf("%d ",x);
    }
    return  0;
}

对于链栈来说，基本不存在栈满的情况，除非内存不够用了，对于空栈的判断，代码中是根据count的数值来判断的，当然也可以通过栈顶指针S->top,当其为null时栈为空，回到栈的初始化状态。