请大虾验证! - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

请大虾验证!

请大虾验证!# Programming - 葵花宝典

l*l2007-02-03 08:02

1 楼

俺在 JOBHUNTING 做的一道题, 不知是否正确, 请大虾验证!
Design an efficient algorithm to sort elements in a stack in either
ascending/descending order, using only pop(), top(), push(), isEmpty(),
isFull(). Do not use any auxiliary stacks or arrays.
How about this?

l*l2007-02-03 08:02

2 楼

俺优化以下:
void sort(stack &s, int numSorted)
{
element *e1;
element *e2;
if (s.size() <= 1+numSorted) {
return;
}
e1 = s.pop();
if(e1 < s.top()) {
e2 = s.pop();
s.push(e1);
sort(s);
s.push(e2);
} else {
sort(s);
s.push(e1);
}
}

【在 l*****l 的大作中提到】

: 俺在 JOBHUNTING 做的一道题, 不知是否正确, 请大虾验证!
: Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: How about this?

q*c2007-02-03 08:02

3 楼

这个是 meaningless...用的内存比全部新开 array 多，
效率低下，不知道这题目为啥。而且 sort(stack)
函数也没定义，不知道咋运行。
这个题目一定要多余的内存，否则罪底下那个元素无法出来。

【在 l*****l 的大作中提到】

: 俺优化以下:
: void sort(stack &s, int numSorted)
: {
: element *e1;
: element *e2;
: if (s.size() <= 1+numSorted) {
: return;
: }
: e1 = s.pop();
: if(e1 < s.top()) {

c*t2007-02-03 08:02

4 楼

the only minor problem i see is that size () is not provided.

【在 l*****l 的大作中提到】

l*l2007-02-03 08:02

5 楼

I think I can use isEmpty()/isFull():)

【在 c*****t 的大作中提到】

: the only minor problem i see is that size () is not provided.

P*f2007-02-03 08:02

6 楼

多余内存在递归的程序stack上
所以这个题有点好玩:不能用辅助栈，但是可以用程序调用的栈
嘿嘿

这个是 meaningless...用的内存比全部新开 array 多，
效率低下，不知道这题目为啥。而且 sort(stack)
函数也没定义，不知道咋运行。
这个题目一定要多余的内存，否则罪底下那个元素无法出来。

【在 q*c 的大作中提到】

: 这个是 meaningless...用的内存比全部新开 array 多，
: 效率低下，不知道这题目为啥。而且 sort(stack)
: 函数也没定义，不知道咋运行。
: 这个题目一定要多余的内存，否则罪底下那个元素无法出来。

l*l2007-02-03 08:02

7 楼

这个也就是面世题, 没有实际意义. 如果有N个数, 要做N层RECURSION.
N必须很小才行.

【在 P*****f 的大作中提到】

: 多余内存在递归的程序stack上
: 所以这个题有点好玩:不能用辅助栈，但是可以用程序调用的栈
: 嘿嘿
:
: 这个是 meaningless...用的内存比全部新开 array 多，
: 效率低下，不知道这题目为啥。而且 sort(stack)
: 函数也没定义，不知道咋运行。
: 这个题目一定要多余的内存，否则罪底下那个元素无法出来。