第二十四天（数据结构：栈和队列）队列实践请看下一篇

栈和队列栈 ： 是限定在表尾进行插入和删除操作的线性表实现是一回事，但是必须要满足栈的基本特点它的设计思路是:先进后出，后进先出栈有两端1 栈顶(top) ：插入数据删除数据都只能在这一端访问也只能访问栈顶2 栈底(bottom) : 栈底是不会动实现栈我们就需要实现如下操作：init    初始化这个栈top     返回栈顶元素，但是不出栈empty   判断栈是否为空size    栈里面有多少个元素push    入栈pop     出栈clear   清空这个栈destory 销魂这个栈我们可以使用链式结构或者顺序结构来实现这个栈1 链式 --- 利用链表,对链表的操作进行限定struct stacknode{int data;struct stacknode * prev;};//利用头节点来搞定stacknode的管理  对于用户来说是最友好的struct ListStack{struct stacknode * top;//指向栈顶元素的int num;//为了防止爆栈(溢出)  我们可以弄一个最大值来进行限定int maxnum;.....};2 顺序 --- 利用数组，对数组的操作进行限定struct ArrayStack //同样是为了管理我们的栈的{//int stack[];//容纳所有的栈里面的元素int * stack;//我给你开辟一个数组出来让stack去保存int  top;//指向栈顶元素的int num;//为了防止爆栈(溢出)  我们可以弄一个最大值来进行限定int maxnum;.....};先弄一遍链式栈，请实现顺序栈队列：是限定在表尾进行插入，在表头删除操作的线性表实现是一回事，但是必须要满足队列的基本特点它的设计思路是:先进先出，后进后出有两头：队头(front)，删除操作在这一边进行队尾(rear),插入操作在这一边进行
队列在实现的时候有两种1 链式队列 --- 链表实现 -> 不存在假溢出struct queuenode{int data;struct queuenode * next;//做尾插};//利用头节点来搞定queuenode的管理  对于用户来说是最友好的struct ListQueue{struct stacknode * front;//指向队头元素的 删除的时候砍掉这个头struct stacknode * rear;//指向队尾元素的  插入的时候往rear的后面进行插入int num;//队列里面有多少个元素//为了防止爆队(溢出)  我们可以弄一个最大值来进行限定int maxnum;.....};2 顺序队列 --- 利用数组来实现根据队列的特点我们可以知道入队出队front rear都是在++总有一个时候队列没有满，但是入队的时候已经溢出了 -- 假溢出因此我们设计顺序队列一定要设计为循环队列让前面已经出队的地方可以继续容纳新的元素设计循环队列有几种思路1 用num来表示我们的循环队列里面有多少个元素只要num没有达到它的最大容纳上限我就可以继续入队只是rear跑到最后去了之后，我们需要让它从头开始2 我们可以利用front 和 rear来进行元素个数，是否为空，是否满的判断-> 没有变量num来对我们的元素个数来进行判断 ---- 这种是常用的根据我们的分析可以知道 当front == rear的时候没有办法判断这个队列是空的还满的因此循环队列设计的时候，我们实际队列容纳个数要比最大的容纳个数少一个maxnum == 5,实际队列容纳就是 5 - 1公式：队空的判断:front == rear队满的判断:(rear + 1) % maxnum == front队列的元素个数：(rear - front + maxnum) % maxnumstruct ArrayQueue //同样是为了管理我们的队列的{//int queue[];//容纳所有的队列里面的元素int * queue;//我给你开辟一个数组出来让queue去保存int  front;//指向对头元素的 指向要删除的数据int rear;//指向队尾元素 指向要插入的数据//为了防止爆队(溢出)  我们可以弄一个最大值来进行限定int maxnum; // 实际队列容纳个数为 maxnum - 1};队列需要实现如下操作init        初始化这个队列front       返回队头元素，但是不出队empty       判断是否为空full        判断是否为满size        返回元素个数push(inqueue)        入队pop(outqueue)         出队clear       清空这个队列destory     销毁这个队列搞定循环队列，然后将链式队列写出来栈最基本的应用就是算表达式的值2+3*5-6*7+8*9-10%3=你输入2+3*5-6*7+8*9-10%3=这个字符串简单一点就用scanf(%s) -> 中间就不能有空格回车就会得到它的结果gets -> 从终端获取一行字符串不想要警告，请使用fgets链式栈

.h与.c

#ifndef __LISTSTACK_H__
#define __LISTSTACK_H__#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int LS_DataType;
#define LS_ERRORVALUE (LS_DataType)(1 << 31)//栈的错误值//节点
typedef struct LS_Node
{LS_DataType _data;//栈的数据struct LS_Node * _next;//写next就用头插
}LS_Node;//管理栈的头节点
typedef struct
{LS_Node * _top;//栈顶  插入删除访问都这一端int _num;//现在栈里面有多少个元素int _maxnum;//最大的容纳个数
}ListStack;//init    初始化这个栈
//maxnum:程序员限定的最大元素个数   如果小于等于0   默认10000000
ListStack * ListStack_init(int maxnum);//top     返回栈顶元素，但是不出栈
//返回LS_ERRORVALUE表示失败
LS_DataType ListStack_top(ListStack * st);//empty   判断栈是否为空
bool ListStack_empty(ListStack * st);//full    判断是不是满了
bool ListStack_full(ListStack * st);//size    栈里面有多少个元素
int ListStack_size(ListStack * st);//push    入栈  失败返回false
bool ListStack_push(ListStack * st,const LS_DataType data);//pop     出栈 没有返回元素  失败返回false
//如果你有需求返回元素也是可以的
//如果你要得到出栈元素 你需要先top再pop
bool ListStack_pop(ListStack * st);//clear   清空这个栈
//callback是否要处理数据，传NULL为不处理
void ListStack_clear(ListStack * st,void (*callback)(const LS_DataType));//destory 销魂这个栈
//callback是否要处理数据，传NULL为不处理
void ListStack_destory(ListStack ** st,void (*callback)(const LS_DataType));#endif

#include "ListStack.h"//创建栈的节点  这个接口是不需要给用户用的
static LS_Node * LS_Node_create(const LS_DataType data)
{LS_Node * ptr = (LS_Node *)calloc(1,sizeof(LS_Node));ptr ->_data = data;return ptr;
}//init    初始化这个栈
//maxnum:程序员限定的最大元素个数   如果小于等于0   默认10000000
ListStack * ListStack_init(int maxnum)
{if(maxnum <= 0){maxnum = 10000000;}ListStack * st = (ListStack *)calloc(1,sizeof(ListStack));st ->_maxnum = maxnum;return st;
}//top     返回栈顶元素，但是不出栈
//返回LS_ERRORVALUE表示失败
LS_DataType ListStack_top(ListStack * st)
{if(ListStack_empty(st))//栈是空的 返回不了一点return LS_ERRORVALUE;return st ->_top ->_data;
}//empty   判断栈是否为空
bool ListStack_empty(ListStack * st)
{if(!st)return true;return st ->_num == 0;
}
//full    判断是不是满了
bool ListStack_full(ListStack * st)
{if(!st)return true;return st ->_num == st ->_maxnum;
}
//size    栈里面有多少个元素
int ListStack_size(ListStack * st)
{return !st ? 0 : st ->_num;
}//push    入栈  失败返回false
bool ListStack_push(ListStack * st,const LS_DataType data)
{//入栈就是一个头插if(!st || ListStack_full(st))return false;//先弄一个节点LS_Node * ptr = LS_Node_create(data);//对这个节点进行头插ptr ->_next = st ->_top;st ->_top = ptr;//将栈顶弄到新加入的节点上面来st ->_num++;return true;
}//pop     出栈 没有返回元素  失败返回false
//如果你有需求返回元素也是可以的
//如果你要得到出栈元素 你需要先top再pop
bool ListStack_pop(ListStack * st)
{if(!st || ListStack_empty(st))return false;//将top给删除LS_Node * ptr = st ->_top;//标记要删除的节点st ->_top = st ->_top ->_next;//top到后面去了st ->_num--;//数量少一个了ptr ->_next = NULL;//孤立这个节点free(ptr);return true;
}//clear   清空这个栈
//callback是否要处理数据，传NULL为不处理
void ListStack_clear(ListStack * st,void (*callback)(const LS_DataType))
{while(!ListStack_empty(st))//只要你的栈不是空的 就一直出栈{LS_DataType data = ListStack_top(st);//获取栈顶元素ListStack_pop(st);if(callback && LS_ERRORVALUE != data){callback(data);}}
}
//destory 销魂这个栈
//callback是否要处理数据，传NULL为不处理
void ListStack_destory(ListStack ** st,void (*callback)(const LS_DataType))
{if(!st)return;ListStack_clear(*st,callback);//先清空//将头节点给删除free(*st);*st = NULL;
}

顺序栈：

.h与.c

#ifndef __ARRAYSTACK_H__
#define __ARRAYSTACK_H__#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>typedef int AS_DataType;
#define AS_ERRORVALUE (AS_DataType)(1 << 31)//栈的错误值typedef struct  //同样是为了管理我们的栈的
{AS_DataType * _st_arr;//我给你开辟一个数组出来让_st_arr去保存数据int  _top;//指向栈顶元素的  下标 入栈从_top开始，栈顶元素为_top-1int _num;//为了防止爆栈(溢出)  我们可以弄一个最大值来进行限定int _maxnum;
}ArrayStack;//init    初始化这个栈
//maxnum:程序员限定的最大元素个数   如果小于等于0   默认10000000
ArrayStack * ArrayStack_init(int maxnum);//top     返回栈顶元素，但是不出栈
//返回LS_ERRORVALUE表示失败
AS_DataType ArrayStack_top(ArrayStack * st);//empty   判断栈是否为空
bool ArrayStack_empty(ArrayStack * st);//full    判断是不是满了
bool ArrayStack_full(ArrayStack * st);//size    栈里面有多少个元素
int ArrayStack_size(ArrayStack * st);//push    入栈  失败返回false
bool ArrayStack_push(ArrayStack * st,const AS_DataType data);//pop     出栈 没有返回元素  失败返回false
//如果你有需求返回元素也是可以的
//如果你要得到出栈元素 你需要先top再pop
bool ArrayStack_pop(ArrayStack * st);//clear   清空这个栈
//callback是否要处理数据，传NULL为不处理
void ArrayStack_clear(ArrayStack * st,void (*callback)(const AS_DataType));//destory 销魂这个栈
//callback是否要处理数据，传NULL为不处理
void ArrayStack_destory(ArrayStack ** st,void (*callback)(const AS_DataType));#endif

#include "ArrayStack.h"//init    初始化这个栈
//maxnum:程序员限定的最大元素个数   如果小于等于0   默认10000000
//入栈从_top开始，栈顶元素为_top-1
ArrayStack * ArrayStack_init(int maxnum)
{if(maxnum <= 0) {printf("动动你的猪脑，0和负数能存东西吗，给你开了10000000，慢慢填吧\n");maxnum = 10000000;}ArrayStack *st = (ArrayStack *)calloc(1,sizeof(ArrayStack));st ->_maxnum = maxnum;//开辟数组  用于保存数据st ->_st_arr = (AS_DataType *)calloc(st ->_maxnum,sizeof(AS_DataType));return st;
}//top     返回栈顶元素，但是不出栈
//返回LS_ERRORVALUE表示失败
AS_DataType ArrayStack_top(ArrayStack * st)
{if (ArrayStack_empty(st)) {return AS_ERRORVALUE;}return st ->_st_arr[st ->_top - 1];
}//empty   判断栈是否为空
bool ArrayStack_empty(ArrayStack * st)
{if (!st || st ->_num == 0) {return true;}return false;
}//full    判断是不是满了
bool ArrayStack_full(ArrayStack * st)
{if (!st || st ->_num == st ->_maxnum) {return true;}return false;
}//size    栈里面有多少个元素
int ArrayStack_size(ArrayStack * st)
{if (!st) {return AS_ERRORVALUE;}return st ->_num;
}//push    入栈  失败返回false
bool ArrayStack_push(ArrayStack * st,const AS_DataType data)
{if (!st || ArrayStack_full(st)) {return false;}st ->_st_arr[st ->_top] = data;st ->_top++;st ->_num++;return true;
}//pop     出栈 没有返回元素  失败返回false
//如果你有需求返回元素也是可以的
//如果你要得到出栈元素 你需要先top再pop
bool ArrayStack_pop(ArrayStack * st)
{if (ArrayStack_empty(st)) {return false;}st ->_top--;st ->_num--;return true;
}//clear   清空这个栈
//callback是否要处理数据，传NULL为不处理
void ArrayStack_clear(ArrayStack * st,void (*callback)(const AS_DataType))
{while (!ArrayStack_empty(st)) {ArrayStack_pop(st);}
}//destory 销魂这个栈
//callback是否要处理数据，传NULL为不处理
void ArrayStack_destory(ArrayStack ** st,void (*callback)(const AS_DataType))
{free((*st) ->_st_arr);free(*st);*st =NULL;}