算法导论10.16习题解答(用两个栈实现一个队列)

CLRS 10.1-6 :
说明如何用两个栈来实现一个队列,并分析有关队列操作的运行时间。

解法:
1.有两个栈s1和s2,先往s1内插入a,b,c,这做的都是enqueue操作。
2.现在要做dequeue操作,即要得到a,这时可以将s1中的元素全部弹出并存入s2中,这时s2中元素的顺序(从底部到顶部)为c,b,a,这时做s2.pop()操作即可得到a。
3.如果继续做enqueue操作,比如插入d,f,则把d,f插入到s1中,
4.此时若要做dequeue操作,则直接弹出s2中的b,它是目前为止,呆得时间最长的元素
5.若继续做dequeue操作,则s2弹出c,
6.若继续做dequeue操作,则s2为空,此时做步骤2的操作,
7.以此类推,就实现了用两个栈来实现一个队列的目的。

插入操作的时间为O(1),删除操作的时间<=O(n),即小于线性时间,有时可能为O(1).

原文地址:https://www.cnblogs.com/null00/p/2065058.html