算法导论 10.1-7
浏览数：14 /
时间：2015年06月08日
题目：用两个队列实现一个栈，并分析栈操作运行时间
分析：
栈的操作只能在表头进行；而队列的入队在表头进行，出队只能在栈尾进行；
考虑将栈底元素变为栈顶元素，即进行倒置，就能在表头进行Pop操作；
解答：（不考虑溢出）
1、使用两个队列A与Tmp，Tmp队列作为中转；
2、当进行Push操作时，在队列A中进行入队操作；
3、当进行Pop操作时，使队列A中的元素出队并进队在队列Tmp中，直到队列A为空，则队列实现了倒置，队头元素变为队尾元素，Tmp执行出队操作，在对Tmp实行同样步骤，将元素倒置到队列A中
操作运行时间分析：
Push：O(1)
Pop：O(N)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
