How to sort a stack using only Push, Pop, Top, IsEmpty, IsFull?

Question

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.

Answer 1

You can't. You can't reorder the contents of a stack without removing elements, by definition. Also push and pop aren't in-place operations, so basically you're asking to sort a stack with Top, IsEmpty and IsFull. IsEmpty = !IsFull. So you're asking to sort a stack with Top and IsEmpty.

Answer 2

techInterview Discussion - Sorting on Stack

More pseudo than anything, but there is code examples and possible solution.

Answer 3

Its not possible.

That happens because you cant iterate through the stack, because it has to be in place (you could if you would use extra memory). So if you cant iterate through the stack you cant even compare two elements of the stack. A sort without comparing would need extra memory, so that cant be used either.

Also im sure its not homework, because i dont think a teacher would give you a problem that cant be solved.

If you really have to do it only with stacks, just use 1-2 extra temporary stacks (i think 2 are needed, but not 100% sure) and do it.

Answer 4

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.)

Ruby

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

Answer 5

What temporary data structures can you use? With push and pop, and no temporary storage for n elements, accessing data near the bottom of the stack would be impossible without storing the rest -somewhere-.

If top (equiv to {x=pop();push(x);return x}) was replaced with shift, it would be perfectly doable - the stack would change into fifo (shift+push; pop would fall into disuse) and it would allow for an easy bubblesort on currently available elements.

Answer 6

For this problem, can we consider using system stack? Make several recursive calls.

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 7

To bad you couldn't have two other stacks, then you could have played the Towers of Hanoi in O(n) space.