网站备案登记表,广东网站建设网站,网站首页被k咋办,学电商比较好的网站有哪些1. 题目
栈排序。 编写程序#xff0c;对栈进行排序使最小元素位于栈顶。 最多只能使用一个其他的临时栈存放数据#xff0c;但不得将元素复制到别的数据结构#xff08;如数组#xff09;中。 该栈支持如下操作#xff1a;push、pop、peek 和 isEmpty。当栈为空时#…1. 题目
栈排序。 编写程序对栈进行排序使最小元素位于栈顶。 最多只能使用一个其他的临时栈存放数据但不得将元素复制到别的数据结构如数组中。 该栈支持如下操作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]范围内。2. 解题
用两个栈来回倒数据保证其中一个为空倒的过程中找到最小的放在非空的栈的顶端
class SortedStack {stackint s;stackint temp;int nextMin;
public:SortedStack() {}void push(int val) {if(isEmpty())s.push(val);else if(temp.empty()){if(s.top() val)//栈顶小swap(val,s.top());//把栈顶变成大的s.push(val);//在把原来的小栈顶放回}else //s.empty(){if(temp.top() val)swap(val,temp.top());temp.push(val);}}void pop() {if(isEmpty())return;if(temp.empty()){s.pop();//最小值popwhile(!s.empty())//倒数据到temp{nextMin s.top();s.pop();if(!temp.empty() nextMin temp.top())swap(nextMin, temp.top());temp.push(nextMin);}}else //s.empty(){temp.pop();//最小值while(!temp.empty())//倒数据到s{nextMin temp.top();temp.pop();if(!s.empty() nextMin s.top())swap(nextMin, s.top());s.push(nextMin);}}}int peek() {if(isEmpty())return -1;if(temp.empty())return s.top();else //s.empty()return temp.top();}bool isEmpty() {return s.empty()temp.empty();}
};
