C数据结构：栈

简介

在之前的几篇文章中已经详细讲解了线性表中的 顺序表、单链表。每一种不同的数据结构都有它独特的结构和应用之处，今天将再次给大家介绍一个新的线性表：栈。

1. 栈：一种特殊的线性表，其中只允许在固定的一端进行插入和删除元素的操作。

2. 栈的原型：其中进行数据插入的和删除操作的一端称为栈顶，另一端称为栈底。

3. 栈的原则：栈中的数据元素遵守后进先出（LIFO）的原则

4. 栈的场景：在日常生活中，（电梯）就相当于一个栈，先进去的人后出，后进去的人总是先出

🔑栈的两个经典操作：
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈（入数据在栈顶）

出栈：栈的删除操作叫做出栈。（出数据也在栈顶）

顺序存储栈

顺序存储栈是栈的顺序实现。顺序栈是指利用顺序存储结构（数组）实现的栈。采用地址连续的存储空间依次存储栈中数据元素。

main.c

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

int main()
{
    sqstack*st;
    st = st_create();
    if(st == NULL)
        exit(1);
    datatype arr[] = {11,22,33,44,55,66,77,88};
    for(int i=0;i<8;i++)
    {
        st_push(st,&arr[i]);
    }
    datatype temp;
    st_travel(st);
    while(st_pop(st,&temp)==0)
    {
        printf("POP %d \n",temp);
    }
    
    st_destroy(st);
    return 0;
}

sqstack.h

#ifndef SQSTACK_H
#define SQSTACK_H
#define MAXSIZE 5
typedef int datatype;

typedef struct node_st
{
    datatype data[MAXSIZE];
    int top;
}sqstack;


sqstack* st_create(void);

int st_isempty(sqstack*);

int st_push(sqstack*,datatype*);

int st_pop(sqstack*,datatype*);

int st_top(sqstack*,datatype*);

void st_travel(sqstack*);

int st_destroy(sqstack*);

#endif

sqstack.c

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

sqstack* st_create(void)
{
    sqstack*st;
    st = malloc(sizeof(*st));
    if(st == NULL)
        return NULL;
        
    st->top = -1;
    return st;
}
int st_isempty(sqstack*st)
{
    if(st->top == -1)
        return 0;
    return 1;
}
int st_push(sqstack*st,datatype* data)
{
    if(st->top == MAXSIZE-1 )
        return -1;
    st->data[++st->top] = *data;
    return 0;
}
int st_pop(sqstack*st,datatype*data)
{
    if(st_isempty(st) == 0)
        return -1;
    *data = st->data[st->top--];
    return 0;
}
int st_top(sqstack*st,datatype*data)
{
    if(st_isempty(st )== 0)
        return -1;
    *data = st->data[st->top];

}
void st_travel(sqstack*st)
{
    if(st_isempty(st)== 0)
        return;
    for(int i=0;i<=st->top;i++)
    {
        printf("%d ",st->data[i]);
    }
    printf("\n");
}

int st_destroy(sqstack*st)
{
    free(st);
    st = NULL;
    return 0;
}

链式存储栈

本文的链式存储为对上一篇文章（链表高级篇）中的双向链表（lib2）的内容进行封装生成的二次使用，如大家感兴趣可以去上篇文章找下源码,也可以给我留言，我给大家私发代码。

main.c

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

struct score_st
{
    int id;
    char name[32];
    int math;
    int chinese;
};

void print_s(const void *record)
{
    const struct score_st*r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math ,r->chinese);

}

int main()
{
    int ret; 
    STACK* st = stack_create(sizeof(struct score_st));
    struct score_st temp;
    if(st == NULL)
        return -1;
    for(int i=0;i<5;i++)
    {
        temp.id = i;
        snprintf(temp.name,sizeof(temp.name),"std_%d",i);
        temp.math = rand()%100;
        temp.chinese = rand()%100;
        stack_push(st,&temp);
    }
    while(1)
    {
        ret = stack_pop(st,&temp);
        if(ret == -1)
            break;
        print_s(&temp);
    }

    stack_destroy(st);
    return 0;
}

stack.c

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


STACK* stack_create(int initsize)
{
    return llist_create(initsize);

}

int stack_push(STACK*ptr,const void *data)
{
    return llist_insert(ptr,data,LLIST_FORWARD);
}

static int always_match(const void*p1,const void*p2)
{
    return 0;
}
int stack_pop(STACK*ptr ,void* data)
{
    return llist_fetch(ptr,(void*)0,always_match,data);
}
void stack_destroy(STACK* ptr)
{

    return llist_destroy(ptr);
}

stack.h

#ifndef STACK_H
#define STACK_H

#include "llist.h"


typedef LLIST STACK;

STACK* stack_create(int);

int stack_push(STACK*,const void *data);

int stack_pop(STACK* ,void* daata);

void stack_destroy(STACK*);


#endif