day23 栈和队列

1.在现实生活中，我们可能使用的大多时操作受限的线性容器，例如：核酸排队，汽车过隧道、手枪弹夹都属于线性结构，只能在某部分操作

2..只能在指定部位进行操作的线性表

3.分类

栈：其插入和删除操作只允许在同一端进行的线性表称为栈

        特点：先进先出或者后进先出

队列：其插入和删除操作只能在不同端进行的线性表称为队列

        特点：先进先出

总结：上述两个数据结构都是只允许在端点处进行操作的受限线性表

栈

栈:操作受限的线性表，其插入和删除操作只能在同一端进行

栈顶:能够进行插入和删除的一端叫做栈顶

栈底:不能被操作的一端称为栈底

分类：

        顺序栈：顺序存储的栈称为顺序栈

        链式栈：链式存储的栈称为链式栈

顺序栈

typedef int datatype;    //数据元素类型
#define SIZE 8           //栈的初始大小为8

//定义栈的类型
typedef struct
{
    datatype *data;   //存储栈的容器，用于指向堆区空间
    int top;      //记录栈顶元素下标   
    int size;      //记录当前栈的最大容量
}SeqStack, *SeqStackPtr;

创建顺序栈

1.需要在堆区申请一个顺序栈的空间

2.给顺序栈的指针在堆区再申请一个空间

#include"seqstack.h"
#include<myhead.h>


//创建顺序栈
SeqStackPtr stack_create()
{
    //在堆区申请一个顺序栈的空间
    SeqStackPtr S = (SeqStackPtr)malloc(sizeof(SeqStack));
    if(NULL==S)
    {
        printf("创建栈失败\n");
        return NULL;
    }
    //此时，栈的空间就申请好了，但是，没有存储栈的连续内存
    S->data = (datatype*)malloc(sizeof(datatype)*SIZE);
    if(NULL == S->data)
    {
        printf("创建顺序栈失败\n");
        free(S);
        return NULL;
    }

    //此时顺序栈申请成功，并且有了存储顺序栈的容器
    //对顺序栈栈顶进行初始化
    S->top = -1;
    S->size = SIZE;    //当前最大容量

    printf("顺序栈创建成功\n");
    return S;
}

3.判空和判满

1.判空：只需要判断记录栈顶元素下标变量是否为-1

2.判满：只需要判断当前元素的下标是否为当前容器最大容量-1

//判空 1表示空  0表示非空
int stack_empty(SeqStackPtr S)
{
    if(NULL==S || S->data==NULL)
    {
        printf("所给栈不合法\n");
        return -1;
    }

    //判断是否为空
    return S->top==-1;
}

//判满  1表示满，0表示非满
int stack_full(SeqStackPtr S)
{
    if(NULL==S || S->data==NULL)
    {
        printf("所给栈不合法\n");
        return -1;
    }

    return S->top == S->size-1;
}

入栈

注意：如果栈已经满了，需要进行二倍扩容

//定义二倍扩容函数
static int stack_expend(SeqStackPtr S)
{
    //判断逻辑
    if(NULL == S)
    {
        printf("所给栈不合法\n");
        return -1;
    }

    //扩容逻辑
    datatype *temp = malloc(sizeof(datatype)*S->size*2);
    if(NULL==temp)
    {
        printf("扩容失败\n");
        return -1;
    }

    //内存拷贝
    memcpy(temp, S->data, sizeof(datatype)*S->size);
    
    //释放原内存
    free(S->data);
    //将指针指向新内存
    S->data = temp;

    S->size *= 2;     //最大容量乘以2
    
    printf("扩容成功\n");
    return 0;

}




//入栈：压栈   先加后压
int stack_push(SeqStackPtr S, datatype e)
{
    //判断逻辑
    if(NULL==S)
    {
        printf("所给栈不合法\n");
        return -1;
    }

    if(stack_full(S))
    {
        //printf("栈满，入栈失败\n");
        //return -1;

        //开始二倍扩容
        stack_expend(S);
    }

    //入栈逻辑
    S->top ++;
    S->data[S->top] = e;

    printf("入栈成功\n");
    return 0;

}

出栈

//出栈
int stack_pop(SeqStackPtr S)
{
    //判断逻辑
    if(NULL==S || stack_empty(S))
    {
        printf("出栈失败\n");
        return -1;
    }

    //出栈：弹栈    先弹后减
    datatype e = S->data[S->top];   //记录栈顶元素下标
    S->top--;

    printf("%d出栈成功\n", e);
    return 0;

}

