how to use stack(s) to realize a queque - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

how to use stack(s) to realize a queque

how to use stack(s) to realize a queque# Programming - 葵花宝典

a*g2008-01-06 08:01

1 楼

An interview question. I proposed using two stacks, whenever changing action
(pop->push or push->pop), put all data from one stack to the other. I was
told it was too slow.
Any idea? thanks

t*t2008-01-06 08:01

2 楼

一个明显的改进是这样, 每次朝stack A里push (push stack).
pop时,从stack B (pop stack) pop. 如果pop时遇到B为空,则把A搬到B.
这样平均复杂度还是O(1). 不过不能保证每个操作都是O(1).

action

【在 a*****g 的大作中提到】

: An interview question. I proposed using two stacks, whenever changing action
: (pop->push or push->pop), put all data from one stack to the other. I was
: told it was too slow.
: Any idea? thanks