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.
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);
}
}
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]
techInterview Discussion - Sorting on Stack
More pseudo than anything, but there is code examples and possible solution.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With