用两个栈实现队列
template<class T>
class CQueue
{
public:
CQueue(){}
int size()
{
return s1.size()+s2.size();
}
bool empty()
{
return size()==0;
}
void push(T val)
{
s1.push(val);
}
void pop()
{
assert(!empty());
if(s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
s2.pop();
}
T top()
{
assert(!empty());
if(!s2.empty())
return s2.top();
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
private:
stack<T>s1;
stack<T>s2;
};
设计包含min的栈
template<class T>
class StackWithMin
{
public:
void push(T val)
{
data.push(val);
if(minData.empty()||minData.top()>val)
minData.push(val);
else
minData.push(minData.top());
}
void pop()
{
assert(!data.empty());
data.pop();
minData.pop();
}
T top()
{
assert(!data.empty());
return data.top();
}
T min()
{
assert(!minData.empty());
return minData.top();
}
private:
stack<T>data; //栈数据成员
stack<T>minData; //最小的元素
};
写一个算法将栈的元素升序排列。栈的实现未知，算法只能借助栈完成可使用的函数包括有push、pop、top、empty
template<typename T>
stack<T> sort(stack<T>s)
{
stack<T>r;
while(!s.empty())
{
int tmp=s.top();
s.pop();
while(!r.empty()&&r.top()>tmp)
{
s.push(r.top());
r.pop();
}
r.push(tmp);
}
}