Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.We design this class using array instead of linkedlist

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

/****************************************************************************************** ******************************************************************************************* Chapter 3 Stack and Queue Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. We design this class using array instead of linkedlist By: Hamed Kiani (Sep. 2, 2015) ****************************************************************************************** ******************************************************************************************/ #include "stdafx.h" #include <iostream> using namespace std; class minStack{ private: int* _main_stk; // main stack int* _aux_stk; // aux. stack to keep elements in sorted int _cap; // the maximum capacity of stack int _top; // size of stack public: minStack(int n); ~minStack(); void push(int data); int pop(); bool is_empty(); bool is_full(); void print_stk(); void print_aux_stk(); int getMin(); }; minStack::minStack(int n) { _cap = n; _main_stk = new int[_cap]; _aux_stk = new int[_cap]; _top = -1; cout << " an object of minStack is created!" << endl; } minStack::~minStack() { delete[] _main_stk; delete[] _aux_stk; cout << " an object of minStack is deleted!" << endl; } bool minStack::is_empty() { return (_top == -1); } bool minStack::is_full() { return (_top == _cap-1); } void minStack::push(int data) { if (is_full()) { cout << "stack overflow!" << endl; return; } cout << " The element " << data << " is pushed on the stack!" << endl; // if the stack is empty or data is less than all elements in the aux. stack, just push it if ((_top == -1) || (data <= _aux_stk[_top])) { _top++; _main_stk[_top] = data; _aux_stk[_top] = data; return; } // otherwise, push data on the main stack and duplicate the current min in the new position int temp = _aux_stk[_top]; _top++; _main_stk[_top] = data; _aux_stk[_top] = temp; } // pop operation: simply just _top--! int minStack::pop() { if (is_empty()) { cout << "underflow!" << endl; return INT_MAX; } _top--; cout << " The element " << _main_stk[_top+1] << " is popped from the stack!" << endl; } // return min value int minStack::getMin() { return _aux_stk[_top]; } // print the main stack void minStack::print_stk() { if (is_empty()) { cout << " nothing to print!" << endl; return; } for (int j = 0; j <= _top; j++) cout << _main_stk[j] << " " ; cout << endl; } // print the main stack void minStack::print_aux_stk() { if (is_empty()) { cout << " nothing to print!" << endl; return; } for (int j = 0; j <= _top; j++) cout << _aux_stk[j] << " " ; cout << endl; } //////////////////////////////////////////////////////////// int _tmain(int argc, _TCHAR* argv[]) { minStack stack(10); stack.push(12); stack.push(3); stack.push(4); stack.push(11); stack.push(12); cout << "the min value is : " << stack.getMin() << endl; stack.push(11); stack.push(41); cout << "the min value is : " << stack.getMin() << endl; stack.push(12); stack.push(1); stack.push(3); cout << "the min value is : " << stack.getMin() << endl; stack.print_stk(); stack.print_aux_stk(); cout << "the min value is : " << stack.getMin() << endl; stack.pop(); stack.pop(); stack.pop(); cout << "the min value is : " << stack.getMin() << endl; stack.print_stk(); stack.print_aux_stk(); return 0; }