一、概念
1.栈只允许在栈顶位置入栈和出栈元素，链表可以在任意位置插入和删除元素，栈和队列只允许在指定位置插入和删除元素
2.链表、栈和队列都是一种线性结构（一对一），栈和队列是一种特殊的表状结构
二、栈
1.基础概念
先进后出，后进先出
栈顶：允许入栈和出栈的一端称为栈顶
栈底：不允许入栈和出栈的一端称为栈底
入栈（压栈）：将元素放入栈顶位置
出栈（弹栈）：将栈顶元素取出
栈针：记录栈顶位置的标记
2.分类：
（1）顺序栈：
增栈：栈的方向自低向高增长 减栈：栈的方向自高向低增长
空栈：栈针指向要入栈的位置 满栈：栈针指向栈顶元素的位置
常见顺序栈： 空增栈、空减栈、满增栈、满减栈
此图为空减栈
①顺序栈的实现
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__
typedef int datatype; //存放数据的类型
typedef struct stack
{
datatype *pdata; //存放数据空间首地址
int top; //栈顶元素位置
int tlen; //最多存放元素个数
}seqstack;
#endif
②顺序栈的创建
申请存放标签的空间，申请存放数据的空间
seqstack *create_seqstack(int len)
{
seqstack *ptmpstack = NULL;
//申请标签空间
ptmpstack = malloc(sizeof(seqstack));
if (NULL == ptmpstack)
{
perror("fail to malloc");
return NULL;
}
//申请存放数据的空间
ptmpstack->pdata = malloc(sizeof(datatype) * len);
if (NULL == ptmpstack->pdata)
{
perror("fail to malloc");
return NULL;
}
ptmpstack->top = 0;
ptmpstack->tlen = len;
return ptmpstack;
}
③ 顺序栈的销毁：
销毁存放数据的空间，销毁存放标签的空间
int destroy_seqstack(seqstack **pptmpstack)
{
free((*pptmpstack)->pdata);
free((*pptmpstack));
*pptmpstack = NULL;
return 0;
}
（注意先后顺序）
④是否为空栈:栈针为0即为空栈
int is_empty_seqstack(seqstack *ptmpstack)
{
return 0 == ptmpstack->top;
}
⑤是否为满栈：栈针与tlen相同即为满栈
int is_full_seqstack(seqstack *ptmpstack)
{
return ptmpstack->tlen == ptmpstack->top;
}
⑥ 压栈：将元素放入栈顶位置，栈针位置++
int push_seqstack(seqstack *ptmpstack, datatype tmpdata)
{
if (is_full_seqstack(ptmpstack))
{
return -1;
}
ptmpstack->pdata[ptmpstack->top++] = tmpdata;
return 0;
}
⑦出栈：栈针位置--，将栈顶元素出栈
datatype pop_seqstack(seqstack *ptmpstack)
{
if (is_empty_seqstack(ptmpstack))
{
return -1;
}
return ptmpstack->pdata[--ptmpstack->top];
}
（2）链式栈
使用链表的思想实现链式栈，参考单向链表节点定义，压栈使用头插法，出栈返回链表第一个有效节点的值，并删除该节点，在主函数循环出栈，销毁栈参考单向链表的销毁
linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
//创建空白节点
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}//初始化节点中的值
ptmpnode->pnext = NULL;
//返回空白节点地址
return ptmpnode;
}
/* 判断顺序栈是否为空 */
int is_empty_linkstack(linknode *phead)
{
//判断空白节点后面还有没有节点
return NULL == phead->pnext;
}/* 压栈 */
int push_linkstack(linknode *phead, datatype tmpdata)
{
linknode *ptmpnode = NULL;
//头插法
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;
return 0;
}/* 出栈 */
datatype pop_linkstack(linknode *phead)
{datatype retval;
linknode *ptmpnode = NULL;
if (is_empty_linkstack(phead))
{
return -1;
}//删除第一个有效元素
ptmpnode = phead->pnext;
phead->pnext = ptmpnode->pnext;
retval = ptmpnode->data;
free(ptmpnode);
//返回数据
return retval;}
/* 销毁栈 */
int destroy_linkstack(linknode **pphead)
{
linknode *ptmpnode = NULL;
linknode *pfreenode = NULL;
ptmpnode = pfreenode = *pphead;
while (ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pfreenode);
pfreenode = ptmpnode;
}
*pphead = NULL;
return 0;
}
三、队列
1.基础概念
先进先出，后进后出
队头：出队的一端
队尾：入队的一端
入队：将元素放入队列末尾
出队：将元素从队头中取出
2.分类
（1）循环队列
①定义
typedef int datatype;
typedef struct queue
{
datatype *pdata; //存放数据空间的首地址
int head; //头下标
int tail; //尾下标
int tlen; //最多存放元素个数
}seqqueuee
②循环队列创建
seqqueue *create_seqqueue(int len)
{
seqqueue *ptmpqueue = NULL;
ptmpqueue = malloc(sizeof(seqqueue));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pdata = malloc(sizeof(datatype) * len);
if (NULL == ptmpqueue->pdata)
{
perror("fail to malloc");
return NULL;
}ptmpqueue->head = 0;
ptmpqueue->tail = 0;
ptmpqueue->tlen = len;
return ptmpqueue;
}
③ 循环队列销毁
int destroy_seqqueue(seqqueue **pptmpqueue)
{
free((*pptmpqueue)->pdata);
free(*pptmpqueue);
*pptmpqueue = NULL;
return 0;
}
④判断循环队列是否为空
int is_empty_seqqueue(seqqueue *ptmpqueue)
{
return ptmpqueue->head == ptmpqueue->tail;
}
⑤ 判断循环队列是否为满
1）为避免循环队列空与满的条件冲突，牺牲一个存放数据的空间，将tail+1 == head作为判断队满的条件
2）循环队列如果head或者tail下标超过tlen范围，需要对tlen取余，保障head和tail的值在队列下标范围内变化
int is_full_seqqueue(seqqueue *ptmpqueue)
{
return ((ptmpqueue->tail + 1) % ptmpqueue->tlen) ==
ptmpqueue->head;
}
⑥入队
int enter_seqqueue(seqqueue *ptmpqueue, datatype tmpdata)
{
if (is_full_seqqueue(ptmpqueue))
{
return -1;
}
ptmpqueue->pdata[ptmpqueue->tail] = tmpdata;
ptmpqueue->tail = (ptmpqueue->tail + 1) % ptmpqueue->tlen;
return 0;
}
⑦出队
datatype quit_seqqueue(seqqueue *ptmpqueue)
{
datatype retval;
if (is_empty_seqqueue(ptmpqueue))
{
return -1;
}
retval = ptmpqueue->pdata[ptmpqueue->head];
ptmpqueue->head = (ptmpqueue->head + 1) % ptmpqueue->tlen;
return retval;
}
（2）链式队列
使用链表的思想实现链式队列，参考单向链表节点定义，入队使用尾插法，出队返回链表第一个有效节点的值，并删除该节点，在主函数循环出栈队，销毁栈参考单向链表的销毁
#include "linkstack.h"
#include <stdio.h>
#include <stdlib.h>linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}ptmpnode->pnext = NULL;
return ptmpnode;
}int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext;
}int push_linkstack(linknode *phead, datatype tmpdata)
{
linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;return 0;
}datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype tmpdata = 0;ptmpnode = phead->pnext;
tmpdata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
ptmpnode = phead->pnext;return tmpdata;
}int destory_linkstack(linknode **phead)
{
linknode *ptmpnode = NULL;
linknode *pprenode = NULL;ptmpnode = pprenode = *phead;
while(ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pprenode);
pprenode = ptmpnode;
}
*phead = NULL;return 0;
}
)
