【数据结构】栈

栈

栈是限制在一端进行插入和删除操作的线性表，其主要特点为“后进先出，先进后出”。

允许操作的一段称为“栈顶”，固定不能够进行操作的一段称为“栈底”。

顺序栈相关程序：

sqstack.h

typedef int data_t;

typedef struct {
    data_t *data;
    int maxlen;                              //方便能够自定义栈的数据大小
    int top;
}sqstack;

sqstack * stack_create(int len);             //创建顺序栈   输入：顺序栈的数据大小   返回值：顺序栈的栈顶指针（未成功创建返回NULL）
int stack_push(sqstack * s, data_t value);   //入栈操作
int stack_empty(sqstack *s);                 //判断栈是否为空栈
int stack_full(sqstack *s);                  //判断栈是否为满栈
data_t stack_pop(sqstack *s);                //出栈操作    返回值：出栈的数据
data_t stack_top(sqstack *s);                //查看栈顶元素的数据
int stack_clear(sqstack *s);                 //清空栈
int stack_free(sqstack *s);                  //释放顺序栈所占的内存空间

sqstack.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sqstack.h"

sqstack * stack_create(int len) {
    sqstack * s;

    if ((s =(sqstack *)malloc(sizeof(sqstack))) == NULL) {
        printf("malloc sqstack failed\n");
        return NULL;
    }

    if ((s->data = (data_t *)malloc(len * sizeof(data_t)))==NULL) {
        printf("malloc data failed\n");
        free(s);
        return NULL;
    }

    memset(s->data, 0, len*sizeof(data_t));
    s->maxlen = len;
    s->top = -1;

    return s;
}

int stack_push(sqstack * s, data_t value) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }

    if (s->top == s->maxlen-1) {
        printf("stack is full\n");
        return -1;
    }

    s->top++;
    s->data[s->top] = value;

    return 0;
}

/*
 *@ret 1-empty
 * */
int stack_empty(sqstack *s) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }
    return (s->top == -1 ? 1 : 0);
}

/*
 * @ret 1-full
 * */
int stack_full(sqstack *s) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }
    return  (s->top == s->maxlen-1 ? 1 : 0);
}

data_t stack_pop(sqstack *s) {
    
    if (s->top == -1) {
        printf("stack is empty\n");
        return -1;
    }
    
    s->top--; 
    return (s->data[s->top+1]);
}

data_t stack_top(sqstack *s) {
    return (s->data[s->top]);
}

int stack_clear(sqstack *s) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }
    
    s->top = -1;
    return 0;
}

int stack_free(sqstack *s) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }
    
    if (s->data != NULL) 
        free(s->data);
    free(s);

    return 0;
}

链式栈相关程序：

linkstack.h

typedef int data_t;

typedef struct node {
    data_t data;
    struct node *next;
}listnode, *linkstack;

linkstack stack_create();　　　　　　　　　　　　//链式栈的创建  返回值栈顶指针（未成功创建返回NULL）
int stack_push(linkstack s, data_t value);　 //入栈操作
data_t stack_pop(linkstack s);               //出栈操作  返回出栈的数据
int stack_empty(linkstack s);                //判断是否栈为空
data_t stack_top(linkstack s);               //查看栈顶的元素
linkstack stack_free(linkstack s);           //释放链式栈的存储空间

linkstack.c

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

linkstack stack_create() {
    linkstack s;

    s = (linkstack)malloc(sizeof(listnode));
    if (s == NULL) {
        printf("malloc failed\n");
        return NULL;
    }
    s->data = 0;
    s->next = NULL;

    return s;
}

int stack_push(linkstack s, data_t value) {
    linkstack p;

    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }

    p = (linkstack)malloc(sizeof(listnode));
    if (p == NULL) {
        printf("malloc failed\n");
        return -1;
    }
    p->data = value;
    //p->next = NULL;
    p->next = s->next;
    s->next = p;

    return 0;
}

data_t stack_pop(linkstack s) {
    linkstack p;
    data_t t;

    p = s->next;
    s->next = p->next;

    t = p->data;

    free(p);
    p =NULL;

    return t;
}

int stack_empty(linkstack s) {
    if (s == NULL) {
        printf("s is NULL\n");
        return -1;
    }

    return (s->next == NULL ? 1 : 0);
}

data_t stack_top(linkstack s) {
    return (s->next->data);
}

linkstack stack_free(linkstack s) {
    linkstack p;

    if (s == NULL) {
        printf("s is NULL\n");
        return NULL;
    }

    while (s != NULL) {
        p = s;
        s = s->next;
        printf("free:%d\n", p->data);
        free(p);
    }

    return NULL;
}