当前位置:首页 » 《资源分享》 » 正文

手撕数据结构---栈和队列的概念以及实现

20 人参与  2024年09月23日 15:21  分类 : 《资源分享》  评论

点击全文阅读


栈的概念:

栈:⼀种特殊的线性表,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插⼊操作叫做进栈/压栈/⼊栈,⼊数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

 栈的基本框架

struct Stack{    int* arr;    int capacity;    int top;//栈顶};

栈的实现

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"void STTest(){    ST st;//创建一个栈变量    //初始化    STInit(&st);    //入栈    SrackPush(&st, 1);    SrackPush(&st, 2);    SrackPush(&st, 3);    SrackPush(&st, 4);    SrackPush(&st, 5);    //打印栈内的有效数据    printf("%d\n", STSize(&st));    //栈的出数据    /*SrackPop(&st);*/    //循环出栈,直到栈为空    //     while (!StackEmpty(&st))//如果栈不为空的话,我们一直进行循环打印栈顶数据    {        //取出当前栈顶的数据        STDataType data = StackTop(&st);        printf("%d ", data);//打印返回的栈顶数据        //数据出栈        SrackPop(&st);        //入栈的顺序是1 2 3 4 5        //出栈的顺序是5 4 3 2 1        //栈是不能被遍历的,也不能被随机访问    }    //打印栈内的有效数据    printf("%d\n", STSize(&st));    //销毁    STDestory(&st);}int main(){    STTest();    return 0;}//栈这样的结构只能在一端入栈,一端出栈

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"//初始化void STInit(ST* ps){    assert(ps);//判断传的ps是不是空的    ps->arr = NULL;    ps->capacity = ps->top = 0;    //一开始的栈顶等于我们的栈底(栈为空的话)}//销毁void STDestory(ST* ps){    assert(ps);//参数不能传空    if (ps->arr)//arr不为空的话我们直接将数组释放掉    {        free(ps->arr);    }    ps->arr = NULL;    ps->capacity = ps->top = 0;}//栈的入数据操作void SrackPush(ST* ps, STDataType x){    assert(ps);//ps不能传空    //如果空间足够的话我们直接进行插入    //判断空间是否足够,如果top等于capacity的话,那么就说明我们这个栈就是满的    if (ps->capacity == ps->top)//,满了,我们需要进行增容操作    {        //二倍的增加        //初始情况下我们的capacity是定义为0的,所以我们不能直接进行乘二的操作        //我们需要创建一个变量        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;        //如果容量为0的话,我们给newCapacity一个初始值4,如果不为0我们就进行乘二的操作        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));        if (tmp == NULL)        {            perror("realloc fail!");            exit(1);        }        //申请成功,我们将tmp申请的空间给pa->arr        ps->arr = tmp;        //申请空间成功了,那么我们就要将capacity进行改变了        ps->capacity = newCapacity;    }    //到这里空间一定是够的    ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据    //添加完数据之后,top要加加    ps->top++;}//判断栈是否为空bool StackEmpty(ST* ps){    assert(ps);    return ps->top == 0;//为空就返回true}//栈的出数据操作void SrackPop(ST* ps){    assert(ps);    //如果栈为空的话,我们是不能出数据的(top==0)    assert(!StackEmpty(ps));//如果栈为空就会报错了    //走到这里就说明栈不为空    --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了}//取栈顶元素---循环打印栈顶的数据STDataType StackTop(ST* ps)//返回值是栈顶的元素{    assert(ps);    assert(!StackEmpty(ps));//判断当前栈是不是空的,如果是空的话,我们没有什么能取的    return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标}//获取栈中有效个数int STSize(ST* ps){    assert(ps);    return ps->top;}

Stack.h

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//定义栈的结构typedef int STDataType;typedef struct Stack{    STDataType* arr;    int capacity;//栈的空间大小    int top;//栈顶(插入数据和删除数据的位置)}ST;//初始化void STInit(ST* ps);//传的是地址//销毁void STDestory(ST* ps);//栈顶-=--如数据、出数据//栈的入数据操作void SrackPush(ST* ps, STDataType x);//第二个参数是要插入的数据//栈的出数据操作void SrackPop(ST* ps);//取栈顶元素---循环打印栈顶的数据STDataType StackTop(ST* ps);//返回值是栈顶的元素//判断栈是否为空bool StackEmpty(ST* ps);//获取栈中有效个数int STSize(ST* ps);

队列的概念

概念:只允许在⼀端进⾏插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)

