网站建设管理工作情况汇报,wordpress 电话登记插件,做旅行网站的依据及意义,网址用队列实现实现栈
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-st…用队列实现实现栈
力扣LeetCode官网 - 全球极客挚爱的技术成长平台备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-stack-using-queues/
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 示例
输入
[MyStack, push, push, top, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]解释
MyStack myStack new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False 队列的基础操作
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int QSLDataType;
typedef struct QueueNode
{QSLDataType x;struct QueueNode*next;
}QNode;typedef struct Queue
{QNode*head;QNode*tail;
}Queue;void QueueInit(Queue* pq){assert(pq);pq-headpq-tailNULL;
}
void QueueDestory(Queue* pq){assert(pq);QNode*curpq-head;while(cur){QNode*nextcur-next;free(cur);curnext;}pq-headpq-tailNULL;
}void QueuePush(Queue* pq,QSLDataType x){assert(pq);QNode* newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL){printf(malloc fail\n);exit(-1);}newnode-xx;newnode-nextNULL;if(pq-tailNULL){pq-headpq-tailnewnode;}else{pq-tail-nextnewnode;pq-tailnewnode;}
}
void QueuePop(Queue* pq){assert(pq);assert(pq-head);if(pq-head-nextNULL){free(pq-head);pq-headpq-tailNULL;}else{QNode*nextpq-head-next;free(pq-head);pq-headnext;}
}QSLDataType QueueFront(Queue* pq){assert(pq);assert(pq-head);return pq-head-x;
}
QSLDataType QueueBack(Queue* pq){assert(pq);assert(pq-head);return pq-tail-x;
}int QueueSize(Queue* pq){assert(pq);QNode*curpq-head;int cnt0;while(cur){cnt;curcur-next;}return cnt;
}
bool QueueEmpty(Queue* pq){assert(pq);return pq-headNULL;
}
int main(){Queue q;QueueInit(q);QueuePush(q,1);QueuePush(q,2);QueuePush(q,3);QueuePush(q,4);while(!QueueEmpty(q)){printf(%d\n,QueueFront(q));QueuePop(q);}QueueDestory(q);return 0;
}
用两个队列实现一个栈。 nonemptyQ是一个指针类型实现myStackPop不需要对其。
代码
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* ps (MyStack*)malloc(sizeof(MyStack));if (ps NULL) {printf(malloc fail\n);exit(-1);}QueueInit(ps-q1);QueueInit(ps-q2);return ps;
}void myStackPush(MyStack* obj, int x) {assert(obj);if (!QueueEmpty(obj-q1)) {QueuePush(obj-q1,x);}else {QueuePush(obj-q2, x);}
}int myStackPop(MyStack* obj) {Queue* emptyQ obj-q1;Queue* nonemptyQ obj-q2;if (!QueueEmpty(obj-q1)) {emptyQ obj-q2;nonemptyQ obj-q1;}while (QueueSize(nonemptyQ) 1) {QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int top QueueFront(nonemptyQ);QueuePop(nonemptyQ);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);
}
