栈和队列

概念

链表、栈和队列都是一种线性结构（一对一）

栈和队列是一张特殊的表状结构

栈只允许在栈顶位置入栈和出栈元素

链表可以在任意位置插入和删除元素

栈和队列只允许在指定位置插入和删除元素

栈

概念

先进后出，后进先出

栈顶：允许入栈和出栈的一端称为栈顶

栈底：不允许入栈和出栈的一端称为栈底

入栈（压栈）：将元素放入栈顶位置

出栈（弹栈）：将栈顶元素取出

栈针：记录栈顶位置的标记

分类

顺序栈：空间连续

        增栈：栈的方向自低向高增长

        减栈：栈的方向自高向低增长（高地址向低地址）

        空栈：栈针指向入栈的位置
        满栈：栈针指向栈顶元素的位置

常见的顺序栈：

        空增栈

        空减栈

        满增栈

        满减栈

顺序栈的实现

类型定义

顺序栈的创建

        申请存放标签的空间

        申请存放数据的空间

//创建栈
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 destory_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;
    /*
    *(ptmpstack->pdata + ptmpstack->top) = tmpdata;
    ptmpstack->top++;
    */
   return 0;
}

顺序栈的出栈

栈针位置--

将栈顶元素出栈

//出栈
datatype pop_seqstack(seqstack *ptmpstack)
{
    if(is_empty_seqstack(ptmpstack))
    {
        return -1;
    }
    return ptmpstack->pdata[--ptmpstack->top];
}

链式栈

类型定义

typedef int datatype;

typedef struct node
{
    datatype data;
    struct node *pnext;
}linknode;

链式栈的创建

linknode *create_empty_linkstack(void)
{
    //创建头结点
    linknode *ptmpstack = NULL;
    ptmpstack = malloc(sizeof(linknode));

    if(NULL == ptmpstack)
    {
        perror("fail to malloc");
        return NULL;
    }
    //初始化节点中的值
    ptmpstack->pnext = NULL;
    //返回头结点地址
    return ptmpstack;
}

是否是空栈

int is_empty_linkstack(linknode *phead)
{
    //判断头结点后面有没有节点
    if(NULL == phead->pnext)
    {
        return 1;
    }
    return 0;
    //return NULL == phead->pnext;
}

链式栈的入栈

//入栈
int push_linkstack(linknode *phead, datatype tmpdata)
{
    //头插法
    linknode *ptmpstack = NULL;

    ptmpstack = malloc(sizeof(linknode));
    if(NULL == ptmpstack)
    {
        perror("fail to malloc");
        return -1;
    }
    ptmpstack->data = tmpdata;
    ptmpstack->pnext = phead->pnext;
    phead->pnext = ptmpstack;
    return 0;
}

链式栈的出栈

返回链表第一个有效节点的值，并删除该节点

//出栈
datatype pop_linkstack(linknode *phead)
{
    //判断是否是空栈
    if(is_empty_linkstack(phead))
    {
        return -1;
    }

    //删除第一个有效元素
    linknode *ptmpstack = NULL;
    ptmpstack = phead->pnext;
    //先把数据接出来
    datatype ret;
    ret = ptmpstack->data;
    
    phead->pnext = ptmpstack->pnext;
    free(ptmpstack);
    //返回数据
    return ret;
}

链式栈的销毁

int destroy_linkstack(linknode **pphead)
{
    //销毁链表
    linknode *ptmpstack = NULL;
    linknode *pfreestack = NULL;

    ptmpstack = *pphead;
    pfreestack =  ptmpstack;

    while(ptmpstack != NULL)
    {
        ptmpstack = ptmpstack->pnext;
        free(pfreestack);
        pfreestack = ptmpstack;
    }
    *pphead = NULL;
    return 0;
}

队列

概念

        先进先出，后进后出

        队头：出队的一端

        队尾：入队的一端

        入队：将元素放入队列末尾

        出队：将元素从队头中取出

分类

循环队列

类型定义

//存放数据的类型
typedef int datatype;

//队列类型
typedef struct queue
{
    datatype *pdata;    //存放数据空间的首地址
    int head;           //头下标
    int tail;           //尾下标
    int tlen;           //最多存放元素个数
}seqqueue;

循环队列的创建

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;
}

判断循环队列是否为满

循环队列如果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;//把要存入的数据tmpdata，存入下标为tail的队列中
    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;
}

链式队列

定义

typedef int datatype;

typedef struct node
{
    datatype data;
    struct node *pnext;
}linknode;

链式队列的创建

linknode *create_empty_linkqueue(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_linkqueue(linknode *phead)
{
    //链式栈判断是否为NULL
    if(NULL == phead->pnext)
    {
        return 1;
    }
    return 0;
    //return NULL == phead->pnext;
}

链式队列的入队

int enter_linkqueue(linknode *phead, datatype tmpdata)
{
    //尾插法
    linknode *ptmpnode = NULL;
    linknode *plastnode = NULL;
    ptmpnode = malloc(sizeof(linknode));
    if(NULL == ptmpnode)
    {
        perror("fail to malloc");
        return -1;
    }
    //遍历找到最后一个节点
    plastnode = phead;
    while(plastnode->pnext != NULL)
    {
        plastnode = plastnode->pnext;
    }

    ptmpnode->data = tmpdata;
    ptmpnode->pnext = NULL;
    plastnode->pnext = ptmpnode;

    return 0;
}

链式队列的出队

datatype quit_linkqueue(linknode *phead)
{
    //参考链式栈的出栈
    if(is_empty_linkqueue(phead))
    {
        return -1;
    }
    //删除第一个有效元素
    linknode *ptmpnode = NULL;
    datatype retval;

    ptmpnode = phead->pnext;
    retval = ptmpnode->data;

    phead->pnext = ptmpnode->pnext;
    free(ptmpnode);

    return retval;
}

链式队列的销毁

int destroy_linkqueue(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;
}