栈和队列
栈 ： 是限定在表尾进行插入和删除操作的线性表
实现是一回事，但是必须要满足栈的基本特点
它的设计思路是:先进后出，后进先出
栈有两端
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) % maxnum
struct 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-1
int _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;
}