Hamed Kiani (Ph.D.)
  • Home
  • Publications
  • Contact

A class of K Stacks in a single array! Efficient memory and run time.: c++

9/2/2015

3 Comments

 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

A class of K Stacks in a single array! Efficient memory and run time. 
 
By: Hamed Kiani (Sep. 2, 2015)
******************************************************************************************
******************************************************************************************/

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

class kStacks{

private:
        int *arr;    // an array of size n to save the values in stacks
        int *top;    // an array of size k to keep the index of top values of k stacks
        int *next;   // an array of size n to keep the next entry in stacks
        int n,k; // n: size of array, k: number of stacks
        int next_slot;   // the next free slot in the array 

public:
        kStacks(int k1, int n1);
        ~kStacks();         
        bool is_full() { return (next_slot == -1);}
        bool is_empty(int sn) { return(top[sn] == -1);}
        void push(int sn, int data);
        int pop(int sn);
        void print_sn(int sn);
};

// constructor
kStacks::kStacks(int k1, int n1)
{
        k = k1; n = n1; 
        arr  = new int[n];    // to keep the values in the stacks
        top  = new int[k];    // to keep the last index of stacks
        next = new int[n];    // to handle the next and previous index of stacks

        // initial to -1, all k stacks are empty
        for (int i = 0; i < k; i++)
                top[i] = -1;

        // the next slot of each entry is the next index
        for (int i = 0; i < n-1; i++)
                next[i] = i+1;

        // for the last entry there is no free slot
        next[n-1] = -1;
        // the initial free slot is arr[0]
        next_slot = 0;
}

// destructor
kStacks::~kStacks()
{
        k = 0; n = 0;
        delete[] arr;
        delete[] next; 
        delete[] top;
}
 
// push operator
void kStacks::push(int sn, int data)
{
        // wrong stack number
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return;
        }

        // first check if the stack sn is overflow
        if (is_full())
        {
                cout << "stack overflow! cann't push!" << endl;
                return;
        }
        // keep the next free slot in i, we will use this to push data in arr
        int i = next_slot;
        // update the next free slot using next[i]. next free slot will be used for next push operation
        next_slot = next[i];
        // now we use next in a different role, to keep the second top value in stack, 
        next[i] = top[sn];
        // update the top by i
        top[sn] = i;
        // push the data in arr[i]
        arr[i] = data;
}

// pop operator
int kStacks::pop(int sn)
{
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return INT_MAX;
        }
        if (is_empty(sn))
        {
                cout << "stack underflow! cann't pup!" << endl;
                return INT_MAX;
        }
        // keep the current index of stack sn
        int i = top[sn];
        // keep the previous index of stack sn in top
        top[sn] = next[i];
        // initialize the next[i] by next free slot
        next[i] = next_slot;
        // next free slot is current i
        next_slot = i;
        // return current value
        return arr[i];
}

// print the stack sn
void kStacks::print_sn(int sn)
{
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return;
        }
        if (is_empty(sn))
        {
                cout << "no value to print" << endl;
                return;
        }

        int i = top[sn];
        
        while(next[i] != -1)
        {
                cout << arr[i] << " ";
                i =  next[i];
        }
        // for the last stack value with next[i] = -1;
        cout << arr[i] << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
        kStacks stack(3, 10);
        stack.push(0, 1);
        stack.push(0, 2);
        stack.push(0, 3);

        stack.push(1, 10);
        stack.push(1, 20);

        stack.push(2, 100);
        stack.push(2, 200);

        stack.print_sn(0);

        stack.pop(0);
        stack.pop(0);
        stack.print_sn(0);
        
        stack.print_sn(1);
        stack.print_sn(2);
        return 0;
}
3 Comments
Recipe Tom link
12/3/2020 04:09:53 am

I enjoyed reading youur post

Reply
Zachary Wade link
11/12/2022 02:32:52 pm

Prepare walk their kitchen at many religious. Identify local campaign box clearly.

Reply
Happy Endings Basingstoke link
1/31/2025 08:44:12 am

Great reading yyour post

Reply



Leave a Reply.

    A place to practice the coding interview.

    Author

    Hamed Kiani

    Categories

    All
    Arrays And Strings
    Linked List
    Stack And Queue
    Trees And Graphs

    Archives

    September 2015
    July 2015

    RSS Feed

Copyright © 2020, Hamed Kiani