Question

Stack and Queue

In this question, you will implement a modified version of stackArray class. This modified class requires you to:

• Implement two stacks using a single array. One stack uses the beginning of the array and the other uses the other end.

• Your code should allowing pushes to and pops from each stack by passing the 0 and 1 to any function to identify the needed stack.

• All stack functions should be be applied on both stack. For example, print(0) will print the content of the first stack while print(1) will print the other stack.

• Your stack should contain the following functions at least: isEmpty, isFull, push, pop, top, clear, print and getsize.

• The capacity of the array may be grow depending on the sum of number of objects stored in the two stacks.

• Moreover, the capacity maybe reduced to the half of the current capacity if the number of objects remaining in the two stacks (after each pop) is 1/4 the capacity of the array or less. The capacity of the array may not be reduced below the initially specified capacity.

using C++

this is the stack array code

#define DEFAULT_CAPACITY 10000
template <class T> class StackArray{
public:
   StackArray(int capacity = DEFAULT_CAPACITY);
   ~StackArray();

   void push(T& val);
   T pop(void);
   T top(void);
   bool isEmpty(void);
   bool isFull(void);
   void clear(void);

private:
   T* data;
   int capacity, last;
};

template <class T>
StackArray<T>::StackArray(int cap){
   capacity = cap;
   data = new T[capacity];
   last = -1;
}

template <class T>
StackArray<T>::~StackArray(void){
   delete [] data;
}

template <class T>
void StackArray<T>::push(T& el)
{
   if(isFull() )
   {
       printf("\n Can't push into a full stack!");
       return;
   }
   last++;
   data[last] = el;
}

template <class T>
T StackArray<T>::pop()
{
   if(isEmpty() )
   {
       printf("\n Can't pop from an empty stack!");
       return -1;
   }
   T el = data[last];
   last--;
   return el;
}

template <class T>
T StackArray<T>::top()
{
   if(!isEmpty() )
   {
       printf("\n Stack is empty!");
       return -1;
   }
   return data[last];
}

template <class T>
bool StackArray<T>::isEmpty(void)
{
   return last == -1;
}

template <class T>
bool StackArray<T>::isFull(void)
{
   return last+1 == capacity;
}

template <class T>
void StackArray<T>::clear(void)
{
   last = -1;
}

Answer 1

Summary :

Provided Notes , Code and sample output with testing push and pop with resizing (reducing) the size of internal structures.

Notes :

In order to store both stack info in same array , utilized last[] which store the index of stack[0] in last[0] and stack[1] in last[1] and thus most of the operations are automatic in terms pushing and poping and other operations.

Only isEmpty() requires special handing in both cases which involves comparing the respective elements .

Resizing : Here upon resizing store the old data and depending on reducing or increasing the size create the array and copy the old data and only require to offset the last[1] pointer as the last[0] remains same in resizing .

added printInfo() funciton to print the stats of the current state of both the stacks .

As part of the test program created a intial stack of size 6 and insert 24 elements into the stack with index module on stack numbe so that equal number of elements are pushed in both the stacks ( 0 & 1 ) . and similarly pop() 24 times on the stack .   this allows to test increasing the size and reducing the size twice that initial size .

It should work with distinct sizes of stack 0 & 1 which requires resize .

################ Code ######################

#ifndef DSTACK_H_
#define DSTACK_H_
#define DEFAULT_CAPACITY 10000

template <class T>
class StackArray{
public:
   StackArray(int capacity = DEFAULT_CAPACITY);
   ~StackArray();

   void push(T& val, int);
   T pop(int);
   T top(int);
   bool isEmpty(int);
   bool isFull(int);
   void clear(int);
   void printInfo();


private:
   void resize();
   T* data;
   // capacity[0] store the initial capacity
   // capacity[1] store current capacity
   int capacity[2];
   // last[0] store the stack[0] last item
   // last[1] store the stack[1] last item
   int last[2];
   int op[2];
};


#endif /* DSTACK_H_ */

#include <iostream>

#include "dStack.h"

using namespace std;


template <class T>
StackArray<T>::StackArray(int cap){
   capacity[0] = cap;
   capacity[1] = cap;
   data = new T[capacity[1]];
   last[0] = -1;
   last[1] = capacity[1];
   op[0] = 1;
   op[1] = -1;
}

template <class T>
StackArray<T>::~StackArray(void){
   delete [] data;
}

// THis method pushes the given element to the top of stack
template <class T>
void StackArray<T>::push(T& el,int stack_index)
{
   if(isFull(stack_index) )
   {
       resize();
   }
   // Chance the last index based on given index
   // ie for 0 , it should increment and for 1 it should decrement
   last[stack_index] = last[stack_index] + op[stack_index];
   data[last[stack_index]] = el;
}

