Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to sort a stack using only Push, Pop, Top, 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.

like image 934
AJ. Avatar asked Jan 30 '10 17:01

AJ.


3 Answers

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);
    }
}
like image 175
SiLent SoNG Avatar answered Jan 12 '23 01:01

SiLent SoNG


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]
like image 27
DigitalRoss Avatar answered Jan 12 '23 01:01

DigitalRoss


techInterview Discussion - Sorting on Stack

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

like image 26
Anthony Forloney Avatar answered Jan 12 '23 01:01

Anthony Forloney