遍历

//遍历
int stack_show(SeqStackPtr S)
{
    //判断逻辑
    if(NULL==S || stack_empty(S))
    {
        printf("遍历失败\n");
        return -1;
    }

    //遍历逻辑
    printf("当前栈从栈顶到栈底元素分别是：");
    for(int i=S->top; i>=0; i--)
    {
        printf("%d\t", S->data[i]);
    }
    printf("\n");
}

销毁栈

先将容器空间销毁,然后销毁栈的空间

//销毁栈
void stack_destroy(SeqStackPtr S)
{
    //判断逻辑
    if(NULL==S)
    {
        return ;
    }

    //如果容器空间为空
    if(NULL==S->data)
    {
        //将顺序栈空间释放即可
        free(S);
        S =NULL;
        return ;
    }

    //先释放容器空间
    free(S->data);
    //释放顺序栈的空间
    free(S);
    S = NULL;

    printf("释放成功\n");
    
}

链式栈

实现方式：

        1.只进行头插和头删操作的单向链表就是一个链式栈1

        单向链表的头部，就是栈顶，单向链表的尾部就是栈底

        2.只进行尾插和尾删操作的单向链表就是一个链式栈

        单向链表的尾部就是栈顶，单向链表的头部就是栈底

队列

1.操作受限的线性表：其插入和删除也只能在端点处进行，但是要求在不同端进行

2.队头：允许删除操作的一端称为队头

3.队尾：允许插入操作的一端称为队尾

4.分类：

顺序队列：顺序存储的队列称为顺序队列（连续存储空间）

链式队列：链式存储的队列称为链式队列（基于节点进行操作）

顺序队列

1.普通顺序队列：

        由一个连续的存储空间存储队列

        有一个变量记录队头元素的下标

        有一个变量记录队尾元素的下标

2.普通顺序队列的弊端：

假溢满：命名队列容器中还有空间可以存储数据，但是，队尾已经达到了上限，不能再入队了

3.为了解决普通顺序队列的假溢满现象，我们引入的循环顺序队列

顺序队列全部代码

seqqueue.h

#ifndef SEQQUEUE_H
#define SEQQUEUE_H

typedef int datatype;    //数据元素类型
#define MAX 8           //循环顺序队列最大容量

//定义循环顺序队列类型
typedef struct
{
    datatype data[MAX];  //存储队列的容器
    int head;        //记录队头的下标变量
    int tail;        //记录队尾的下标变量

}SeqQueue, *SeqQueuePtr;

//创建循环队列
SeqQueuePtr queue_create();

//判空
int quque_empty(SeqQueuePtr Q);

//判满
int queue_full(SeqQueuePtr Q);

//入队
int queue_push(SeqQueuePtr Q, datatype e);
//遍历
void queue_show(SeqQueuePtr Q);

//出队
int queue_pop(SeqQueuePtr Q);

//销毁队列
void queue_destroy(SeqQueuePtr Q);


#endif

seqqueue.c

#include"seqqueue.h"
#include<myhead.h>

//创建循环队列
SeqQueuePtr queue_create()
{
    //在堆区申请一个循环顺序队列的空间
    SeqQueuePtr Q = (SeqQueuePtr)malloc(sizeof(SeqQueue));
    if(NULL==Q)
    {
        printf("顺序队列创建失败\n");
        return NULL;
    }

    //进行初始化
    Q->head = 0;
    Q->tail = 0;

    printf("队列创建成功\n");
    return Q;
}

//判空   1表示空  0表示非空
int quque_empty(SeqQueuePtr Q)
{
    if(NULL==Q)
    {
        printf("所给队列不合法\n");
        return -1;
    }
    return Q->head==Q->tail;
}

//判满
int queue_full(SeqQueuePtr Q)
{
    if(NULL==Q)
    {
        printf("所给队列不合法\n");
        return -1;
    }
    //判满很重要
    return (Q->tail+1)%MAX == Q->head;
}

//入队
int queue_push(SeqQueuePtr Q, datatype e)
{
    //判断逻辑
    if(NULL==Q || queue_full(Q))
    {
        printf("入队失败\n");
        return -1;
    }

    //入队逻辑
    Q->data[Q->tail] = e;    //将数据放入队尾所在位置
    //Q->tail ++;            //?队尾后移

    Q->tail = (Q->tail+1)%MAX;   //队尾后移  重要
    printf("入队成功\n");
}

