用队列实现栈
其实和用栈实现队列及其的相似🐱🐉.能看懂第一题的可以用这道题来试验一下自己的学习成功.
用队列实现栈相对用栈实现队列要效率低一些.
大致思路
通过两个队列来实现栈.
队列实现栈.
队列打入顺序为
12345时读取数据时12345
但是我们的栈要的顺序是54321.
两个队列时我们用和上一题同样的思路是不行的.
但是我们可以留下一个数据比如
p1存放12345.
p2存放:无.
将p1的元素的除最后一个元素放入到p2中
操作后如下
p1: 5
p2: 1234
然后我们将p1的值给出就可👍.
队列的代码
typedef int QDatetype; typedef struct QueueNode { int date; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq,QDatetype x) { if (pq->tail == NULL) { pq->head = pq->tail = (QNode*)malloc(sizeof(QNode)); if (pq->tail == NULL) { exit(-1); } pq->head->date = x; pq->tail->next = NULL; } else { QNode* tail = pq->tail; QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("ʧ\n"); exit(-1); } newnode->date = x; newnode->next = NULL; tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } QDatetype QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->date; } QDatetype QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->date; }
这部分是我手搓的队列,用不习惯的可以改改👍.
正确代码
typedef struct { Queue p1; Queue p2; } MyStack; MyStack* myStackCreate() { MyStack* ST = (MyStack*)malloc(sizeof(MyStack)); assert(ST); QueueInit(&ST->p1); QueueInit(&ST->p2); return ST; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->p1)) { QueuePush(&obj->p1,x); } else { QueuePush(&obj->p2,x); } } int myStackPop(MyStack* obj) { Queue* empty = &obj->p1; Queue* nonEmpty = &obj->p2; if(!QueueEmpty(empty)) { empty = &obj->p2; nonEmpty = &obj->p1; } while(QueueSize(nonEmpty)>1) { int num = QueueFront(nonEmpty); QueuePush(empty,num); QueuePop(nonEmpty); } int ret = QueueFront(nonEmpty); QueuePop(nonEmpty); return ret; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->p1)) { return QueueBack(&obj->p1); } else { return QueueBack(&obj->p2); } } bool myStackEmpty(MyStack* obj) { if(QueueEmpty(&obj->p1)&&QueueEmpty(&obj->p2)) { return 1; } else { return 0; } } void myStackFree(MyStack* obj) { QueueDestory(&obj->p1); QueueDestory(&obj->p2); free(obj); } /** * 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 struct { Queue p1; Queue p2; } MyStack; MyStack* myStackCreate() { MyStack* ST = (MyStack*)malloc(sizeof(MyStack)); assert(ST); QueueInit(&ST->p1); QueueInit(&ST->p2); return ST; }
结构体
结构体里装着两个队列时设计好的结构类型.
MyStack* myStackCreate()
这个函数还是简单的初始化两个队列和结构体的栈类型变量的实现
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->p1)) { QueuePush(&obj->p1,x); } else { QueuePush(&obj->p2,x); } } int myStackPop(MyStack* obj) { Queue* empty = &obj->p1; Queue* nonEmpty = &obj->p2; if(!QueueEmpty(empty)) { empty = &obj->p2; nonEmpty = &obj->p1; } while(QueueSize(nonEmpty)>1) { int num = QueueFront(nonEmpty); QueuePush(empty,num); QueuePop(nonEmpty); } int ret = QueueFront(nonEmpty); QueuePop(nonEmpty); return ret; }
栈的推送
推送的时候我们要保证一个队列是空的这样才能达到我们想要的目的.
所以我们用if条件句来判断那个队列不为空,不为空就将元素放到他那里这样就就可以保证一个队列是完全空的了.
为啥要保证一个队列是空的呢?
在pop的时候就知道了
原先的思路就是将有元素的队列内的除倒数第一个元素外都转移到另一个空的队列中.
然后将最后一个元素返回,再删除去最后的元素.这样我们的队列就又有一个为空了,可以循环使用下去了.
注意事项
我们要得到空和非空的队列假设是p1然后再通过if来判断是p1还是p2
记得将最后一个元素pop掉哦~.
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->p1)) { return QueueBack(&obj->p1); } else { return QueueBack(&obj->p2); } } bool myStackEmpty(MyStack* obj) { if(QueueEmpty(&obj->p1)&&QueueEmpty(&obj->p2)) { return true; } else { return false; } } void myStackFree(MyStack* obj) { QueueDestory(&obj->p1); QueueDestory(&obj->p2); free(obj); }
栈顶元素的获得
其实很简单直接看非空队列的队尾数就好👍
判断是否为空
两个队列都为空及为空,否则就不为空.
队列摧毁
将两个队列都摧毁后free掉obj即可👍.
结尾
舒文想要机器人呜呜呜呜呜呜呜呜呜呜😭😭😭😭😭
