栈
先进后出、后进先出
一、系统栈
大小：8MB
1、局部变量
2、未经初始化为随机值
3、代码执行到变量定义时为变量开辟空间
4、当变量的作用域结束时回收空间
5、函数的形参和返回值
6、函数的调用关系、保护现场和恢复现场
7、栈的增长方向，自高向低增长
二、栈：FILO
怎样具备先进后出、后进先出？
类似羽毛球桶
FILO（栈）
只允许从一端进行数据的插入和删除的线性存储结构（线性表）（一对一的线性存储结构，与顺序表、链式表类似）
插入：入栈、压栈 — 栈顶（允许操作）
删除：出栈、弹栈 — 栈底（不允许操作）
顺序表——顺序栈
满增栈 满减栈 空增栈 空减栈
入栈时操作方法不同
满、空栈
栈顶所在位置是否存有元素
增、减栈
取决于栈增长的方向
增：栈顶由低地址向高地址
减：栈顶由高地址向低地址
链式表——链式栈
栈顶、栈底
三.栈的基本操作：
注：只针对于链式栈
1.创建栈
5 LINKSTACK_LIST *creat_link()6 {7 LINKSTACK_LIST *plist = malloc(sizeof(LINKSTACK_LIST));8 if(NULL == plist)9 {10 perror("fail to malloc!");11 return NULL;12 }13 plist->phead = NULL;14 plist->clen = 0;15 16 return plist;17 }
2.入栈（头插）
26 int push_head_linkstack(LINKSTACK_LIST *plist,DATA_TYPE data)27 {28 LINKSTACK_NODE *pnode = malloc(sizeof(LINKSTACK_NODE));29 if(NULL == pnode)30 {31 perror("fail to malloc");32 }33 pnode -> data = data;34 pnode ->pnext = NULL;35 36 pnode ->pnext = plist->phead;37 plist->phead = pnode;38 39 plist->clen++;40 return 0;41 }
3.出栈
42 /* 出栈 shanchu*/43 int pop_head_delete(LINKSTACK_LIST *plist)44 {45 46 LINKSTACK_NODE *save = malloc(sizeof(LINKSTACK_NODE)); 47 LINKSTACK_NODE *ptmp = NULL;48 if(is_empty_linkstack(plist))49 {50 printf("kong ");51 return 0;52 }53 else54 {55 ptmp = plist->phead ;56 if(ptmp->pnext == NULL)57 {58 plist->phead = NULL;59 save->data = ptmp->data;60 printf("删除的值:%d \n",save->data);61 free(ptmp);62 }63 else64 {65 plist -> phead = ptmp -> pnext;66 save->data = ptmp->data;67 printf("删除的值:%d \n",save->data);68 free(ptmp);69 }70 // free(save);71 }72 }
4.获取栈顶元素
93 /*获取栈顶元素*/94 int linkstack_top_msg(LINKSTACK_LIST *plist)95 {96 LINKSTACK_NODE *p = malloc(sizeof(LINKSTACK_NODE));97 LINKSTACK_NODE *ptmp = NULL;98 if(is_empty_linkstack(plist))99 {
100 return 0;
101 }
102 else
103 {
104 ptmp = plist->phead;
105 p = ptmp;
106 printf("顶端元素:%d \n",p->data);
107 }
108
109 }
5.清空栈
110 /*清空栈*/
111 int linkstack_msg_isempty(LINKSTACK_LIST *plist)
112 {
113 LINKSTACK_NODE *ptmp = plist->phead;
114 if(is_empty_linkstack(plist))
115 {
116 return 0;
117 }
118 else
119 {
120 while(ptmp!=NULL)
121 {
122 ptmp = ptmp -> pnext;
123 pop_head_delete(plist);
124 }
125 }
126 }
6.销毁栈
127 /*销毁*/
128 int linkstack_destory(LINKSTACK_LIST *plist)
129 {
130 linkstack_msg_isempty(plist);
131 free(plist);
132 }
133
7.测试遍历.
74 /*遍历*/75 void list_for_each(LINKSTACK_LIST *plist)76 {77 if(is_empty_linkstack(plist))78 {79 printf("空");80 return ;81 }82 LINKSTACK_NODE *ptmp = plist->phead;83 84 while(ptmp != NULL)85 {86 printf("%d ",ptmp->data);87 ptmp = ptmp -> pnext;88 89 }90 putchar('\n');91 return ;92 }
四、队列：FIFO
概念
允许从一端进行数据插入，而另一端进行数据删除的线性表
特性
先进先出、后进后出
应用场景：缓冲区（数据缓存）
为了解决高速设备和低速设备交互时速度不匹配问题，进行缓存（缓冲）
队列的基本操作
1.创建队列
5 /*创建队列*/6 QUEUE_LIST *creat_link()7 {8 QUEUE_LIST *plist = malloc(sizeof(QUEUE_LIST));9 if(NULL == plist)10 {11 perror("fail to malloc!");12 return NULL;13 }14 plist->phead = NULL;15 plist->preal = NULL;16 plist->clen = 0;17 18 return plist;19 }
2.入队
25 /*入队*/26 int push_tail_queue(QUEUE_LIST *plist,DATA_TYPE data)27 {28 29 QUEUE_NODE *pnode = malloc(sizeof(QUEUE_NODE));30 if(NULL == pnode)31 {32 perror("fail to malloc");33 return 0;34 }35 pnode->data = data;36 pnode ->pnext =NULL;37 38 if(plist->preal != NULL)39 {40 plist->preal->pnext = pnode;41 plist->preal = pnode;42 }43 else 44 {45 plist->preal = pnode;46 plist->phead = pnode;47 }48 plist->clen++;49 }
3.出队
50 /*出队*/51 int pop_tail_delete(QUEUE_LIST *plist)52 {53 QUEUE_NODE *ptmp;54 QUEUE_NODE *save;55 if(is_empty_queue(plist))56 {57 printf("kong ");58 return 0;59 }60 else61 { 62 if(plist->phead->pnext ==NULL) //仅有一个数据63 {64 free(plist->phead);65 plist->phead = plist->preal =NULL;66 }67 else//多个数据68 {69 ptmp = plist->phead->pnext;70 save = ptmp;71 free(plist->phead);72 plist->phead = ptmp;73 printf("对头第一个数据:%d \n",save->data);74 }75 plist->clen--;76 }77 }78
4.清空队列
114 /*清空队列*/
115 int queue_empty(QUEUE_LIST *plist)
116 {
117 QUEUE_NODE *ptmp = plist->phead;
118 if(is_empty_queue(plist))
119 {
120 return 0;
121 }
122 else
123 {
124 while(ptmp!=NULL)
125 {
126 ptmp = ptmp -> pnext;
127 pop_tail_delete(plist);
128 }
129
130 }
131
132 }
5.获取队列队头的数据
96 /*获取队头信息*/97 int queue_top_msg(QUEUE_LIST *plist)98 {99 QUEUE_NODE *p=malloc(sizeof(QUEUE_NODE));
100 QUEUE_NODE *ptmp;
101
102 if(is_empty_queue(plist))
103 {
104 return 0;
105 }
106 else
107 {
108 ptmp = plist->phead;
109 p = ptmp;
110 printf("队头数据: %d \n",p->data);
111 }
112
113 }
6.销毁队列
133 /*销毁队列*/
134 int queue_destort(QUEUE_LIST *plist)
135 {
136 queue_empty(plist);
137 free(plist);
138 }
7.测试（遍历）
79 /*遍历*/80 void queue_for_each(QUEUE_LIST *plist)81 {82 if(is_empty_queue(plist))83 {84 printf("空");85 return ;86 }87 QUEUE_NODE *ptmp = plist->phead;88 while(ptmp != NULL)89 {90 printf("%d ",ptmp->data);91 ptmp=ptmp->pnext;92 }93 putchar('\n');94 return ;95 }