⼊队列:进⾏插⼊操作的⼀端称为队尾

出队列:进⾏删除操作的⼀端称为队头

队头:用来删除数据

对头:用来插入数据

队列的底层是链表,链表是由一个一个的节点组成

//定义队列节点的结构struct QueueNode{    int data;    struct QueueNode* next;//指向下个节点的指针};struct Queue{    struct QueueNode* phead;//指向的是队头--删除数据    struct QueueNode* ptail;//指向的是队尾--插入数据};

为什么是定义的是两个结构体类型呢?

队列中的每一个数据是通过一个节点保存的,节点和节点之间是通过指针链接的,

其实就是维护了一个链表,给这个链表加上先进先出的限制,其实就是队列了

Queue.h

#pragma once#include <stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//定义队列结构typedef int QDataType;typedef struct QueueNode{    QDataType data;    struct QueueNode* next;}QueueNode;typedef struct Queue{    QueueNode*phead;//指向头节点的指针---队头--删除数据    QueueNode*ptail;//指向尾节点的指针---队尾--插入数据    int size;//保存队列有效个数}Queue ;//初始化void QueueInit(Queue* pq);//入队列,队尾   插入数据void QueuePush(Queue* pq, QDataType x);//出队列,队头    删除数据void QueuePop(Queue* pq);//判断队列是否为空bool Queuempty(Queue* pq);//取队头数据QDataType QueueFront(Queue* pq);//取队尾数据QDataType QueueBack(Queue* pq);//队列有效元素个数int QueueSize(Queue* pq);//队列的销毁void QueueDestroy(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"//初始化void QueueInit(Queue* pq){    assert(pq);//传过来的不能是空指针     pq->phead = pq->ptail = NULL;//空的队列    pq->size = 0;}//判断队列是否为空bool Queuempty(Queue* pq){    assert(pq);    return pq->phead == NULL && pq->ptail == NULL;    //如果后面的表达式成立,那么就是真,返回的是true    //就是说如果这里的是空队列的话,那么就返回的是true}//入队列,队尾   插入数据void QueuePush(Queue* pq, QDataType x){    assert(pq);    //申请新节点    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间    if (newnode == NULL)    {        perror("malloc dail!");        exit(1);    }    //对newnode进行初始化操作    newnode->data = x;    newnode->next = NULL;    if (pq->phead == NULL)//说明队列为空    {        pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点    }    else//队列不为空    {        pq->ptail->next = newnode;        //那么此时的newnode 就是新的ptail        pq->ptail = newnode;    }    pq->size++;}//出队列,队头    删除数据    从头结点开始删除数据void QueuePop(Queue* pq){    assert(pq);    //队列为空(不可删除数据,因为没有数据)    //队列不为空(可删除数据)    assert(!Queuempty(pq));//队列为空白的话就报错    //处理只有一个节点的情况,避免ptail变成野指针    //判断只有一个节点的情况    if (pq->ptail == pq->phead)//头尾指针相同,说明只有一个节点    {        free(pq->phead);//随便释放        pq->phead = pq->ptail = NULL;    }    else//处理多个节点的情况    {        //删除队头元素    //那么我们现将下个节点的位置进行保存        QueueNode* next = pq->phead->next;        //存储好之后我们直接将头结点进行释放        free(pq->phead);        pq->phead = next;//那么之前存的next就是新的头结点了    }    pq->size--;}//取队头数据QDataType QueueFront(Queue* pq)//返回队头数据{    assert(pq);    assert(!Queuempty(pq));//队列不为空    return pq->phead->data;//将队头里面的数据直接返回就行了}//取队尾数据QDataType QueueBack(Queue* pq){    assert(pq);    assert(!Queuempty(pq));//队列不为空    return pq->ptail->data;}//队列有效元素个数int QueueSize(Queue* pq){    assert(pq);    //下面这种遍历的话效率太低了    //int size = 0;    定义一个指针进行遍历    //QueueNode* pcur = pq->phead;//指向队列的头结点    //while (pcur)//pcur不为空就往后走    //{    //  size++;    //  pcur = pcur->next;    //}    //return size;    return pq->size;}//队列的销毁void QueueDestroy(Queue* pq){    assert(pq);    assert(!Queuempty(pq));//队列不为空    //遍历    QueueNode* pcur = pq->phead;    while (pcur)    {        //销毁之前先把下个节点进行保存        QueueNode* next = pcur -> next;        free(pcur);        //将Pcur销毁之后,那么之前保存的next就是新的头结点        pcur = next;    }    pq->phead = pq->ptail = NULL;    pq->size = 0;}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void QueueTest01(){    Queue q;//创建一个队列变量    //初始化    QueueInit(&q);    //插入数据    QueuePush(&q, 1);    QueuePush(&q, 2);    QueuePush(&q, 3);    QueuePush(&q, 4);    //取队头数据    printf("head:%d\n", QueueFront(&q));    //取队尾数据    printf("tail:%d\n", QueueBack(&q));    //删除    QueuePop(&q);    //队列有效个数    printf("size:%d\n", QueueSize(&q));    //队列的销毁    QueueDestroy(&q);}int main()  {    QueueTest01();}

