栈转置与栈排序

1. 问题描述

（1） 用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

（2） 用递归方法对栈进行排序。

2. 解决方案

这两个问题主要是考察应聘者对递归的理解。递归程序有两个关键因素：递归定义和递归终止条件。

（1） 问题1

经过分析后，很容易得到该问题的递归定义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后继续不包含该栈顶元素的子栈。终止条件：递归下去，直到栈为空。代码如下：

//将栈底元素移动到栈顶 
void move_bottom_to_top(stack& s)  {
  if(s.empty()) return;
  int top1 = s.top();
  s.pop();
  if(!s.empty()) {
    move_bottom_to_top(s);
    int top2 = s.top();
    s.pop();
    s.push(top1); //通过交换元素的方式移动 
    s.push(top2);   
    return;         
  }  
  s.push(top1); 
}
 
//颠倒整个栈 
void reverse_stack(stack& s) {
  if(s.empty()) return;
  move_bottom_to_top(s); //将栈底元素移动到栈顶 
  int top = s.top();
  s.pop();
  reverse_stack(s); //递归处理子栈 
  s.push(top);
}

（2） 问题2

栈排序与栈翻转思想基本一致，稍微修改上面的代码便可得到栈就地排序代码：

void move_min_to_top(stack& s)  {
  if(s.empty()) return;
  int top1 = s.top();
  s.pop();
  if(!s.empty()) {
    move_min_to_top(s);
    int top2 = s.top();
    if(top1 > top2) {
      s.pop();
      s.push(top1);
      s.push(top2);   
      return;  
    }       
  }  
  s.push(top1); 
}
 
void sort_stack(stack& s) {
  if(s.empty()) return;
  move_min_to_top(s);
  int top = s.top();
  s.pop();
  sort_stack(s);
  s.push(top);
}

原创文章，转载请注明： 转载自

本文链接地址: