2016做网站,pxhere素材网站,网页设计与制作教程的页数是,新手学做百度联盟网站题目描述:
请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。
实现 MyStack 类#xff1a;
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元…题目描述:
请你仅使用两个队列实现一个后入先出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双端队列来模拟一个队列 , 只要是标准的队列操作即可。
题目链接:力扣LeetCode官网 - 全球极客挚爱的技术成长平台
功能实现思路:
在实现这个题目之前得先完成队列的基本操作,可以参考文章:http://t.csdnimg.cn/3v2IZ
1. 出栈
现在我们有两个队列,假设在第一个队列里依次入了1 2 3 4 5,另一个队列为空队列 现在要出栈的话,应该把5出去,但是数据目前在队列里,出数据只能从队头出,所以可以把1 2 3 4依次出队列,并入到第二个队列中,此时就可以把5出去了,此时又是一个队列为空,另一个存着剩余的数据,再出栈的话,还按照这个方法即可 int myStackPop(MyStack* obj) {//由于不知道哪个队列为空队列,可以采用假设法Queue* empty obj-queue1;Queue* nonemptyobj-queue2;if(!QueueEmpty(obj-queue1)){emptyobj-queue2;nonemptyobj-queue1;}while(QueueSize(nonempty)1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int topQueueFront(nonempty);QueuePop(nonempty);return top;
}
总结:
出栈操作相当于非空队列的队尾元素出队,此时需要把非空队列除最后一个元素之外的其他元素入队到空队列,然后出队最后一个队尾元素
2.入栈
入栈操作相当于在非空队列进行入队操作 void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-queue1)){QueuePush(obj-queue1,x);}else{QueuePush(obj-queue2,x);}
}
3.判空
只要两个队列都没有元素就表示栈空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-queue1)QueueEmpty(obj-queue2);
}
4.返回栈顶元素
即返回非空队列队尾元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-queue1)){return QueueTail(obj-queue1);}else{return QueueTail(obj-queue2);}
}
typedef int QDataType;
typedef struct QueueNode {QDataType x;struct QueueNode* next;
}Node;typedef struct Queue
{Node* head;Node* tail;int size;
}Queue;void QueueInit(Queue* ps);
void QueuePush(Queue* ps,QDataType x);
void QueuePop(Queue* ps);
bool QueueEmpty(Queue* ps);
QDataType QueueFront(Queue* ps);
QDataType QueueTail(Queue* ps);
int QueueSize(Queue* ps);
void QueueDestory(Queue* ps);void QueueInit(Queue* ps)
{assert(ps);ps-head ps-tail NULL;ps-size 0;
}void QueuePush(Queue* ps, QDataType x)
{assert(ps);//创建新节点Node* newnode (Node*)malloc(sizeof(Node));if (newnode NULL){perror(malloc);return;}newnode-next NULL;newnode-x x;//尾插if (ps-tail NULL){ps-head ps-tail newnode;}else{ps-tail-next newnode;ps-tail ps-tail-next;}ps-size;
}void QueuePop(Queue* ps)
{assert(ps);assert(ps-head);if (ps-head-next NULL){ps-head ps-tail NULL;}else{Node* next ps-head-next;free(ps-head);ps-head next;}ps-size--;
}bool QueueEmpty(Queue* ps)
{assert(ps);return ps-tail NULL;
}QDataType QueueFront(Queue* ps)
{assert(ps);assert(ps-head);return ps-head-x;
}QDataType QueueTail(Queue* ps)
{assert(ps);assert(ps-tail);return ps-tail-x;
}int QueueSize(Queue* ps)
{assert(ps);return ps-size;
}void QueueDestory(Queue* ps)
{assert(ps);Node* cur ps-head;while (cur){Node* next cur-next;free(cur);cur next;}ps-headps-tail NULL;ps-size0;
}typedef struct {Queue queue1;Queue queue2;
} MyStack;MyStack* myStackCreate() {MyStack* mystack(MyStack*)malloc(sizeof(MyStack));QueueInit(mystack-queue1);QueueInit(mystack-queue2);return mystack;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-queue1)){QueuePush(obj-queue1,x);}else{QueuePush(obj-queue2,x);}
}int myStackPop(MyStack* obj) {Queue* empty obj-queue1;Queue* nonemptyobj-queue2;if(!QueueEmpty(obj-queue1)){emptyobj-queue2;nonemptyobj-queue1;}while(QueueSize(nonempty)1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int topQueueFront(nonempty);QueuePop(nonempty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-queue1)){return QueueTail(obj-queue1);}else{return QueueTail(obj-queue2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-queue1)QueueEmpty(obj-queue2);
}void myStackFree(MyStack* obj) {QueueDestory(obj-queue1);QueueDestory(obj-queue2);free(obj);
} 文章转载自： http://www.morning.mwns.cn.gov.cn.mwns.cn http://www.morning.qbrdg.cn.gov.cn.qbrdg.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.txfzt.cn.gov.cn.txfzt.cn http://www.morning.clgbb.cn.gov.cn.clgbb.cn http://www.morning.qwbls.cn.gov.cn.qwbls.cn http://www.morning.wqbhx.cn.gov.cn.wqbhx.cn http://www.morning.mjdbd.cn.gov.cn.mjdbd.cn http://www.morning.tfwg.cn.gov.cn.tfwg.cn http://www.morning.ejknty.cn.gov.cn.ejknty.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.glnxd.cn.gov.cn.glnxd.cn http://www.morning.rgsgk.cn.gov.cn.rgsgk.cn http://www.morning.ptmgq.cn.gov.cn.ptmgq.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.ngznq.cn.gov.cn.ngznq.cn http://www.morning.lxkhx.cn.gov.cn.lxkhx.cn http://www.morning.ksqyj.cn.gov.cn.ksqyj.cn http://www.morning.bmyrl.cn.gov.cn.bmyrl.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.rzmsl.cn.gov.cn.rzmsl.cn http://www.morning.zzgkk.cn.gov.cn.zzgkk.cn http://www.morning.phwmj.cn.gov.cn.phwmj.cn http://www.morning.jwqqd.cn.gov.cn.jwqqd.cn http://www.morning.bmyrl.cn.gov.cn.bmyrl.cn http://www.morning.mtdfn.cn.gov.cn.mtdfn.cn http://www.morning.dgsx.cn.gov.cn.dgsx.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.fnczn.cn.gov.cn.fnczn.cn http://www.morning.tztgq.cn.gov.cn.tztgq.cn http://www.morning.hjlwt.cn.gov.cn.hjlwt.cn http://www.morning.rtsdz.cn.gov.cn.rtsdz.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.gsqw.cn.gov.cn.gsqw.cn http://www.morning.bxqpl.cn.gov.cn.bxqpl.cn http://www.morning.ycmpk.cn.gov.cn.ycmpk.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn http://www.morning.bpmnh.cn.gov.cn.bpmnh.cn http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.kaylyea.com.gov.cn.kaylyea.com http://www.morning.qhmql.cn.gov.cn.qhmql.cn http://www.morning.ykwqz.cn.gov.cn.ykwqz.cn http://www.morning.thbqp.cn.gov.cn.thbqp.cn http://www.morning.mhdwp.cn.gov.cn.mhdwp.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.hyryq.cn.gov.cn.hyryq.cn http://www.morning.jygsq.cn.gov.cn.jygsq.cn http://www.morning.plflq.cn.gov.cn.plflq.cn http://www.morning.khlxd.cn.gov.cn.khlxd.cn http://www.morning.qxycf.cn.gov.cn.qxycf.cn http://www.morning.mcqhb.cn.gov.cn.mcqhb.cn http://www.morning.xcdph.cn.gov.cn.xcdph.cn http://www.morning.bpmtq.cn.gov.cn.bpmtq.cn http://www.morning.qlhwy.cn.gov.cn.qlhwy.cn http://www.morning.nmlpp.cn.gov.cn.nmlpp.cn http://www.morning.reababy.com.gov.cn.reababy.com http://www.morning.rcrnw.cn.gov.cn.rcrnw.cn http://www.morning.rmkyb.cn.gov.cn.rmkyb.cn http://www.morning.dnphd.cn.gov.cn.dnphd.cn http://www.morning.fygbq.cn.gov.cn.fygbq.cn http://www.morning.rzysq.cn.gov.cn.rzysq.cn http://www.morning.hcgbm.cn.gov.cn.hcgbm.cn http://www.morning.lxyyp.cn.gov.cn.lxyyp.cn http://www.morning.jpmcb.cn.gov.cn.jpmcb.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn http://www.morning.sypby.cn.gov.cn.sypby.cn http://www.morning.nqbkb.cn.gov.cn.nqbkb.cn http://www.morning.gmgnp.cn.gov.cn.gmgnp.cn http://www.morning.cgtfl.cn.gov.cn.cgtfl.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.mnnxt.cn.gov.cn.mnnxt.cn http://www.morning.fmkbk.cn.gov.cn.fmkbk.cn http://www.morning.rsxw.cn.gov.cn.rsxw.cn http://www.morning.lfjmp.cn.gov.cn.lfjmp.cn http://www.morning.qghjc.cn.gov.cn.qghjc.cn http://www.morning.lhldx.cn.gov.cn.lhldx.cn
