栈内元素排序问题
昨天笔试某知名IT企业，最后面一道编程题，题目如下：
完成函数StackSort,传入stack,返回排序后的stack，可以使用的数据结构只有stack,方法限于pop() top() push() isempty() is full(),先给出算法思想，然后完成代码。
…………………………………………………………………………………………………………
昨天我再考场上最后时间不够，就用两个辅助栈，每次找出最大元素入栈，然后再找次大元素，依次类推，没来得及写代码，不知道有更好的思路没有，只能用栈，我开始想直接把数据读入数组，然后排序，然后入栈，此方法不行。
小兰·魇魅
9 years, 1 month ago
Answers
可以用快排啊
Stack Qsort(Stack stk)
{
Stack result = new Stack();
if (stk.isEmpty()) {
return result;
}
Elem spliter = stk.top();
stk.pop();
Stack s1 = new Stack(), s2 = new Stack();
while (!stk.isEmpty()) {
Elem e = stk.top();
stk.pop();
if (e < spliter) {
s1.push(e);
} else {
s2.push(e);
}
}
s1 = Qsort(s1);
s2 = Qsort(s2);
Stack s1Rev = new Stack(), s2Rev = new Stack();
while (!s1.isEmpty()) {
Elem e = s1.top();
s1.pop();
s1Rev.push(e);
}
while (!s2.isEmpty()) {
Elem e = s2.top();
s2.pop();
s2Rev.push(e);
}
while (!s1Rev.isEmpty()) {
Elem e = s1Rev.top();
s1Rev.pop();
result.push(e);
}
result.push(spliter);
while (!s2Rev.isEmpty()) {
Elem e = s2Rev.top();
s2Rev.pop();
result.push(e);
}
return result;
}
qscgul
answered 9 years, 1 month ago
