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

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; }