栈和队列相关的OJ题

题目一:有效的括号

 

//借助数据结构---栈来解决这道题/*思路:我们先创建一个字符串指针ps我们再创建一个栈空间我们通过ps进行字符串的遍历如果是做左括号的话,那么我们就进行入栈操作如果我们遇到了右括号的话,那么我们就与栈顶的元素进行匹配 如果是一对括号的话,那么我们就进行出栈操作,然后ps++,top-- 进行下一对括号的匹配 如果ps++指向的是大括号,但是栈顶的是小括号,那么现在就是不匹配的 那么我们就直接返回false*/typedef char STDataType;typedef struct Stack{    STDataType* arr;    int capacity;    int top;//栈顶}ST;//初始化void STInit(ST* ps){    assert(ps);//判断传的ps是不是空的    ps->arr = NULL;    ps->capacity = ps->top = 0;    //一开始的栈顶等于我们的栈底(栈为空的话)}//销毁void STDestory(ST* ps){    assert(ps);//参数不能传空    if (ps->arr)//arr不为空的话我们直接将数组释放掉    {        free(ps->arr);    }    ps->arr = NULL;    ps->capacity = ps->top = 0;}//栈的入数据操作void SrackPush(ST* ps, STDataType x){    assert(ps);//ps不能传空    //如果空间足够的话我们直接进行插入    //判断空间是否足够,如果top等于capacity的话,那么就说明我们这个栈就是满的    if (ps->capacity == ps->top)//,满了,我们需要进行增容操作    {        //二倍的增加        //初始情况下我们的capacity是定义为0的,所以我们不能直接进行乘二的操作        //我们需要创建一个变量        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;        //如果容量为0的话,我们给newCapacity一个初始值4,如果不为0我们就进行乘二的操作        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));        if (tmp == NULL)        {            perror("realloc fail!");            exit(1);        }        //申请成功,我们将tmp申请的空间给pa->arr        ps->arr = tmp;        //申请空间成功了,那么我们就要将capacity进行改变了        ps->capacity = newCapacity;    }    //到这里空间一定是够的    ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据    //添加完数据之后,top要加加    ps->top++;}//判断栈是否为空bool StackEmpty(ST* ps){    assert(ps);    return ps->top == 0;//为空就返回true}//栈的出数据操作void SrackPop(ST* ps){    assert(ps);    //如果栈为空的话,我们是不能出数据的(top==0)    assert(!StackEmpty(ps));//如果栈为空就会报错了    //走到这里就说明栈不为空    --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了}//取栈顶元素---循环打印栈顶的数据STDataType StackTop(ST* ps)//返回值是栈顶的元素{    assert(ps);    assert(!StackEmpty(ps));//判断当前栈是不是空的,如果是空的话,我们没有什么能取的    return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标}//获取栈中有效个数int STSize(ST* ps){    assert(ps);    return ps->top;}bool isValid(char* s){    ST st;//创建一个栈变量    //初始化    STInit(&st);    //遍历字符串s    char *ps=s;//指向字符串s    while(*ps!='\0')//我们需要遍历字符串'\0'之前的数据    {        //左括号入栈        if(*ps=='('|| *ps=='[' || *ps=='{')        {            SrackPush(&st,*ps);        }        else//右括号,和栈顶元素进行匹配        {            //栈不为空才能取元素            //判断栈是否为空,空的话直接返回false            if(StackEmpty(&st))//栈为空的话,这个函数返回的就是true            {                return false;            }            //取栈顶元素,与top进行比较            char ch=StackTop(&st);//栈顶的元素,我们取出            if((*ps==')' &&ch=='(')            ||(*ps==']' &&ch=='[')            ||(*ps=='}' &&ch=='{'))            {                //匹配上了我们就进行出栈操作                SrackPop(&st);            }            else            {                //不匹配的话,我们在返回之前我们同样需要进行销毁操作                STDestory(&st);                //那么就是括号不匹配了                return false;            }        }        //入栈之后我们进行ps++        ps++;    }    bool ret=StackEmpty(&st)==true;//为空的话那么我们就返回truew    //销毁    STDestory(&st);    return ret;}/*假如我们的字符串里面只有一个左括号的话,那么这个代码就会直接入栈然后跳出循环,并没有对栈内的空间进行检查 并没有进行出栈的操作,所以栈内是有元素的我们要判断栈内是否为空如果是空的话,那么就说括号都配对完成了,左括号都出栈了,那么就返回true*//*我们在取栈顶元素之前我们还要对栈的空间进行判断,看看栈是否为空,栈不为空才能去栈顶元素栈为空的话,之间返回false*/

