首页 > 代码库 > 014写程序将一个栈按升序排序,对这个栈是如何实现的,你不应该做任何特殊的假设(keep it up)
014写程序将一个栈按升序排序,对这个栈是如何实现的,你不应该做任何特殊的假设(keep it up)
写程序将一个栈按升序排序。对这个栈是如何实现的,你不应该做任何特殊的假设。
程序中能用到的栈操作有:push | pop |isEmpty
最容易想到的就是优先队列来做此题,容易实现。
附加栈来实现:
第二种算法有个极端的测试列子:如果原来栈的数据底部到顶部是从小到大的,例如:
1 2 3 4 5 6 7
那么Tmp每次push一个不同的数就要清空栈中的所有数据,比如某时刻
vStk:1 2 3 4 5
Tmp:6 7
当Tmp要push 5的时候就要清空6 7,然后在push5,这时候vStk栈的数据增加:
vStk: 1 2 3 4 7 6
Tmp: 5
程序中能用到的栈操作有:push | pop |isEmpty
最容易想到的就是优先队列来做此题,容易实现。
另外我们可以再用一个栈来实现栈的升序排列。
优先队列:
//优先队列来实现 void sortStack(std::stack<int>& vStk) { std::priority_queue<int, std::vector<int>, std::greater<int>> Queue; while (!vStk.empty()) { Queue.push(vStk.top()); vStk.pop(); } while (!Queue.empty()) { vStk.push(Queue.top()); Queue.pop(); } }
附加栈来实现:
//附加一个栈来实现 void sortStack_(std::stack<int>& vStk) { std::stack<int> Tmp; while (!vStk.empty()) { int Top = vStk.top(); vStk.pop(); while (!Tmp.top() && Top < Tmp.top()) { vStk.push(Tmp.top()); Tmp.pop(); } Tmp.push(Top); } }
第二种算法有个极端的测试列子:如果原来栈的数据底部到顶部是从小到大的,例如:
1 2 3 4 5 6 7
那么Tmp每次push一个不同的数就要清空栈中的所有数据,比如某时刻
vStk:1 2 3 4 5
Tmp:6 7
当Tmp要push 5的时候就要清空6 7,然后在push5,这时候vStk栈的数据增加:
vStk: 1 2 3 4 7 6
Tmp: 5
014写程序将一个栈按升序排序,对这个栈是如何实现的,你不应该做任何特殊的假设(keep it up)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。