// This method returns the top of the stack if its not empty
// further it resizes the stack if the occupancy is 1/4 of current capacity.
template <class T>
T StackArray<T>::pop(int stack_index)
{
   if(isEmpty(stack_index) )
   {
       printf("\n Can't pop from an empty stack!");
       return -1;
   }
   T el = data[last[stack_index]];
   last[stack_index] = last[stack_index] + op[ ( stack_index+1)%2] ;
   int current_occupancy = last[0] +1+ ( capacity[1] - last[1]) ;

   if ( current_occupancy <= ( capacity[1]/4 ))
   {
     //     cout << " Time to reduce \n";
     resize();
   }

   return el;
}


template <class T>
T StackArray<T>::top(int stack_index)
{
  // return the top of the stack for respective stack index
  if(!isEmpty(stack_index) )
   {
       printf("\n Stack is empty!");
       return -1;
   }
   return data[last[stack_index]];
}

// If stack index of respect stacks are at bottom then its empty
template <class T>
bool StackArray<T>::isEmpty(int stack_index)
{
  if ( stack_index == 0 )
   return last[stack_index] == -1;
  else
    return last[stack_index] == capacity[1];
}


template <class T>
bool StackArray<T>::isFull(int stack_index)
{
 // if last index of both stacks are adjacent then stack is full
  return last[0] + 1 == last[1];

}


template <class T>
void StackArray<T>::clear(int stack_index)
{
  if ( stack_index == 0 )
   last[stack_index] = -1;
  else
    last[stack_index] = capacity[1];

}


// The same resize method is used for increasing the size as welll as reducing the capacity of the Array
// which holds two stacks.

template <class T>
void StackArray<T>::resize()
{
  //cout << " Prior to resize : ";
  //printInfo();
  int prev_capacity = capacity[1];
  T* old_data = data ;

  if ( isFull(1) )
  {
    //cout << " Prior to resize : ";
    //printInfo();
    int prev_capacity = capacity[1];
    capacity[1] = prev_capacity * 2 ;

    data = new T[capacity[1]];

    for(int i=0 ; i <= last[0] ; i++)
    {
      data[i] = old_data[i] ;
    }

    for(int i= 0 ; i <  (prev_capacity - last[1])  ; i++)
    {
      data[capacity[1] -1 - i] = old_data[prev_capacity -1 -i ] ;
    }

    last[1] = capacity[1] - ( prev_capacity - last[1]);
    //cout << " Resize Done \n";
    //printInfo();
    delete[] old_data;
  } else {
    if ( prev_capacity/2 >= capacity[0])
    {
         capacity[1] = prev_capacity/2 ;

         data = new T[capacity[1]];

         for(int i=0 ; i <= last[0] ; i++)
         {
           data[i] = old_data[i] ;
         }

         for(int i= 0 ; i <  (prev_capacity - last[1])  ; i++)
            {
              data[capacity[1] -1 - i] = old_data[prev_capacity -1 -i ] ;
            }

        last[1] = capacity[1] - ( prev_capacity - last[1]);
       // cout << " Resize Done \n";
            //printInfo();
            delete[] old_data;




    }
  }

}


// THis method prints the Internal stack info such as the last index of both
// occupancy , the current size , etc.
template <class T>
void StackArray<T>::printInfo()
{

  cout << "\n###################################################################\n";
  cout << " Current Capacity : " << capacity[1] << "\n";
  cout << " Occupancy "  << ( last[0] +1 + ( capacity[1] - last[1])) << " \n";
  cout << " Stack[0] Last :  " << last[0] << " \n Stack[1] Last : " << last[1] << "\n";

  cout << "\n Stack[0] -> Empty - " << this->isEmpty(0) << "\n";
  cout << " Stack[0] -> Full - " << this->isFull(0) << "\n";

  cout << " Contents of Stack[0] - > " ;
  for( int i=0 ; i <= last[0]; i++)
    cout << data[i]   << " " ;


  cout << "\n\n Stack[1] -> Empty - " << this->isEmpty(1) << "\n";
  cout << " Stack[1] -> Full - " << this->isFull(1) << "\n";

  cout << " Contents of Stack[1] - > " ;
    for( int i = capacity[1] -1  ; i >= last[1]; i--)
      cout << data[i]   << " " ;

    cout << "\n###################################################################\n";
}



int main()
{

  // Initialize the stack with 6 size
   StackArray<int> st(6);


   // Insert 24 elements which should double the size from 6 to 12 to 24
   for ( int i=0 ; i < 24 ; i++ )
   {
       st.push( i, i%2 );
   }

   // Print Stack info.
   st.printInfo();


   // Now Pop all the elements and at the end the size should be initial size which is 6
   cout << " Popping - > ";
   for ( int i=0 ; i < 24 ; i++ )
   {
     cout << " ( Stack[" << (i%2 ) << "] -> " <<  st.pop( i%2 ) << " ) , ";
   }

   // Print Stack info.
   st.printInfo();
}

#################### Output ####################