网站建设怎样回答客户问题,市长调度国庆假期安全稳定工作,北京正规网站建设公司哪家好,哪个网站是可以做书的. - 力扣#xff08;LeetCode#xff09;
题目描述 解题思路
这道题的思路就是使用两个队列来实现
入栈就是入队列
出栈就是将非空队列的前n-1个元素移动到新的队列中去
再将最后一个元素弹出
动画详解 代码实现 #define _CRT_SECURE_NO_WARNINGS 1#include stdio.…. - 力扣LeetCode
题目描述 解题思路
这道题的思路就是使用两个队列来实现
入栈就是入队列
出栈就是将非空队列的前n-1个元素移动到新的队列中去
再将最后一个元素弹出
动画详解 代码实现 #define _CRT_SECURE_NO_WARNINGS 1#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType x;
}QNode;// 使用另一个结构体来存储头尾指针指向队列的头尾
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-x x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size ! 0);/*QNode* next pq-phead-next;free(pq-phead);pq-phead next;if (pq-phead NULL)pq-ptail NULL;*/// 一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else // 多个节点{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-x;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-x;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueIsEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate()
{// 使用malloc开辟新的栈防止局部变量出作用域之后被销毁// 不能使用全局变量因为下一次调用的时候全局变量不会初始化MyStack* obj (MyStack*)malloc(sizeof(MyStack));// 调用队列初始化函数对两个队列进行初始化QueueInit((obj-q1));QueueInit((obj-q2));return obj;
}void myStackPush(MyStack* obj, int x)
{// 向不为空的队列插入数据if (QueueIsEmpty(obj-q1)){QueuePush((obj-q1), x);}else{QueuePush((obj-q2), x);}
}int myStackPop(MyStack* obj)
{// 将前size-1个数据弹出导入到不为空的队列中去再删除非空队列中的最后一个数据// 使用假设法来判断空队列Queue* empty (obj-q1);Queue* notempty (obj-q2);if (!QueueIsEmpty((obj-q1))){notempty (obj-q1);empty (obj-q2);}// 开始遍历while (QueueSize(notempty) 1){// 向空队列中插入非空队列中的数据QueuePush(empty, QueueFront(notempty));// 弹出非空队列的数据QueuePop(notempty);}int top QueueFront(notempty);// 弹出非空队列中的最后一个数据实现出栈操作QueuePop(notempty);return top;
}int myStackTop(MyStack* obj)
{if (!QueueIsEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}bool myStackEmpty(MyStack* obj)
{return QueueIsEmpty((obj-q1)) QueueIsEmpty((obj-q2));}void myStackFree(MyStack* obj)
{// 不能直接释放obj因为还有剩下的链表没有释放将成为野指针QueueDestroy(obj-q1);QueueDestroy(obj-q2);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);
*/
复杂度分析
我们可以发现这个代码仅有在将非空队列的元素导入空队列时有循环因此时间复杂度为O(n)
总结
Bye!!
