腾讯企业邮箱收费标准一年多少钱,网站排名优化效果,软装设计师培训机构,宁波网站开发公司电话这时一道非常经典的题型#xff0c;因为栈和队列的性质是相反的#xff0c;队列的数据是先入先出#xff0c;栈的数据是后入先出#xff0c;那么怎样使用两个队列实现栈呢#xff1f;
225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/ 这是… 这时一道非常经典的题型因为栈和队列的性质是相反的队列的数据是先入先出栈的数据是后入先出那么怎样使用两个队列实现栈呢
225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/ 这是题目的要求如果使用C语言来实现的话只能自己写一个队列了这里我就不详细讲解了具体实现思路在这
http://t.csdnimg.cn/0SiCqhttp://t.csdnimg.cn/0SiCq代码如下
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
void QueueInit(Que* pq)
{assert(pq);pq-size 0;pq-head pq-tail NULL;
}
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(malloc fail);exit(-1);}tmp-data x;tmp-next NULL;if (pq-tail NULL){pq-head pq-tail tmp;}else{pq-tail-next tmp;pq-tail tmp;}pq-size;
}
void QueuePop(Que* pq)
{assert(pq);assert(pq-head);if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
QDataType QueueFront(Que* pq)
{assert(pq);assert(pq-head);return pq-head-data;
}
QDataType QueueBack(Que* pq)
{assert(pq);assert(pq-head);return pq-tail-data;
}
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}
实现思路
在实现这个栈之前我们需要有一个具体思路栈是后进先出队列是先进后出那么在插入上是没有区别的在删除上就需要将对列的尾部删除那么如何实现对列的尾部删除呢这就需要将其中一个对列nonempty的数据导入到另一个对列empty直到nonempty只剩一个数据然后头删即可。 删除之后将nonempty和empty互换即可必须保证其中一个队列为空。
1.栈的定义
题目要求是使用两个队列实现栈那么就直接在栈的定义里面包含两个队列即可。
typedef struct
{Que q1;Que q2;
} MyStack;
2.栈的初始化
为栈malloc一块空间在使用QueueInit实现两个队列的初始化。
MyStack* myStackCreate()
{MyStack* obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-q1);QueueInit(obj-q2);return obj;
}
3.数据入栈
数据入栈需要将数据push到不为空的那个队列使用QueueEmpty判断队列是否为空再使用QueuePush尾插数据。
void myStackPush(MyStack* obj, int x)
{if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}
4.数据出栈
这个是题目的难点创建两个变量分别为nonempty(非空队列)和empty(空队列在使用if判断q1和q2哪个为空。使用while循环来实现遍历插入和删除结束条件为nonempty内的数据为1也就是队列的尾部数据在循环内使用QueuePush将nonempty的头部数据插入到empty每次插入之后要删除掉原节点。到这里还需要注意的是题目要求返回这个数据所以要创建一个变量返回这个数据最后再删除掉始终保存一个队列为空。
int myStackPop(MyStack* obj)
{Que* emptyobj-q1;Que* nonemptyobj-q2;if(!QueueEmpty(obj-q1)){nonemptyobj-q1;emptyobj-q2;}else{nonemptyobj-q2;emptyobj-q1;}//将前size-1个元素导入空队列while(QueueSize(nonempty)1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret QueueFront(nonempty);QueuePop(nonempty);return ret;
}
5.取栈顶数据
栈顶数据也就是队列的尾部数据使用QueueBack直接取nonempty的尾部数据即可。
int myStackTop(MyStack* obj)
{if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}
6.判断栈是否为空
栈由两个队列组成直接使用QueueEmpty判断两个队列是否为空即可配合必须两个都为空才返回true。
bool myStackEmpty(MyStack* obj)
{return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}
7.毁栈销
使用QueueDestroy销毁掉两个队列再free掉栈的空间即可。
void myStackFree(MyStack* obj)
{QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}
完整代码
typedef struct
{Que q1;Que q2;
} MyStack;MyStack* myStackCreate()
{MyStack* obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-q1);QueueInit(obj-q2);return obj;
}void myStackPush(MyStack* obj, int x)
{if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}}int myStackPop(MyStack* obj)
{Que* emptyobj-q1;Que* nonemptyobj-q2;if(!QueueEmpty(obj-q1)){nonemptyobj-q1;emptyobj-q2;}else{nonemptyobj-q2;emptyobj-q1;}//将前size-1个元素导入空队列while(QueueSize(nonempty)1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret QueueFront(nonempty);QueuePop(nonempty);return ret;
}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)
{QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
} 今天的分享到这里就结束啦谢谢老铁们的阅读让我们下期再见。
