Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this.Implement

9/7/2015
/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Imagine a (literal) stack of plates.
If the stack gets too high, it might topple.
Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. 
Implement a data structure SetOfStacks that mimics this.
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
 
By: Hamed Kiani (Sep. 7, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class SetOfStacks{
private:
        int _numOfStk;   // number of stacks
        int _thOfStk;    // threshold of stacks
        int _curStk;     // index of current stack
        int **_stacks;       // two-dim array to keep stacks elements
        int *_elmts; // number of elements in each stack

public:
        SetOfStacks(int n, int t);
        ~SetOfStacks();
        void push(int n);  // push the element n on the stack
        int pop();                        // pop operation
        int pop(int k);            // pop operation from stack k
        bool isFull(int k);        // is stack k full?
        bool isFull();            // is the stack full?
        bool isEmpty(int k);//        is the stack k empty?
        bool isEmpty();           // is the stack empty?
        void printAll();  // print all elements
        void printK(int k);        // print elemets of stack k
};

////////////////////////////////////////////////////////////       
SetOfStacks::SetOfStacks(int n, int t)
{
        _numOfStk = n;
        _thOfStk  = t;
        _curStk   = 0;

        // _elmts = new int[_numOfStk];
        _elmts = (int*) malloc(_numOfStk * sizeof(int));
        for(int i = 0; i < _numOfStk; i++)
                _elmts[i] = -1;  // all are empty


        _stacks = (int **) malloc(_numOfStk * sizeof(int *));
        for (int i = 0; i<_numOfStk; i++)
                _stacks[i] = (int *) malloc(_thOfStk * sizeof(int));
        cout << n << " stacks are created, windex 0,..., " << n-1 << endl;
        cout << " the threshold for each stack is " << t << " elements " << endl;
}

////////////////////////////////////////////////////////////
SetOfStacks::~SetOfStacks()
{
        free(_elmts);
        free(_stacks);
        cout << " stacks are deleted!" << endl;
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull(int k)
{
        return (_elmts[k] == _thOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull()
{
        return isFull(_numOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty(int k)
{
        return (_elmts[k] == -1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty()
{
        return isEmpty(0);
}

////////////////////////////////////////////////////////////
void SetOfStacks::push(int n)
{
        if (isFull())
        {
                cout << "stack overflow! cann't push " << n << " value! " << endl;
                return;
        }       
        if (_elmts[_curStk] == _thOfStk - 1)
                _curStk++;
        cout << "value " << n << " pushed on stack " << _curStk <<  endl;
        _elmts[_curStk]++;
        _stacks[_curStk][_elmts[_curStk]] = n;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop()
{
        if (isEmpty())
        {
                cout << "stack under flow! " << endl;
                return INT_MAX;
        }
        int i = _stacks[_curStk][_elmts[_curStk]];
        cout << "value " << i << " is popped from stack " << _curStk << endl;
        _elmts[_curStk]--;  
        if ((_elmts[_curStk] == -1) & (_curStk > 0))
                _curStk--;
        
        return i;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop(int k)
{
        if (isEmpty(k))
        {
                cout << "stack under flow!" << endl;
                return INT_MAX;
        }

        if ((k > _numOfStk-1) | (k < 0))
        {
                cout << " stack index is out of range! " << endl;
                return INT_MAX;
        }

        
        int i = _stacks[k][_elmts[k]];
        cout << "value " << i << " is popped from stack " << k << endl;
        _elmts[k]--;
        if ((_elmts[k] == -1) & (k > 0) & (k == _curStk))
                _curStk--;
        return i;
}

////////////////////////////////////////////////////////////

void SetOfStacks::printAll()
{
        cout << "print all the stacks:" << endl;
        for (int i = 0; i < _numOfStk; i++)
        {
                if (isEmpty(i))
                        cout << "stack " << i <<  " is empty " << endl;
                else
                {
                        for (int j = 0; j <= _elmts[i]  ; j++)
                                cout << _stacks[i][j] << " " ;
                        cout << endl;
                }
        }
}

////////////////////////////////////////////////////////////
void SetOfStacks::printK(int k)
{
        if (k > _numOfStk-1)
        {
                cout << "index is more than the stack size!" << endl;
                return;
        }

        if (k < 0)
        {
                cout << "index is less than the stack size!" << endl;
                return;
        }

        if (isEmpty(k))
                        {
                                cout << "stack " << k <<  " is empty " << endl;
                                return;
        }
                else
                {
                        for (int j = 0; j <= _elmts[k]  ; j++)
                                cout << _stacks[k][j] << " " ;
                        cout << endl;
                }
}

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        int n = 2;
        int t = 3;
        SetOfStacks stacks(n,t);
        
        stacks.push(1);
        stacks.push(2);
         stacks.push(3);
        
        stacks.push(10);
        stacks.push(20);
        stacks.push(30);

        stacks.push(100);
        stacks.push(200);
        stacks.push(300);

        stacks.push(1000);
        stacks.push(2000);
        stacks.push(3000);
        stacks.push(3001);
        stacks.push(3002);       

        stacks.printK(0);
        stacks.printK(1);
        stacks.printK(2);
        stacks.printK(3);
        stacks.printK(4);

        stacks.printAll();

        stacks.pop();
        stacks.pop();
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(2);
        stacks.printAll();
        return 0;
}
1 Comment
Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this.Implement

Leave a Reply.

Author

Categories

Archives