题目二:用队列实现栈

 

/*队列是先进先出栈是先进后出*//*因为我们是要进行栈的实现那么假如我们存进去1 2 3那么拿出来的就是3 2 1我们用两个队列实现Q1和Q2两个队列假设现在Q1里面的是1 2 3,1在对头,3在队尾我们Q1每次出size-1个数据入到Q2里面,那么此时的Q1就剩下一个3,那么我们直接将3出栈,那么得到的第一个数就是3以此类推我们就能得到3 2 1*//*两个队列,那个队列不为空,我们就将这个队列里面的size-1个数据导入到另一个队列里面去,然后将剩下的元素导出了如果最后队列里面只有一个数据,那么我们就直接将这个数据导出*//*思路:出栈:找到不为空的队列,将size-1个数据导入到另一个队列中入栈:往空队列中插入数据取栈顶元素*///定义队列结构typedef int QDataType;typedef struct QueueNode{    QDataType data;    struct QueueNode* next;}QueueNode;typedef struct Queue{    QueueNode*phead;//指向头节点的指针---队头--删除数据    QueueNode*ptail;//指向尾节点的指针---队尾--插入数据    int size;//保存队列有效个数}Queue ;//初始化void QueueInit(Queue* pq){    assert(pq);//传过来的不能是空指针     pq->phead = pq->ptail = NULL;//空的队列    pq->size = 0;}//判断队列是否为空bool Queuempty(Queue* pq){    assert(pq);    return pq->phead == NULL && pq->ptail == NULL;    //如果后面的表达式成立,那么就是真,返回的是true    //就是说如果这里的是空队列的话,那么就返回的是true}//入队列,队尾   插入数据void QueuePush(Queue* pq, QDataType x){    assert(pq);    //申请新节点    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间    if (newnode == NULL)    {        perror("malloc dail!");        exit(1);    }    //对newnode进行初始化操作    newnode->data = x;    newnode->next = NULL;    if (pq->phead == NULL)//说明队列为空    {        pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点    }    else//队列不为空    {        pq->ptail->next = newnode;        //那么此时的newnode 就是新的ptail        pq->ptail = newnode;    }    pq->size++;}//出队列,队头    删除数据    从头结点开始删除数据void QueuePop(Queue* pq){    assert(pq);    //队列为空(不可删除数据,因为没有数据)    //队列不为空(可删除数据)    assert(!Queuempty(pq));//队列为空白的话就报错    //处理只有一个节点的情况,避免ptail变成野指针    //判断只有一个节点的情况    if (pq->ptail == pq->phead)//头尾指针相同,说明只有一个节点    {        free(pq->phead);//随便释放        pq->phead = pq->ptail = NULL;    }    else//处理多个节点的情况    {        //删除队头元素    //那么我们现将下个节点的位置进行保存        QueueNode* next = pq->phead->next;        //存储好之后我们直接将头结点进行释放        free(pq->phead);        pq->phead = next;//那么之前存的next就是新的头结点了    }    pq->size--;}//取队头数据QDataType QueueFront(Queue* pq)//返回队头数据{    assert(pq);    assert(!Queuempty(pq));//队列不为空    return pq->phead->data;//将队头里面的数据直接返回就行了}//取队尾数据QDataType QueueBack(Queue* pq){    assert(pq);    assert(!Queuempty(pq));//队列不为空    return pq->ptail->data;}//队列有效元素个数int QueueSize(Queue* pq){    assert(pq);    //下面这种遍历的话效率太低了    //int size = 0;    定义一个指针进行遍历    //QueueNode* pcur = pq->phead;//指向队列的头结点    //while (pcur)//pcur不为空就往后走    //{    //  size++;    //  pcur = pcur->next;    //}    //return size;    return pq->size;}//队列的销毁void QueueDestroy(Queue* pq){    assert(pq);    //assert(!Queuempty(pq));//队列不为空    //遍历    QueueNode* pcur = pq->phead;    while (pcur)    {        //销毁之前先把下个节点进行保存        QueueNode* next = pcur -> next;        free(pcur);        //将Pcur销毁之后,那么之前保存的next就是新的头结点        pcur = next;    }    pq->phead = pq->ptail = NULL;    pq->size = 0;}//两个队列来实现栈typedef struct {    Queue q1;//队列1    Queue q2;//队列2} MyStack;//STInit  栈的初始化MyStack* myStackCreate(){    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));//创建一个栈大小的空间    QueueInit(&pst->q1);//调用初始化函数对q1进行初始化    QueueInit(&pst->q2);    return pst;}//那么到这里我们有一个空栈,栈里面有两个队列//入数据void myStackPush(MyStack* obj, int x){    //往不为空的队列插入数据    //第一步判断那个队列是非空队列    if(!Queuempty(&obj->q1))//如果这个队列不是空的话,我们就我那个这个队列里面入数据    {        //往队列内插入数据        QueuePush(&obj->q1,x);    }    else    {        QueuePush(&obj->q2,x);    }}//出数据int myStackPop(MyStack* obj){    //找到不为空的队列    Queue*empQ=&obj->q1;//假设q1是空的,创建指针指向q1    Queue*noneQ=&obj->q2;//q2不为空,指针指向q2    if(!Queuempty(&obj->q1))//如果q1不为空    {        //创建两个指针,noneQ指向的是非空队列,empQ指向的是空队列        noneQ=&obj->q1;//那么这个非空指针就指向了q1        empQ=&obj->q2;//那么空指针就指向q2了    }    //将不为空内的size-1个数据导入到另一个队列里面    while(QueueSize(noneQ)>1)//循环条件是非空队列里面只剩下一个有效的数据了    {        int front=QueueFront(noneQ);//获取这个非空队列里面的队头数据        QueuePush(empQ,front);//往空队列里面循环插入队头数据        QueuePop(noneQ);//因为我们这个非空队列的队头数据已经拿出去了 ,那么我们就将非空队列进行删除数据操作    }    //非空队列中只剩下一个数据----那么这个数据就是要出栈的数据    int pop=QueueFront(noneQ);//获取剩下的这个元素    QueuePop(noneQ);//进行出数据操作    return pop;//返回我们要的值}//取栈顶元素  假设插入1 2 3,那么栈顶就是3   这里是2两个队列int myStackTop(MyStack* obj)   {    //找到不为空的队列,取队尾元素    if(!Queuempty(&obj->q1))//如果第一个队列不为空的话    {        return QueueBack(&obj->q1);//直接将取到的队尾元素进行返回就行了    }    else    {        return QueueBack(&obj->q2);    }}//判读栈是否为空bool myStackEmpty(MyStack* obj){    //两个队列如果都为空的话,那么这个栈就是空的    return Queuempty(&obj->q1)  &&  Queuempty(&obj->q2);}//销毁void myStackFree(MyStack* obj){    //就是栈内的连个队列的销毁    QueueDestroy(&obj->q1);    QueueDestroy(&obj->q2);    free(obj);//将我们之前申请的栈空间进行释放掉    obj=NULL;}/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj);*/

