Question

Given an array-based stack of integers, sort it largest to smallest using recursion. Do NOT use any loop constructs such as while, for and so on. Only use the following stack ADT functions in the recursion:

IsEmpty

Push

Pop

Top (note: doesn’t remove anything from the stack).

Your program should read 10 integers into a stack from a file named input.txt (outputting them to the screen first) then implement the recursions. Use stacks only, no queues. The program should then output the stack. The output results should clearly be displayed in descending order if the stack was properly sorted in ascending order.

StackType.cpp that needs to be used, edit as needed but it stills need to be templated:

// The class definition for StackType using templates 
class FullStack
// Exception class thrown by Push when stack is full.
{};

class EmptyStack
// Exception class thrown by Pop and Top when stack is emtpy.
{};


template<class ItemType>          
class StackType
{
public:

    StackType();
    // Class constructor.
    StackType(int max);
    // Parameterized constructor.
    ~StackType();
    // Destructor
    bool IsFull() const;
    // Function: Determines whether the stack is full.
    // Pre:  Stack has been initialized.
    // Post: Function value = (stack is full)
    bool IsEmpty() const;
    // Function: Determines whether the stack is empty.
    // Pre:  Stack has been initialized.
    // Post: Function value = (stack is empty)
    void Push(ItemType item);
    // Function: Adds newItem to the top of the stack.
    // Pre:  Stack has been initialized.
    // Post: If (stack is full), FullStack exception is thrown;
    //       otherwise, newItem is at the top of the stack.
    void Pop();
    // Function: Removes top item from the stack.
    // Pre:  Stack has been initialized.
    // Post: If (stack is empty), EmptyStack exception is thrown;
    //       otherwise, top element has been removed from stack.
    ItemType Top();
    // Function: Returns a copy of top item on the stack.
    // Pre:  Stack has been initialized.
    // Post: If (stack is empty), EmptyStack exception is thrown;
    //       otherwise, top element has been removed from stack.
           
private:
    int top;
    int maxStack;
    ItemType*  items;           
};

// The function definitions for class StackType.

template<class ItemType>
StackType<ItemType>::StackType(int max)
{
  maxStack = max;
  top = -1;
  items = new ItemType[maxStack];
}

template<class ItemType>
StackType<ItemType>::StackType()
{
  maxStack = 500;
  top = -1;
  items = new ItemType[maxStack];
}

template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
  return (top == -1);
}

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
  return (top == maxStack-1);
}

template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem) 
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

template<class ItemType>
void StackType<ItemType>::Pop()
{
  if( IsEmpty() )
    throw EmptyStack();
  top--;
}

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
  if (IsEmpty())
    throw EmptyStack();
  return items[top];
}    

template<class ItemType>
StackType<ItemType>::~StackType()
{
  delete [] items;
}

Answer 1

Below code sorts the stack recursively:-

void sortedInsert(int x)
{
if (isEmpty() || x > Top())
{
Push(x);
return;
}
  
int tmp = Top();
Pop();
sortedInsert(x);
Push(tmp);
}
  
void sortStack()
{
if (!isEmpty())
{
int x = Top();
Pop();
sortStack();
sortedInsert(x);
}
}