顺序堆栈与链式堆栈的区别与实现

/*
堆栈也分为顺序栈和链式堆栈，堆栈只能对栈的一端进行操作
入栈和出栈操作均在这一端，叫做栈顶，为了操作方便，引入
了栈顶指示器
顺序堆栈的特点：
1.时间复杂度为O(1)
2.存储空间是限定大小的
3.操作比较简单和方便
链式堆栈的特点：
1.时间复杂度也为O(1),但撤销操作的时间复杂度为O(n)
*/
顺序堆栈的实现

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct stack{
    int data[MAXSIZE];
    int top;
}stack;

//初始化堆栈
int init(stack *s)
{
    s->top=0;
}
//是否为空
int isEmpty(stack *s)
{
    if(s->top<=0) return 0;
    else
        return 1;
}
//入栈
int push(stack *s,int a)
{
    if(s->top>=MAXSIZE){
        printf("堆栈已满。\n");
        return 0;
    }
    s->data[s->top]=a;
    s->top++;
    return 1;
}
//出栈
int out(stack *s)
{
    if(s->top<=0){
        printf("堆栈为空。\n");
        return 0;
    }
    s->top--;
    return s->data[s->top];

}
//取栈顶元素
int get(stack *s)
{
    if(s->top>=MAXSIZE){
        printf("堆栈空。\n");
        return 0;
    }
    return s->data[s->top-1];
}
int main()
{
    int i;
    stack s;
    init(&s);
    for(i=0;i<MAXSIZE;i++){
        push(&s,i);
    }
    for(i=0;i<MAXSIZE;i++){
        printf("%d ",out(&s));
    }
    printf("\n");
    return 0;
}

//链式堆栈的实现
/*
若把链式堆栈设计成带头节点的结构
则入栈和出栈操作的是head->next
头指针参数可以设计成节点的指针类型
若把链式堆栈设计成不带头节点的，则插入
和删除操作的改变都是头指针的的值，则头指针参数
必须设计成节点的双重指针。
这里把链式堆栈设计成带头节点的结构
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct Lnode{
    int data;
    struct Lnode *next;
}Lnode;
//初始化
void init(Lnode **head)
{
    *head=(Lnode*)malloc(sizeof(Lnode));
    (*head)->next=NULL;
}
//非空否
int isEmpty(Lnode *l)
{
    if(l->next==NULL) return 0;
    else return 1;
}

//入栈
void push(Lnode *l,int a)
{
    Lnode *p;
    p=(Lnode *)malloc(sizeof(Lnode));
    p->data=a;

    p->next=l->next;//新的节点入栈
    l->next=p;//新的节点成为新的栈顶元素
}


//出栈
int out(Lnode *l)
{
    if(l->next==NULL){
        printf("栈为空.\n");
        return 0;
    }
    Lnode *p=l->next;//构造一个指针指向栈顶元素
    int d;
    d=p->data;//获得数据
    l->next=p->next;//改变栈顶元素

    free(p);//释放p
    return d;
}
//取栈顶元素
int get(Lnode *l)
{
    if(l->next==NULL){
        printf("stack is null\n");
        return;
    }
    return l->next->data;
}
//撤销空间
void destroy(Lnode *l)
{
    Lnode *p,*p1;
    p=l->next;
    while(p!=NULL){
        p1=p;
        p=p->next;
        free(p1);
    }
}

int main()
{

    Lnode *l;
    init(&l);
    int i;
    for(i=0;i<MAXSIZE;i++){
        push(l,i);
    }
    printf("栈顶：%d\n",get(l));
    while(isEmpty(l)){
        printf("%d ",out(l));
    }
    printf("\n");
    return 0;
}