题目三:用栈实现队列

 

//定义栈的结构typedef int STDataType;typedef struct Stack{    STDataType* arr;    int capacity;//栈的空间大小    int top;//栈顶(插入数据和删除数据的位置)}ST;//初始化void STInit(ST* ps){    assert(ps);//判断传的ps是不是空的    ps->arr = NULL;    ps->capacity = ps->top = 0;    //一开始的栈顶等于我们的栈底(栈为空的话)}//销毁void STDestory(ST* ps){    assert(ps);//参数不能传空    if (ps->arr)//arr不为空的话我们直接将数组释放掉    {        free(ps->arr);    }    ps->arr = NULL;    ps->capacity = ps->top = 0;}//栈的入数据操作void SrackPush(ST* ps, STDataType x){    assert(ps);//ps不能传空    //如果空间足够的话我们直接进行插入    //判断空间是否足够,如果top等于capacity的话,那么就说明我们这个栈就是满的    if (ps->capacity == ps->top)//,满了,我们需要进行增容操作    {        //二倍的增加        //初始情况下我们的capacity是定义为0的,所以我们不能直接进行乘二的操作        //我们需要创建一个变量        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;        //如果容量为0的话,我们给newCapacity一个初始值4,如果不为0我们就进行乘二的操作        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));        if (tmp == NULL)        {            perror("realloc fail!");            exit(1);        }        //申请成功,我们将tmp申请的空间给pa->arr        ps->arr = tmp;        //申请空间成功了,那么我们就要将capacity进行改变了        ps->capacity = newCapacity;    }    //到这里空间一定是够的    ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据    //添加完数据之后,top要加加    ps->top++;}//判断栈是否为空bool StackEmpty(ST* ps){    assert(ps);    return ps->top == 0;//为空就返回true}//栈的出数据操作void SrackPop(ST* ps){    assert(ps);    //如果栈为空的话,我们是不能出数据的(top==0)    assert(!StackEmpty(ps));//如果栈为空就会报错了    //走到这里就说明栈不为空    --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了}//取栈顶元素---循环打印栈顶的数据STDataType StackTop(ST* ps)//返回值是栈顶的元素{    assert(ps);    assert(!StackEmpty(ps));//判断当前栈是不是空的,如果是空的话,我们没有什么能取的    return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标}//获取栈中有效个数int STSize(ST* ps){    assert(ps);    return ps->top;}////*因为我们是用两个栈来实现队列那么假如我们插入1 2 3 那么导出的也是1 2 3 我们创建两个栈,分别用来入数据和出数据 第一个栈接入我们放的是1 2 3  1在栈底,3在栈顶 那么我们将这三个数据依次放到另一个栈内 那么另一个栈就是3 2 1  3在栈第,1在栈顶,那么我们依次将这个栈的数据依次导出 就能达到队列的效果了*//*逻辑:pop是出数据入队:往pushST中插入数据出队:判断popST是否为空,不为空直接pop,为空的话将pushST导入到popST中 取队头:跟出队一样的,但是这里不pop数据*/typedef struct{    ST pushST;//两个栈    ST popST;} MyQueue;//初始化操作MyQueue* myQueueCreate(){    MyQueue*pst=(MyQueue*)malloc(sizeof(MyQueue));    STInit(&pst->pushST);//栈的初始化    STInit(&pst->popST);    return pst;}//往pushST中插入数据void myQueuePush(MyQueue* obj, int x){    //调用栈的插入方法    SrackPush(&obj->pushST,x);//往pushST中插入数据}//删除数据int myQueuePop(MyQueue* obj){    //1.检查popST是否为空       //1)不为空直接 出       //2)为空,pushST导入到popST,在出数据    if(StackEmpty(&obj->popST))//如果为空的话,我们就进项导数据操作    {        //导数据        while(!StackEmpty(&obj->pushST))//只要不为空,我们就将这个栈内的数据导出        {            //循环取栈顶数据            //StackTop(&obj->pushST)将这个栈内的栈顶数据取出            SrackPush(&obj->popST,StackTop(&obj->pushST));            //将pushST这个栈的栈顶数据导入到popST中            //取完数据,插入完数据之后我们再将进行pop操作,换下个数            SrackPop(&obj->pushST);            //下次我们取到的就是新的栈顶元素        }    }    //取栈顶,删除栈顶元素并返回栈顶数据    int top=StackTop(&obj->popST);//将这个栈的栈顶元素保存出来    SrackPop(&obj->popST);//将栈顶元素删除,下次就是新的栈顶元素    return top;}//取队头元素int myQueuePeek(MyQueue* obj){    //1.检查popST是否为空       //1)不为空直接 出       //2)为空,pushST导入到popST,在出数据    if(StackEmpty(&obj->popST))//如果为空的话,我们就进项导数据操作    {        //导数据        while(!StackEmpty(&obj->pushST))//只要不为空,我们就将这个栈内的数据导出        {            //循环取栈顶数据            //StackTop(&obj->pushST)将这个栈内的栈顶数据取出            SrackPush(&obj->popST,StackTop(&obj->pushST));            //将pushST这个栈的栈顶数据导入到popST中            //取完数据,插入完数据之后我们再将进行pop操作,换下个数            SrackPop(&obj->pushST);            //下次我们取到的就是新的栈顶元素        }    }    //取栈顶,删除栈顶元素并返回栈顶数据    return StackTop(&obj->popST);//我们直接将这个栈顶数据返回}//判断我们的队列是否为空,就是判断这个队列里面的两个栈是否为空bool myQueueEmpty(MyQueue* obj){    //如果这两个栈都不为空,那么这个队列就不为空    return StackEmpty(&obj->pushST)  &&StackEmpty(&obj->popST);}//销毁void myQueueFree(MyQueue* obj){    STDestory(&obj->pushST);    STDestory(&obj->popST);    free(obj);    obj=NULL;}/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj);*/