//遍历
void queue_show(SeqQueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || quque_empty(Q))
    {
        printf("遍历失败\n");
        return;
    }

    //遍历逻辑
    printf("从队头到队尾元素分别是：");
    for(int i=Q->head; i!=Q->tail; i=(i+1)%MAX)
    {
        printf("%d\t", Q->data[i]);
    }
    printf("\n");

}

//出队
int queue_pop(SeqQueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || quque_empty(Q))
    {
        printf("出队失败\n");
        return -1;
    }

    //出队逻辑
    datatype e = Q->data[Q->head];
    //队头后移
    //Q->head ++;        //?  不可以
    Q->head = (Q->head+1)%MAX;
    printf("%d出队成功\n", e);

    return 0;
}

//销毁队列
void queue_destroy(SeqQueuePtr Q)
{
    //判断逻辑
    if(NULL==Q)
    {
        return;
    }
    //释放顺序队列
    free(Q);
    Q = NULL;

    printf("销毁成功\n");
}

main.c

#include"seqqueue.h"
#include<myhead.h>

int main(int argc, const char *argv[])
{
    SeqQueuePtr Q = queue_create();
    if(NULL==Q)
    {
        return -1;
    }

    //调用入队函数
    queue_push(Q, 3);
    queue_push(Q, 7);
    queue_push(Q, 2);
    queue_push(Q, 4);
    queue_push(Q, 6);
    queue_push(Q, 9);

    //调用遍历函数
    queue_show(Q);

    //调用出队函数
    queue_pop(Q);
    queue_pop(Q);
    queue_pop(Q);

    queue_show(Q);

    //调用销毁函数
    queue_destroy(Q);
    Q=NULL;
    queue_show(Q);
    
    return 0;
}

链式队列

1.实现方式：

        使用单向链表进行头删尾插实现：此时链表的头部称为队尾，链表的尾部称为队头

        使用单向链表进行头删尾插实现：此时链表的头部称为队头，链表的尾部称为队尾

2.此时我们可以设置两个指针，分别指向单向链表的头部和尾部，删除时，通过头指针进行头删，插入时使用尾指针进行尾插

链式队列的操作

、1.链式队列类型结构体

typedef char datatype;   //数据元素类型

//定义结点类型
typedef struct Node
{
    union
    {
        int len;   //头结点数据域
        datatype data;  //普通结点数据域
    };

    struct Node *next;   //指针域
}Node, *NodePtr; 

//定义链式队列类型
typedef struct
{
    NodePtr head;    //指向头结点的指针
    NodePtr tail;    //指向最后一个结点的指针
}LinkQueue, *LinkQueuePtr;

创建链式队列

//创建链式队列
LinkQueuePtr queue_create()
{
    //在堆区申请一个队列的空间
    LinkQueuePtr L = (LinkQueuePtr)malloc(sizeof(LinkQueue));
    if(NULL==L)
    {
        printf("链式队列创建失败\n");
        return NULL;
    }
    //此时，L指向的空间中只有16字节（两个结点类型的指针变量）
    // L->head      L->tail
    // 上面的指针变量都是野指针
    
    //在堆区申请一个头结点的空间（就是一条链表）
    NodePtr N = (NodePtr)malloc(sizeof(Node));
    if(NULL==N)
    {
        printf("队列创建失败\n");
        free(L);
        return NULL;
    }

    //初始化头结点
    N->len = 0;      //链表长度为0
    N->next = NULL;

    //将队列的两个指针都指向链表的头结点
    L->head = L->tail = N;
    printf("链式队列创建成功\n");
    return L;
}

全部代码

linkqueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H

typedef char datatype;   //数据元素类型

//定义结点类型
typedef struct Node
{
    union
    {
        int len;   //头结点数据域
        datatype data;  //普通结点数据域
    };

    struct Node *next;   //指针域
}Node, *NodePtr; 

//定义链式队列类型
typedef struct
{
    NodePtr head;    //指向头结点的指针
    NodePtr tail;    //指向最后一个结点的指针
}LinkQueue, *LinkQueuePtr;

//创建链式队列
LinkQueuePtr queue_create();

//判空
int queue_empty(LinkQueuePtr L);

//入队
int queue_push(LinkQueuePtr L, datatype e);

//遍历
void queue_show(LinkQueuePtr L);

