如何栈只用PUSH​​，POP，顶部，为IsEmpty，IsFull排序？ [英] How to sort a stack using only Push, Pop, Top, IsEmpty, IsFull?

问题描述

由于一摞S，需要仅使用按，流行堆排序，顶，的IsEmpty ， IsFull 。

Given a stack S, need to sort the stack using only Push, Pop, Top, IsEmpty, IsFull.

寻找最简单的解决方案。

Looking for most simple solution.

编辑：删除到位情况。不能使用另一个堆栈或队列。

Edited: Removed in place condition. Can't use another stack or queue.

推荐答案

确定：排序，啊哈，就地，只有上市老年退休金计划，也没必要顶（）或IsFull（）或大于调用帧等另一个堆栈或数据结构。 （presumably的<击>作业的整点问题是需要一个递归解决方案。）

It can be done...

---

Ok: sorted, ahem, "in-place" with only the listed ops, didn't need Top() or IsFull() or another stack or data structure other than the call frames. (Presumably the whole point of the homework problem was to require a recursive solution.)

@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]

这篇关于如何栈只用PUSH​​，POP，顶部，为IsEmpty，IsFull排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！