a. Write a program to implement multiple stacks ( say n stacks) in a single arra

Question

a. Write a program to implement multiple stacks ( say n stacks) in a single array. Implement ADD(i. X) and DELETE(i) to add X and delete an element from stack i, 1<= i <= n.

b. Modify the program so that STACK_FULL (i) will redistribute all the stacks so that the free space between stacks j and j + 1 is in proportion to the growth of stack j since the last call to STACK_FULL. STACK_FULL (i) should assign at least 1 free location to stack i.

https://www.dropbox.com/s/1fqdy5dtgyzu4z0/Data%20Structures%202017%20-%20Assignment%203-%20B%20Sec.dot?dl=0

https://www.dropbox.com/s/bppr91c35jqrsq9/DS%20Assignment%203.pdf?dl=0

a. Write a program to implement multiple stacks ( say n stacks) in a single array. Implement ADDG. X) and DELETE(j) to add X and delete an element from stack 1, l

Explanation / Answer

A: i have put all the comments to understand the code easily, if not let me know i will help you with more information.

#include<iostream>
#include<climits>
using namespace std;

// k stacks in a single array of size n
class kStacks
{
int *arr; // Array of size n to store actual content to be stored in stacks
int *top; // Array of size k to store indexes of top elements of stacks
int *next; // Array of size n to store next entry in all stacks
  
int n, k;
int free;
public:
//constructor to create k stacks in an array of size n
kStacks(int k, int n);

// A utility function to check if there is space available
bool isFull() { return (free == -1); }

// To Add an item in stack number 'sn' where sn is from 0 to k-1
void Add(int item, int sn);

// To Delete an from stack number 'sn' where sn is from 0 to k-1
int Delete(int sn);

// To check whether stack number 'sn' is empty or not
bool isEmpty(int sn) { return (top[sn] == -1); }
};

//constructor to create k stacks in an array of size n
kStacks::kStacks(int k1, int n1)
{
// Initialize n and k, and allocate memory for all arrays
k = k1, n = n1;
arr = new int[n];
top = new int[k];
next = new int[n];

// Initialize all stacks as empty
for (int i = 0; i < k; i++)
top[i] = -1;

// Initialize all spaces as free
free = 0;
for (int i=0; i<n-1; i++)
next[i] = i+1;
next[n-1] = -1; // -1 is used to indicate end of free list
}

// To Add an item in stack number 'sn' where sn is from 0 to k-1
void kStacks::Add(int item, int sn)
{
// Overflow check
if (isFull())
{
cout << " Stack Overflow ";
return;
}

int i = free; // Store index of first free slot

// Update index of free slot to index of next slot in free list
free = next[i];

// Update next of top and then top for stack number 'sn'
next[i] = top[sn];
top[sn] = i;

// Put the item in array
arr[i] = item;
}

// To Delete an from stack number 'sn' where sn is from 0 to k-1
int kStacks::Delete(int sn)
{
// Underflow check
if (isEmpty(sn))
{
cout << " Stack Underflow ";
return INT_MAX;
}


// Find index of top item in stack number 'sn'
int i = top[sn];

top[sn] = next[i];  

// Attach the previous top to the beginning of free list
next[i] = free;
free = i;

// Return the previous top item
return arr[i];
}

/* Driver program to test twStacks class */
int main()
{
// Let us create 3 stacks in an array of size 10
int k = 3, n = 10;
kStacks ks(k, n);

// Let us put some items in stack number 2
ks.Add(15, 2);
ks.Add(45, 2);

// Let us put some items in stack number 1
ks.Add(17, 1);
ks.Add(49, 1);
ks.Add(39, 1);

// Let us put some items in stack number 0
ks.Add(11, 0);
ks.Add(9, 0);
ks.Add(7, 0);

cout << "Deleted element from stack 2 is " << ks.Delete(2) << endl;
cout << "Deleted element from stack 1 is " << ks.Delete(1) << endl;
cout << "Deleted element from stack 0 is " << ks.Delete(0) << endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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