//出队
int queue_pop(LinkQueuePtr L);

//销毁队列
void queue_destroy(LinkQueuePtr L);




#endif

linkqueue.c

#include"linkqueue.h"
#include<myhead.h>


//创建链式队列
LinkQueuePtr queue_create()
{
    //在堆区申请一个队列的空间
    LinkQueuePtr L = (LinkQueuePtr)malloc(sizeof(LinkQueue));
    if(NULL==L)
    {
        printf("链式队列创建失败\n");
        return NULL;
    }
    //此时，L指向的空间中只有16字节（两个结点类型的指针变量）
    // L->head      L->tail
    // 上面的指针变量都是野指针
    
    //在堆区申请一个头结点的空间（就是一条链表）
    NodePtr N = (NodePtr)malloc(sizeof(Node));
    if(NULL==N)
    {
        printf("队列创建失败\n");
        free(L);
        return NULL;
    }

    //初始化头结点
    N->len = 0;      //链表长度为0
    N->next = NULL;

    //将队列的两个指针都指向链表的头结点
    L->head = L->tail = N;
    printf("链式队列创建成功\n");
    return L;
}

//判空
int queue_empty(LinkQueuePtr L)
{
    //判断逻辑
    if(NULL==L || L->head==NULL)
    {
        printf("所给队列不合法\n");
        return -1;
    }

    return L->head == L->tail;
}

//入队
int queue_push(LinkQueuePtr L, datatype e)
{
    //判断逻辑
    if(NULL==L || NULL==L->head)
    {
        printf("所给队列不合法\n");
        return -1;
    }

    //申请结点封装数据
    NodePtr p = (NodePtr)malloc(sizeof(Node));
    if(NULL==p)
    {
        printf("结点申请失败\n");
        return -1;
    }
    p->data = e;    //将数据封装进结点
    p->next = NULL;

    //进行尾插
    L->tail->next = p;   //将新结点连接到链表最后一个结点后面
    L->tail = p;     //更新尾指针指向最新结点

    //表长变化
    L->head->len++;
    printf("入队成功\n");
    return 0;
}

//遍历
void queue_show(LinkQueuePtr L)
{
    //判断逻辑
    if(NULL==L || L->head==NULL||queue_empty(L))
    {
        printf("遍历失败\n");
        return;
    }

    //定义遍历指针从第一个结点出发
    printf("从队头到队尾元素分别是：");
    NodePtr q = L->head->next;   //从第一个结点出发
    while(q!=NULL)
    {
        printf("%c\t", q->data);
        q = q->next;
    }
    printf("\n");
}

//出队
int queue_pop(LinkQueuePtr L)
{
    //判断逻辑
    if(NULL==L || L->head==NULL||queue_empty(L))
    {
        printf("出队失败\n");
        return -1;
    }

    //出队逻辑  链表头删
    NodePtr p = L->head->next;   //标记第一个结点
    L->head->next = p->next;    //孤立要删除的结点
    printf("%c出队成功\n", p->data);
    free(p);                 //释放要删除的结点
    p = NULL;

    //链表长度变化
    L->head->len--;

    //判断出队后，链表是否为空
    if(L->head->next == NULL)
    {
        L->tail = L->head;  //将尾指针归位
    }

    return 0;
}

//销毁队列
void queue_destroy(LinkQueuePtr L)
{
    //判断逻辑
    if(NULL==L)
    {
        return;
    }

    if(NULL == L->head)   //有队列没有链表
    {
        free(L);
        L = NULL;
        return;
    }

    //既有队列也有链表
    while(!queue_empty(L))
    {
        queue_pop(L);      //将所有结点释放
    }

    //释放头结点
    free(L->head);
    //释放队列
    free(L);
    L = NULL;
    printf("销毁成功\n");

}

main.c

#include"linkqueue.h"
#include<myhead.h>

int main(int argc, const char *argv[])
{
    //调用创建顺序队列函数
    LinkQueuePtr L = queue_create();
    if(NULL==L)
    {
        return -1;
    }

    //调用入队函数
    queue_push(L, 'Q');
    queue_push(L, 'W');
    queue_push(L, 'E');
    queue_push(L, 'R');

    //调用遍历函数
    queue_show(L);

    //调用出队函数
    queue_pop(L);
    queue_pop(L);

    queue_show(L);

    //调用销毁队列函数
    queue_destroy(L);
    L = NULL;

    queue_show(L);

    
    return 0;
}