广州建网站藤虎,机械加工网瓦房北方机床附件厂,公司简介样本,襄阳seo费用问题描述#xff1a;
栈排序。 编写程序#xff0c;对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据#xff0c;但不得将元素复制到别的数据结构#xff08;如数组#xff09;中。该栈支持如下操作#xff1a;push、pop、peek 和 isEmpty。当栈…问题描述
栈排序。 编写程序对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据但不得将元素复制到别的数据结构如数组中。该栈支持如下操作push、pop、peek 和 isEmpty。当栈为空时peek 返回 -1。
示例1: 输入
[SortedStack, push, push, peek, pop, peek]
[[], [1], [2], [], [], []]输出
[null,null,null,1,null,2]示例2: 输入
[SortedStack, pop, pop, push, pop, isEmpty]
[[], [], [], [1], [], []]输出
[null,null,null,null,null,true]说明:
栈中的元素数目在[0, 5000]范围内。
解决方案
1、分析题目用两个栈主栈辅助栈实现排序算法返回主栈
2、栈顶元素比较主栈 始终为较大的值辅助栈 始终为小值
注辅助栈中始终为降序出栈先大后小
3、循环判断如果 主栈 中栈顶元素 待输入值val该元素归入 辅助栈里。
例132
11-- 主栈
2131--辅助栈3--主栈1--主栈
312同上结果主栈3辅助栈1 第二次判断32 2 直接放入 主栈合并辅助栈即主栈123
函数代码 class SortedStack {
public:stackint num;stackint tmp;SortedStack() {}void push(int val) {while(!num.empty() num.top()val){tmp.push(num.top());num.pop();}num.push(val);while(!tmp.empty()){num.push(tmp.top());tmp.pop();}}void pop() {if(!num.empty()) num.pop();}int peek() {if(num.empty()) return -1;return num.top();}bool isEmpty() {return num.empty();}
};
