引言:
北京时间 2022/12/01 凌晨0:44 ,两个字,很困,今天是队列和栈的一天,所有时间否话在了这上面,根本没空去干别的,单单是栈我今天就实现了4~5遍,目前对其的理解应该是有的,但是如果明天让我重新再来一遍,估计还能写错,队列同理,但是今天也不算是一无所获,我今天学会了如何使用队列实现栈,和如何使用栈实现队列,所以接下来我们就讲一下这两个小玩意,还有就是明天在复习的基础上我们要向单链表相关的题目进军了,虽然我昨天花了9块9买了一些二叉树的视屏,但是我们还是先刷题吧,不然前面的链表应该是不能很好的掌握
咽口口水咱继续
一、首先是使用队列实现栈(两个队列才可以哦!)
1.力扣上的题目详情:
用两个队列实现一个栈,请你使用两个队列实现一个后进先出的栈,并支持普通栈的全部四中操作
实现mystack类:
void push(int x) 将元素x压入栈顶
int pop() 移除并返回栈顶元素
int top() 返回栈顶的元素
boolean empty() 如果栈是空的,返回 true;否则,返回false
2.题目分析:
解题原理:就是通过两个队列的交换(先把所有的数据存到其中一个队列之中,保持另一个队列空)
然后把当队列满了,就将这个队列中的前n-1个数据转移到我的空队列中,然后把刚刚存数据的那个队列中的剩下的唯一的数据给拿出来就行了(这样就可以很成功的实行先进后出的栈的原则了)
然后此时空队列中的数据就是我的正常的数据(就是先进的后出,此时放在了队列的前面位置,此时就可以直接拿出来,就不需要再通过转移了,还是栈的原则(先进后出))
3.核心思路:
入数据,往不为空的队列入,保持另一个队列为空; 出数据的时候,把前n-1个数据转移到另一个队列保存,当只剩下最后一个数据的时候将其pop掉,然后另一个队列中的数据依次出队;
4.具体实现加注释:
队列的基本结构体 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; //函数的声明 void QueueInist(Queue* ps); void QueueDestory(Queue* ps); void QueuePush(Queue* ps, QDataType x); void QueuePopt(Queue* ps); size_t QueueSize(Queue* ps); bool QueueEmpty(Queue* ps); QDataType QueueBack(Queue* ps); QDataType QueueFront(Queue* ps); //队列基本功能实现后才可以进行这个题目的解决 void QueueInits(Queue* pq) { //此时为什么传参接收参数的时候不需要二级指针呢? //原因就是:我使用了两个结构体类型 assert(pq); pq->head = NULL; pq->tail = NULL; } //销毁(此时销毁的就是一个一个动态内存开辟出来的结点,这个结点就是从另一个结构体的定义之中来的) void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next;//保存下一个(因为我是一个链表) free(cur); cur = next; } pq->head = pq->tail = NULL; } //插入 void QueuePush(Queue* pq, QDataType x) { //因为此时已经把结构体的地址传过来了,所以此时就可以对结构体进行改变了 assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL;//这个就是结点是初始化 //此时先进行队列有无数据的判断 if (pq->head == NULL)//这个表示无 { //这个就是此时的把我的结构体进行改变,但是要注意进行结构体的改变一定要进行结构体地址的传递,然后要用一级指针接收 pq->head = pq->tail = newnode;//这个就是表示此时的这个队列一个值都还没有,所以此时就可以把这个newnode给我的head和tail } else//这个就是有(然后有数据,此时因为是一个队列,所以此时我们就需要在这个队列的后面插入一个新的结点,因为队列的特点(一头进一头出)),然后此时就需要在tail这个表示尾的指针后面进行一个尾插,这样就可以完成队列的插入功能 { pq->tail->next = newnode; pq->tail = newnode;//上面那个是主要的完成插入的步骤,下面这个没什么主要的功能(其实就只是想让我的tail继续保持在最后一个结点的位置而已) } } //删除 void QueuePopt(Queue* pq) { //因为队列的特性(队尾入,队头出) //所以删除数据是已经规定死了的,只能在队头删 assert(pq); //还是那两种写法:1.温柔的写法 2.暴力的写法 //if (pq->head == NULL) //{ // return; //} //assert(pq->head != NULL); //并且下面这个函数 QueueEmpty(pq) 为真就是表示此时的pq->head为空,为假就表示此时的pq->head不为空 assert(!QueueEmpty(pq));//这个在报错(就是说明此时的这个QueueEmpty(pq)函数为真,然后(!QueueEmpty(pq))加了一个感叹号就表示此时整个为假),所以此时这个断言的意思就是判断这个pq->head不为空,为空就报错 Queue* next = pq->head->next; free(pq->head); pq->head = NULL; pq->head = next;//完成这些基本的操作,我们一定还要注意几个注意点 //因为此时可能会把整个队列都给删空,所以此时当删到只有一个数据的时候,此时就要进行tail的置空,不然就有野指针问题 if (pq->head == NULL)//此时这个为空,就是表示已经删完了(但是此时只是把head给处理完了,这边还剩了一个tail指针(此时如果把最后一个数据也删掉,那么此时的tail就会变成一个野指针),所以我们在删除最后一个数据的时候,一定要注意tail的置空,不然就是野指针) { pq->tail = NULL; } } //取队头的数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//此时就是表示我的头已经为空了,所以我已经不能再去取头数据了 return pq->head->data;//这个就是表示队列头的数据 } //取队尾的数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//判断队列不为空 return pq->tail->data;//此时为了寻找我队列的尾(也就是入口),并且此时的tail就是指向我队列的尾数据,所以想要找尾中的数据,只需要把tail->data给返回去就行了 } //计算队列中的数据个数 size_t QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur != NULL)//想要计算数据个数,自然要遍历我的队列 { n++; cur = cur->next;//有了这步上面那步就不需要写成cur->next != NULL;了 } return n; } //判断队列是否为空(在删除的时候会用到,因为删除的时候队列是不可以为空的,所以要进行一定的判断) bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //上面是队列功能的实现,下面是具体关于这个题目的解答: //一定要注意:不能去改变队列的结构,只能去调用队列提供的接口函数实现 //实现栈的队列结构 typedef struct MyStack { Queue q1; //一个q1队列的结构体 Queue q2; //一个q2队列的结构体 //此时就是用这两个队列去实现我的栈 }MyStack; MyStack* myStackCreate()//此时的这个函数的作用就是,创建一个结构体然后把这个结构体的地址传给我,这样我就可以使用这个结构体的地址了 { /* MyStack st; return &st;*///返回结构体的地址(就是相当于我的自己去调用这个结构体创建变量 Queue q; 的意思,反正就是为了拿到结构体) //但是此时不能像上面这样去写,因为按照上面这样去写的意思是创建了一个局部的变量(这个变量是随着栈帧的,出了函数这个变量就会消失) //所以我此时就不可以使用局部变量(一定要在堆区搞一个变量),所以这变就可以malloc一个变量出来(这样这个变量就不会消失了) MyStack* st = (MyStack*)malloc(sizeof(MyStack));//当然有的人说可以在静态区搞一个全局的变量(但是因为全局变量容易出现各种各样的问题,所以这边我们不使用) if (st == NULL) { printf("malloc faile\n"); exit(-1); } //此时有了这个新的结构体变量(我们就要对其进行初始化) // 但是我们这边进行初始化的时候一定要注意:不能去改变队列的结构,只能去调用队列提供的接口函数实现 //就是初始化我刚刚创建的那个结构体中的指针(切记不敢直接自己初始化,最后是调用队列实现中的函数) QueueInits(&st->q1);//想要初始化结构体中的变量,就要对结构体进行改变(所以改变结构体就要传结构体的地址) QueueInits(&st->q1); //这边再次强调一遍,当我们在做oj题的时候一定不能去改变队列的结构(要通过去调用我自己实现的队列的接口函数来实现) } void myStackPush(MyStack* obj, int x) { //按照解题原理,我们这边可以很好的把这个插入函数给写出来 if (!QueueEmpty(&obj->q1))//这个就是表示此时的q1不为空 { QueuePush(&obj->q1, x); } //反正就是保持这个位置的核心原则(一个有数据,一个无数据) else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { int top = 0; //此时先默认我的q1为空,q2不为空 Queue* emptyQ = &obj->q1; Queue* noemptyQ = &obj->q2; //此时假如假设错了 if (!QueueEmpty(&obj->q1))//这个就是假设错了,此时的q1是为空,q2是不为空的 { emptyQ = &obj->q2;//此时就把这个逻辑反过来 noemptyQ = &obj->q1; } else { //这里就表示我假设对了 while (QueueSize(noemptyQ) > 1) { //此时就可以将数据进行转换了 QueuePush(emptyQ, QueueFront(noemptyQ)); QueuePopt(noemptyQ); } top = QueueFront(noemptyQ);//保存最后一个数据 QueuePopt(noemptyQ); } return top; } int myStackTop(MyStack* obj) { if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { //此时的free一定要小心,因为我的结构体中还有一个结构体所以这边的free一定要进行两次的free QueueDestory(&obj->q1); QueueDestory(&obj->q2); //记住此时是全程都不会使用队列中的结构,都是在调用我自己实现的那个队列中的结构(这个一定要注意,因为这个是一个oj题) free(obj); } int main() { MyStack* st = myStackCreate(); myStackPush(st, 1); myStackPush(st, 2); myStackPush(st, 3); myStackPush(st, 4); myStackPush(st, 5); QueueDestory(st); return 0; }
5.完整代码(力扣可提交)
typedef struct QueueNode { struct QueueNode* next; int data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; void QueueInist(Queue* ps); void QueueDestory(Queue* ps); void QueuePush(Queue* ps, int x); void QueuePopt(Queue* ps); int QueueSize(Queue* ps); int QueueEmpty(Queue* ps); int QueueBack(Queue* ps); int QueueFront(Queue* ps); typedef struct { Queue q1; Queue q2; } MyStack; void QueueInist(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, int x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); Queue* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } int QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } int QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur != NULL) { n++; cur = cur->next; } return n; } int QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } MyStack* myStackCreate() { MyStack* st = (MyStack*)malloc(sizeof(MyStack)); QueueInist(&st->q1); QueueInist(&st->q2); return st; } void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Queue* emptyQ = &obj->q1; Queue* noemptyQ = &obj->q2; if (!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; noemptyQ = &obj->q1; } while (QueueSize(noemptyQ) > 1) { QueuePush(emptyQ, QueueFront(noemptyQ)); QueuePop(noemptyQ); } int top = QueueFront(noemptyQ); QueuePop(noemptyQ); return top; } int myStackTop(MyStack* obj) { if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); }
二、使用栈实现队列(同理需要两个栈)
1.题目详情:
题目如下:使用两个栈实现一个队列,队列应该要支持一般队列支持的所有操作
实现MyQueue类:
void push(int x) 将元素x推出队列的末尾
int pop 从队列开头移除并返回元素
int peek 返回队列开头数据
boolean empty() 如果队列为空,返回true 否则返回 false
2.核心思路:
两个栈,一个专门用来入数据(pushST)一个专门用来出数据(popST)
3.具体代码实现符详细注释每一步
typedef struct Stack { int* a; int top; int capacity; }Stack; void StackInit(Stack* ps); //销毁 void StackDestory(Stack* ps); //栈顶插入 void StackPush(Stack* ps, int x); //栈顶删除 void StackPop(Stack* ps); //寻找栈顶(这个肯定是有返回值的) int StackTop(Stack* ps); //还有一个就是计算栈的大小 int StackSize(Stack* ps); //判断栈是否为空 int StackEmpty(Stack* ps); void StackInit(Stack* ps)//错误 { //int* a = NULL; //int top = 0; //int caapcity = 0; //又在犯这种一直犯的错误 ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackPush(Stack* ps, int x) { //首先我要插入数据第一步就是要弄一个新的结点出来 if (ps->capacity == ps->top)//此时这个就是表示我的容量的大小等于我的此时的数组的大小 { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity); if (tmp == NULL) { printf("realloc faile\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x;//这里的两个ps->top 的意思是不一样的,一个是起着下标的作用,一个是起记录个数的作用 ps->top++; } void StackDestory(Stack* ps) { //while (ps->top != NULL) //free(ps->top); //我真的很不理解为什么这边要这样去写 //真的要搞清楚这个东西(只是一个数组而已,因为此时的a指针指向的就是我的我开辟出来的那块空间,所以直接把这个a指针释放掉就是把所有的栈给释放掉了) assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPop(Stack* ps) { //对是对了,但是没有进行条件的判断,这边一定要进行一步不为空的判断 assert(ps->top > 0); ps->top--; } int StackTop(Stack* ps) { assert(ps->top > 0); return ps->a[ps->top - 1];//这个位置一定要理解(因为我的top一直都只是栈顶,这个top是不会改变位置的,top++的意思只是数值加加了而已,并且在括号中的top也就只是起下标的作用而已) } //我真的是人才,栈你找栈底的位置干嘛 //int StackBack(Stack* ps) //{ // return ps->a[ps->top - 1]; //} int StackSize(Stack* ps) { return ps->top; } int StackEmpty(Stack* ps) { return ps->top == 0; } typedef struct { Stack pushST; Stack popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushST); StackInit(&q->popST);//这边就还是那句话(想要改变结构体你就一定要传这个结构体的地址,不然你改个屁) return q;//这个的注意点已经是写过了,就是要注意局部变量出了函数会销毁(变成一个空指针) //所以我们这边就算是传地址也是没有用的,所以这边一定要malloc一块空间,不然随着栈帧的改变,这个变量就会销毁 //所以这变一定要用上面这个方式,不能用返回地址的方式 } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST, x); //这步就是不管三七二十一,入数据就是往pushST里面入 } int myQueuePop(MyQueue* obj) { //如果popST中没有数据就把pushST中的数据导过去 //popST中的数据就符合先进先出的顺序了 if (StackEmpty(&obj->popST)) { while (!StackEmpty(&obj->pushST)) { StackPush(&obj->popST, StackTop(&obj->pushST));//这步就是函数的嵌套(就是为了把pushST中的数据导入到popST之中),看不明白就多看几遍 StackPop(&obj->pushST); } } int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } int myQueuePeek(MyQueue* obj) { //获得最头上的数据 //如果popST中没有数据就把pushST中的数据导过去 //popST中的数据就符合先进先出的顺序了 if (StackEmpty(&obj->popST)) { while (!StackEmpty(&obj->pushST)) { StackPush(&obj->popST, StackTop(&obj->pushST));//这步就是函数的嵌套(就是为了把pushST中的数据导入到popST之中),看不明白就多看几遍 StackPop(&obj->pushST); } } return StackTop(&obj->popST);//一定要记住这个popST是一个栈,是栈,所以我在使用函数时,要按照栈的方式去使用,不然完蛋 } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); } void myQueueFree(MyQueue* obj) { //只是是两层 StackDestory(&obj->pushST); StackDestory(&obj->popST); free(obj); }
4.完整代码(力扣可提交)
typedef struct stack { int* a; int capacity; int top; }stack; void StackPush(stack* ps, int x); void StackInit(stack* ps); int StackTop(stack* ps); int StackSize(stack* ps); int StackEmpty(stack* ps); int StackPop(stack* ps); void StackDestory(stack* ps); int myQueueFront(MyQueue* ps); void myQueuePush(MyQueue* ps, int x); void myQueueDestory(MyQueue* ps); int myQueueEmpty(MyQueue* ps); //1. void StackPush(stack* ps, int x) { if (ps->capacity == ps->top) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapacity); if (tmp == NULL) { printf("realloc faile\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void StackInit(stack* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } int StackTop(stack* ps) { assert(ps); return ps->a[ps->top - 1]; } void StackDestory(stack* ps) { assert(ps); free(ps->a); ps->a = NULL; } int StackPop(stack* ps) { assert(ps->top > 0); ps->top--; } int StackSize(stack* ps) { return ps->top; } int StackEmpty(stack* ps) { return ps->top == 0; } typedef struct MyQueue { stack Push; stack Pop; }MyQueue; MyQueue* myQueueCreate() { MyQueue* q = malloc(sizeof(MyQueue)); StackInit(&q->Pop); StackInit(&q->Push); return q; } void myQueuePush(MyQueue* ps,int x) { StackPush(&ps->Push, x); } void myQueuePop(MyQueue* ps) { if (StackEmpty(&ps->Pop)) { while (!StackEmpty(&ps->Push)) { StackPush(&ps->Pop, StackTop(&ps->Push)); } } int front = StackTop(&ps->Pop); StackPop(&ps->Pop); return front; } int myQueueEmpty(MyQueue* ps) { return StackEmpty(&ps->Pop) && StackEmpty(&ps->Push); } int myQueueFront(MyQueue* ps) { if (StackEmpty(&ps->Pop)) { while (!StackEmpty(&ps->Push)) { StackPush(&ps->Pop, StackTop(&ps->Push)); } } return StackTop(&ps->Pop); } void myQueueDestory(MyQueue* ps) { StackDestory(&ps->Pop); StackDestory(&ps->Push); free(ps); ps = NULL; } int main() { MyQueue* q; myQueuePush(&q, 1); myQueuePush(&q, 2); //myQueuePush(&q->Pop, 3); while (!myQueueEmpty(&q)) { printf("%d", myQueueFront(&q)); myQueuePop(&q->Pop); } myQueueDestory(&q); return 0; }
总结:
一定要多练,虽然很磨人,加油代码人。