数据结构06 ------栈和链栈

       栈是线性表的一种特殊的存储结构。它是以先进后出（FILO:  first int last out）的方式来存储数据。

        top为栈顶指针，栈顶指针实际上不是指针，它是用来记录栈顶位置 。但是我们在这里用程序来实现栈，就用一个int类型的变量来记录栈顶位置。实际上，内存中的运行时栈，也有栈指针，只不过这个栈指针是用一个寄存器来记录栈顶位置的。

#include

#define N 7

typedef int datatype;

typedef struct stack{
    datatype data[N];    //数据保存处
    int top;            //栈顶指针
} stack_t,*pstack_t;

pstack_t stack_init(void)
{
    //开空间
    pstack_t p = (pstack_t)malloc(sizeof(stack_t));
    if(p==NULL){
        perror("malloc error");
        return NULL;
    }
    
    //赋值
    p->top = -1;
    
    //返回
    return p;
}

int push(pstack_t p,datatype d)
{
    //判断是否栈满
    if(p->top+1 == N){        //因为一开始，p->top == -1，所以这里为p->top+1
        printf("栈满n");
        return -1;
    }
    
    p->top++;
    p->data[p->top]=d;
    
    return 0;
}

int pop(pstack_t p,datatype *d)
{
    //判断栈是否为空
    if(p->top == -1){
        printf("栈空n");
        return -1;
    }
    
    *d = p->data[p->top];
    p->top--;
    
    return 0;
    
}

void display(pstack_t p)
{
    int i;
    printf("栈的结果：n");
    
    for(i=p->top;i>=0;i--){
        printf("| %d |n",p->data[i]);
    }
    printf("n");
}

由于顺序栈的大小会被限制，所以使用链表来实现栈

#include

typedef int datatype;

typedef struct link{
    datatype data;
    struct link *next;
} link_t,*plink_t;

int push(plink_t *top,datatype d)
{
    //创建节点
    plink_t node = (plink_t)malloc(sizeof(link_t));
    if(node==NULL){
        perror("malloc error");
        return -1;
    }
    
    //赋值
    node->data = d;
    //让其指针域指向top
    node->next = *top; 
    
    *top = node;
    
    return 0;
}

int pop(plink_t *p,datatype *d)
{
    //判断 栈 是否为空
    if(*p == NULL){
        printf("栈空n");
        return -1;
    }
    
    //存起来
    plink_t node = *p;
    
    //top往后移动
    (*p) = (*p)->next;    
    
    //将数据 传出  
    *d = node->data;
    
    //释放node
    node->next = NULL;
    free(node);
    
    return 0;
    
}

void display(plink_t p)
{
    
    printf("栈的结果：n");
    while(p!=NULL){
        printf("| %d |n",p->data);
        p = p->next;
    }
    printf("n");
}