Hello, I have a problem that I need help with. I am completely lost in it. This

Question

Hello,

I have a problem that I need help with. I am completely lost in it. This is the question:

One widespread use of stacks is to provide the undo operation, familiar to us from many different
applications. While support for undo can be implemented with an unbounded stack (one that keeps growing and
growing as long as memory permits), many applications provide only limited support for such an undo history. In
other words, the stack is fixed-capacity.
When such a stack is full, and push is invoked, rather than throwing an exception, a more typical approach is to
accept the pushed element at the top, while removing the oldest element from the bottom of the stack to make
room. This is known as “leaking.” Note that this does not mean that the ADT exposes a method to allow removal
from the bottom directly. This is only performed when the stack becomes full.
For this part, you are to give an implementation of such a LeakyStack abstraction, using some array-based
implementation.
Note that you must create a Leaky Stack interface, and then use the C++ : operator to implement that interface
(using public inheritance) with your LeakyArrayStack implementation. See the Interface specified near the end
of the assignment instructions.
Part II
Repeat Part I, but use a singly linked list instead of an array for the actual data storage, and allow for a
maximum capacity specified as a parameter to the constructor.

Explanation / Answer

PROGRAM CODE:

using Arrays

#include <iostream>
using namespace std;

#define CAPACITY 10
class LeakyStack
{
public:
int array[CAPACITY];
int size;
LeakyStack()
{
size = 0;
}
virtual void push(int) = 0;
void pop()
{
if(size > 0)
{
array[size-1] = 0;
size--;
}
}
int getTop()
{
if(size>0)
return array[size-1];
else return -1;
}
void print()
{
cout<<"STACK: [ ";
for(int i=size-1; i>=0; i--)
{
cout<<array[i]<<" ";
}
cout<<"]"<<endl;
}
};

class LeakyStackArray: public LeakyStack
{
public:
LeakyStackArray():LeakyStack(){}
void push(int data)
{
if(size>=CAPACITY)
{
for(int i=0; i<CAPACITY-1; i++)
{
array[i] = array[i+1];
}
array[CAPACITY-1] = data;
}
else
{
array[size] = data;
size++;
}
}
};
int main() {
LeakyStackArray stack1;
for(int i=0; i<10; i++)
{
stack1.push(i+1);
}
stack1.print();
//Push will remove the most botton element, shift all the items and then add the new element to the top
stack1.push(11);
stack1.print();
return 0;
}

OUTPUT:

Using Singly linked list:

#include <iostream>
using namespace std;

class Node
{
   public:
   int data;
   Node *prev;
  
   Node(int v)
   {
       data = v;
       prev = NULL;
   }
};
class LeakyStack
{
   public:
   Node *last;
   int size;
   int Capacity;
   LeakyStack(int capacity)
   {
   Capacity = capacity;
   size = 0;
   last = NULL;
   }
   virtual void push(int) = 0;
   void pop()
   {
       if(size > 0)
       {
           last = last->prev;
           size--;
       }
   }
   int getTop()
   {
       if(size>0)
           return last->data;
       else return -1;
   }
   void print()
   {
       Node *temp = last;
       cout<<"STACK: [ ";
       for(int i=0; i<size; i++)
       {
           cout<<temp->data<<" ";
           temp = temp->prev;
       }
       cout<<"]"<<endl;
   }
};

class LeakyStackArray: public LeakyStack
{
   public:
   LeakyStackArray(int c):LeakyStack(c){}
   void push(int data)
   {
       Node *node = new Node(data);
       node->prev = last;
       last = node;
       size++;
       if(size>Capacity)
       {
           Node *temp = last;
           int i=0;
           while(i<size-1)
           {
               temp = temp->prev;
               i++;
           }
           temp->prev = NULL;
           size--;
       }
   }
};
int main() {
   LeakyStackArray stack1(10);
   for(int i=0; i<10; i++)
   {
       stack1.push(i+1);
   }
   stack1.print();
   //Push will remove the most botton element, shift all the items and then add the new element to the top
   stack1.push(11);
   stack1.print();
   return 0;
}

OUTPUT:

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.