C++-不使用额外的空间实现栈的反转

C++-不使用额外的空间实现栈的反转

虐人心 发布于 2017-06-19 字数 192 浏览 1244 回复 3

给定一个栈,比如Stack s。s可以使用的函数有:push、pop、top、isEmpty。
现在向s中压入一些数字:1、2、3、4、5
要求:不能申请额外的空间(比如定义另外一个栈、数组等)实现栈的反转。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

归属感 2017-08-12 3 楼

我认为只申请常数空间(也就是LZ的“不用额外空间”)在stack上无法完成Reverse。
因为stack只有push()和pop()。要将stack Reverse就必须要将最底的元素取出来,而在pop出最底元素时,其它元素必然已经被pop出来,如果要不丢失这些元素必然需要额外的非常数(线性)空间来存储。所以在stack上仅使用常数空间无法完成Reverse。

瑾兮 2017-08-03 2 楼

这个跟汉诺塔问题还是有些相同之处的,直接给代码吧:

static void ReverseStack(Stack& stack)
{
if (isEmpty(stack))
return;
object top = stack.pop();
ReverseStack(stack);
if (isEmpty(stack))
{
stack.push(top);
return;
}
object top2 = stack.pop();
ReverseStack(stack);
stack.push(top);
ReverseStack(stack);
stack.push(top2);
}

这里用到了两个局部变量,不知道是否符合楼主的要求?

参考链接:栈和队列

虐人心 2017-06-23 1 楼

我觉得这个题目没办法完成的,假设题目不是栈反转。假设就是一根柱子的汉诺塔。从下到上有10个盘子。要求不用其他柱子就要反转。这个也是不可能的。个人观点