如何使用Push,Pop,Top,IsEmpty,IsFull对堆栈进行排序？

Question

给定一个栈S,需要重新梳理只使用堆栈Push,Pop,Top,IsEmpty,IsFull.

寻找最简单的解决方案.

编辑:删除到位条件.无法使用其他堆栈或队列.

Answer 1

对于这个问题,我们可以考虑使用系统堆栈吗？进行几次递归调用.

public static void sort(Stack<Integer> s) {
    if (!s.isEmpty()) {
        Integer t = s.pop();
        sort(s);
        insert(t, s);
    }
}

private static void insert(Integer x, Stack<Integer> s) {
    if (s.isEmpty()) {
        s.push(x);
        return;
    }

    if (x < s.peek()) {
        Integer t = s.pop();
        insert(x, s);
        s.push(t);
    } else {
        s.push(x);
    }
}

Answer 2

可以办到...

好的:排序,ahem,"就地"只有列出的操作,不需要Top()或IsFull()或除调用帧之外的其他堆栈或数据结构.(据推测,作业问题的重点是要求递归解决方案.)

红宝石

@a = [3, 2, 1, 6, 5, 4]

class Array
  def empty?
    return size == 0
  end
end

def sort e
  if @a.empty?
    @a.push e
    return
  end
  t = @a.pop
  if e > t
    @a.push(t).push(e)
    return
  end
  sort e
  @a.push t
end

def resort
  return if @a.empty?
  t = @a.pop
  resort
  sort t
end

p ['first ', @a]
resort
p ['final ', @a]