O(1)时间复杂度逆序栈和排序栈

浏览数：36 / 时间：2015年06月08日

两种操作都是递归实现，汉诺塔思想。

1、逆序栈

void ReverseStack(Stack& stack)
{
    if (stack.Count == 0)
        return;
    object top = stack.Pop();
    ReverseStack(stack);
    if (stack.Count == 0)
    {
        stack.Push(top);
        return;
    }
    object top2 = stack.Pop();
    ReverseStack(stack);                //p1
    stack.Push(top);
    ReverseStack(stack);                 //p2
    stack.Push(top2);        
}

举例：
例如栈
1
2 object top = stack.Pop();后栈变为 2
3 3
4 4
ReverseStack(stack); 后站变为
4
3
2
object top2 = stack.Pop();后变为
3
2
（可以注意到1是栈顶元素，4是栈底元素）
然后 ReverseStack(stack);//p1 变为
2
3
然后 stack.Push(top);变为
1
2
3
（这一步发现栈底元素4取出来了）
下面就是，
3
2
1
最后是
4
3
2
1

2、排序栈，利用逆序栈的思想实现

void Sort(Stack& stack)
{
    if (stack.Count == 0)
        return;
    object top = stack.Pop();
    Sort(stack);
    if (stack.Count == 0)
    {
        stack.Push(top);
        return;
    }
    object top2 = stack.Pop();
    if ((int)top > (int)top2)
    {
        stack.Push(top);
        Sort(stack);
        stack.Push(top2);
    }
    else
    {
        stack.Push(top2);
        Sort(stack);
        stack.Push(top);
    }
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

O(1)时间复杂度逆序栈和排序栈