10.1-6
Q:说明如何用两个栈来实现一个队列，并分析有关队列操作的运行时间。
A:栈是先进后出，而队列是先进先出，一种自然的想法是，用一个栈来存储队列的元素，入队就和如栈一样； 出队的时候先将这个栈的元素依次压出另一个栈内，然后将栈顶元素(即队首)弹出，然后再依次倒回原先的栈内。 这样入队为O(1)，出队为O(n)。仔细想想，并不需要每次都将当前所有元素在两个栈内倒来倒去， 只需要入队用一个栈，出队用另一个栈: 入队操作即在第一个栈上执行入栈；出队操作时，若第二个栈不为空，则在第二个栈上执行出栈， 若第二个栈为空，则将第一个栈内的元素依次全部压入第二个栈内。这样入队出队操作都为O(1)的复杂度。
10.1-7
Q:说明如何用两个队列来实现一个栈，并分析有关栈操作的运行时间。
A:一种自然的想法，类似于上一题，用一个队存储，另一个队列作为临时空间。入栈时就向第一个队列中插入元素； 出栈时，先将第一个队列中除队尾(栈顶)的元素依次出队后进入第二个队列，然后将队尾(栈顶 ...
more…Read full article from H.y's Blog
No comments:
Post a Comment