Question

1. Consider an ADT with the same operators as a stack (push(), pop(), size(), empty()), except that the pop() operator returns the largest element rather than the element most recently pushed. For this to make sense, the objects on the stack must be totally ordered (e.g. numbers). Describe array and linked list implementations of the ADT. Your implementations should be as time and space efficient as you can manage. Give the running times for the CRUD operators.

Answer 1

Following solution are in c++.

Array based solution:-

'stack' array is used to store maximum element obtained so far. 'SIZE' denotes the maximum size of the stack. 'stack_itr' is used to iterate through the stack in LIFO(Last In First Out) order. Whenever any new element is added to the stack then it is compared with previous element is that exist and maximum among these two are inserted in the stack array. Also when we pop an element from the stack then it should n ot be considered afterwards.

#include <iostream>
using namespace std;
const int SIZE=5;
int stack[SIZE],stack_itr=0;

bool isEmpty()
{
   return (stack_itr==0);
}

int stack_size()
{
   return stack_itr;
}

void push(int x)
{
   if(stack_itr>=SIZE)
   {
       cout<<"Stack Overflow\n";
   }
   else
   {
       if(stack_itr==0)
           stack[stack_itr]=x;
       else
           stack[stack_itr]=max(stack[stack_itr-1],x);
       stack_itr++;
   }
}
void pop()
{
   // Before calling pop we should check whether stack is empty or not
   if(!isEmpty())
   {
       int x= stack[stack_itr-1];
       stack_itr--;
       cout<< x<<" ";
   }
   else
   {
       cout<<"Stack Underflow\n";
   }
}

int main() {
   push(1);
   push(3);
   push(2);
  
   //Size of the stack
   cout<<stack_size()<<"\n";
  
   // Largest element are printed in reverse order :
   pop();
   pop();
   push(5);
   pop();
   return 0;
}

Time complexity:

push(), pop(), stack_size() and  isEmpty() = O(1)

Space Complexity: = O(n)

Linked list based Implementation:

In this case, we for push operation we have to traverse the entire linked list as we only know the head pointer in linked list. Also when we reach the last node then we are inserting the maximum of current element and previous element.

For pop operation also we have to traverse the entire linked list and then print the last element and free the allocated memory.

#include <iostream>
using namespace std;
const int SIZE=5;
struct node
{
int data;
struct node *next;
};
int stack_itr=0;

bool isEmpty()
{
   return (stack_itr==0);
}

int stack_size()
{
   return stack_itr;
}

node * newNode(int x)
{
   node *tmp=new node();
   tmp->data=x;
   tmp->next=NULL;
   return tmp;
}
void push(int x,node **head)
{
   if(stack_itr>=SIZE)
   {
       cout<<"Stack Overflow\n";
   }
   else
   {
       if(stack_itr==0)
       {
           node *tmp=newNode(x);
           *head=tmp;
       }
       else
       {
           node *tmp=*head;
           while(tmp->next!=NULL)
               tmp=tmp->next;
           // we have store largest number upto that element
           tmp->next=newNode(max(x,tmp->data));
       }
       stack_itr++;
   }
}
void pop(node *head)
{
   // Before calling pop we should check whether stack is empty or not
   if(!isEmpty())
   {
       node *tmp=head;
       // Here there can be single node so checking tmp->next also
       while(tmp->next!=NULL && tmp->next->next!=NULL)
       {
           tmp=tmp->next;
       }
       int x;
       if(tmp->next==NULL)
       {
           x=tmp->data;
           free(tmp);
           head=NULL;
       }
       else
       {
           x=tmp->next->data;
           node *tmp2=tmp->next;
           tmp->next=NULL;
           free(tmp2);
       }
       stack_itr--;
       cout<< x<<" ";
   }
   else
   {
       cout<<"Stack Underflow\n";
   }
}

int main() {
   node * head =NULL;
  
   push(1,&head);
   push(3,&head);
   push(2,&head);
  
   //Size of the stack
   cout<<stack_size()<<"\n";
  
   // Largest element are printed in reverse order :
   pop(head);
   pop(head);
   push(5,&head);
   pop(head);
   return 0;
}

Time complexity:

push() and  pop() = O(n)

stack_size() and isEmpty() = O(1)

Space Complexity: = O(n)