Question

Write an implementation of the ADT stack that uses a resizeable array to represent the stack items. Anytime the stack becomes full, double the size of the array. Maintain the stack's top entry at the beginning of the array.

Use c++ to write this code.

Answer 1

#include <iostream>

using namespace std;

/*
* "Stack" class is the implementation of the abstract data type - Stack
* It uses a resizable array to represent the stack elements, anytime
the stack becomes full, the size of the array representing the stack has to be doubled.
* This particular implementation assumes that only positive int are
   inserted into the stack.
*/

/* API interface for the class
1. "Stack" class represents the ADT
2. Attributes:
(a) size_of_stack (stores the current length of the stack[] array.)
(b) num_of_elems_in_stack (stores number of elements in the stack)
3. Methods:
(a) push(elem)
(b) pop()
(c) return_top()
(d) return_status_of_stack()
*/

class Stack {
   public:
       // class atributes
       int size_of_stack;
       int num_of_elems_in_stack;
       int* stack_arr = NULL;

       Stack(int top_elem){ // this is the constructor that initializes the stack
           stack_arr = new int[1]; // Allocate 1 int and save ptr in stack_arr.
           stack_arr[0] = top_elem;
           size_of_stack = 1;
           num_of_elems_in_stack = 1;
       }

       // this method is used as a helper function to move contents within the stack array
       void shift(int left_or_right){
           // left_or_right = 0, i.e. shift left
           if (left_or_right==0)
           {
               for (int i = num_of_elems_in_stack-1; i >0 ; --i)
               {
                   stack_arr[i-1] = stack_arr[i];
               }
               num_of_elems_in_stack-=1;
           }
           // left_or_right = 1, i.e. shift right
           else
           {
               for (int i = 0; i < num_of_elems_in_stack; ++i)
               {
                   stack_arr[i+1] = stack_arr[i];
               }
               num_of_elems_in_stack+=1;
           }
       }

       // This method pushes elements on to the stack by appropriately checking the
       // end conditions
       void push(int elem){
           // Case 1: size of stack = num of elems in stack
           // => insertion will cause overflow. So, need to resize array
           if (size_of_stack == num_of_elems_in_stack)
           {
               int* temp = stack_arr;
               stack_arr = new int[2*num_of_elems_in_stack];

               stack_arr[0] = elem;
               for (int i = 1; i < num_of_elems_in_stack+1; ++i)
               {
                   stack_arr[i] = temp[i];
               }

               delete [] temp; // free memory pointed to by temp;
               num_of_elems_in_stack+=1;
               size_of_stack = 2*num_of_elems_in_stack;
           }  

           // Case 2: size of stack > num of elems in stack
           // => insertion will not cause overflow.
           else
           {
               shift(1); // shift right
               stack_arr[0] = elem;
           }

       }

       // This method pops elements from the stack by appropriately checking the
       // end conditions
       int pop(){
           if (num_of_elems_in_stack==0)
           {
               cout<<"Underflow Error"<<endl;
               return -1;
           }
           else{
               int top = stack_arr[0];
               shift(0);// pop the element of the stack
               return top;
           }
       }

       // this method returns top of the stack(if stack not empty)
       int return_top(){
           if (num_of_elems_in_stack==0)
           {
               cout<<"No elements in the stack"<<endl;
               return -1;
           }
           else
               return stack_arr[0];
       }

       int return_status_of_stack(){
           if (num_of_elems_in_stack!=0)
               cout<<"Top of stack: "<<stack_arr[0]<<endl;

           cout<<"Size of the stack: "<<size_of_stack<<endl;
           cout<<"Number of elements in stack: "<<num_of_elems_in_stack<<endl;
       }
};

int main(int argc, char const *argv[])
{
   cout<<endl;
   cout<<"Checking stack init"<<endl;
   Stack s(100);
   s.return_status_of_stack();

   // testing push method
   cout<<endl;
   cout<<"Check push method: "<<"elems inserted 230,50,70"<<endl;
   s.push(230);
   s.push(50);
   s.push(70);
   s.return_status_of_stack();

   // testing pop method
   cout<<endl;
   cout<<"Checking popped element"<<endl;
   cout<<"Popped element: "<<s.pop()<<endl;
   s.return_status_of_stack();

   cout<<endl;
   cout<<"End of testing"<<endl;
   return 0;
}