This is c++11. Straightforward sort function for stack using two stacks. While debuging tempStack inside sort() function is filling correctly but sort() function is returning empty object?
I was trying to add std::move() or std::forward() but this is incorrect. General sort() algorithm is correct! This code compiled successfully. Some mistakes with c++11 (move semantics)!
My ideas (not working correctly!): return forward>(tempStack); return move(tempStack);
Code (sort()):
template<typename T>
Stack<T> sort(Stack<T> &input)
{
if(input.isEmpty()) return Stack<T>();
Stack<T> tempStack;
while(!input.isEmpty())
{
T element = input.pop();
while(!tempStack.isEmpty() && tempStack.peek() > element) input.push(tempStack.pop());
tempStack.push(move(element));
}
return tempStack;
}
Code (Stack class):
template <typename T>
class Stack
{
public:
Stack() : top(nullptr), stackSize(0)
{}
Stack(Stack &&other) : top(std::move(other.top)), stackSize(std::move(other.stackSize)) {}
~Stack() { while (!isEmpty()) pop(); }
void push(T &&value)
{
auto n = new Node(std::forward<T>(value), top);
top = n;
++stackSize;
}
T &peek()
{
if (!top) throw StackIsEmptyException();
return top->value;
}
T pop()
{
if (!top) throw StackIsEmptyException();
auto value(std::move(top->value));
auto n = top;
top = n->next;
delete n;
--stackSize;
return value;
}
bool isEmpty() const { return !top; }
size_t size() const { return stackSize; }
class StackIsEmptyException
{};
private:
struct Node
{
Node(T &&v, Node *n): value(std::move(v)), next(n)
{}
Node(const T &v, Node *n): value(v), next(n)
{}
T value;
Node *next;
};
Node *top;
size_t stackSize;
};
Code (main()):
Stack<int> s;
s.push(34);;
s.push(3);
s.push(31);
s.push(98);
s.push(92);
s.push(23);
cout << sort(s).peek() << endl;
Aucun commentaire:
Enregistrer un commentaire