题目四:设计循环队列

//推荐循环队列底层队列为数组/*插入数据:循环队列满了,就不能插入数据*//*一开始的front指向的是数组的头元素rear也是指向数组的头元素每次插入一个元素,rear就进行++操作我们在下面申请了k+1个整型的空间,最后一个空间仅仅只是占位置的,不是存储数据的,实际存储数据的只有k个假设这里是5个空间0 1 2 3 4  这是对应的下标一开始的front和rear都指向的是0,每次增加一个元素,rear++等rear指向4的时候这个数组就存满了因为是循环,最后rear++会回到front的位置那么我们可以通过(rear+1)%(k+1)==front来判断队列是否满了rear==front可以判断队列是否为空*///定义循环队列的结构typedef struct{    int *arr;    int rear;    int front;    int capacity;//保存数组的空间的大小k} MyCircularQueue;//循环队列的初始化MyCircularQueue* myCircularQueueCreate(int k)//我们根据这个K进行动态的申请内存,这里的返回值是指向循环队列的指针{    MyCircularQueue*pst=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先开辟队列的空间    //因为队列的底层结构是数组,那么我们再为数组开辟空间    pst->arr=(int*)malloc(sizeof(int)*(k+1));//我们给数组申请K+1个整型大小的空间    pst->front=pst->rear=0;    pst->capacity=k;//循环队列的容量大小是k    return pst;}//判断队列是否满了bool myCircularQueueIsFull(MyCircularQueue* obj){    return (obj->rear+1)%(obj->capacity+1)==obj->front;//就说明满了    //capacity+1是数组的容量大小,多出的1是用来占位置的}//向循环队列里面插入数据,如果成功插入就返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){    //队列如果满了的话就不能进行插入数据的操作了    if(myCircularQueueIsFull(obj))//如果满了的话,就不能插入数据了    {        return false;    }    //走到这里说明队列还没有满,我们就进行插数据操作    obj->arr[obj->rear++]=value;//插入完数据之后rear要进行++的操作    //为了保证循环的效果    /*    假设我们的rear此时在占位置的那个位置,就是多出来的1的那个位置    为了保证循环,我们要让rear回到数组的第一个位置 */    obj->rear%=obj->capacity+1;//obj->rear=obj->rear % (obj->capacity+1)//我们这里进行求余的操作,将结果给rear    //插入完成我们就返回true    return true;}//判断队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj){    return obj->rear==obj->front;}//从循环队列中删除一个元素,成功删除就返回truebool myCircularQueueDeQueue(MyCircularQueue* obj){    //既然要删除数据,那么队列就不能为空    if(myCircularQueueIsEmpty(obj))//说明这个数组为空,我们就不进行删除数据的操作了    {        return false;    }    //走到这里说明队列不为空,那么我们就进行删除操作    obj->front++;    obj->front%=obj->capacity+1;//取余    //原先front位置的数据还在,但是我们现在front已经换位置了,那么原先位置的数据就能就行插入数据了    return true;}//取对首元素,返回对应值int myCircularQueueFront(MyCircularQueue* obj){    //队列为空就没啥数据能取    //判断队列是否为空    if(myCircularQueueIsEmpty(obj))//队列为空的话我们直接返回-1    {        return -1;    }    return obj->arr[obj->front];}//取对尾元素,返回对应值int myCircularQueueRear(MyCircularQueue* obj){    //队列为空就没啥数据能取    //判断队列是否为空    if(myCircularQueueIsEmpty(obj))//队列为空的话我们直接返回-1    {        return -1;    }    //return obj->arr[obj->rear-1];//rear指向的是最后一个数据的下一个位置    //假如我们的rear指向的是0下标的数,那么rear-1不就是-1吗?这么写代码就是错的,,存在越界情况    int prev=obj->rear-1;//定义一个指针指向rear前一个数据    if(obj->rear==0)    {        prev=obj->capacity;//下标为4,那么就是这个数组的第5个位置,就是最后一个位置    }    return obj->arr[prev];    //队尾元素就是rear经历过++操作之前的位置的元素}//循环队列的销毁void myCircularQueueFree(MyCircularQueue* obj){    free(obj->arr);    free(obj);    obj=NULL;}/** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj);*/

点击全文阅读


本文链接:http://zhangshiyu.com/post/163511.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1