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