Write a program to sort a stack in ascending order. 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 167 168 169 170

/****************************************************************************************** ******************************************************************************************* Chapter 3 Stack and Queue Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty. peek: return the top value of stack without removing it. We use two stacks for ordering the elements. The main stack contains the elements in a sorted fashion. The auxulary stack is used to sort the elements of the main stack if required. memory O(n) time O(n^2) Questions: how can we write this function with the memory of O(1)? how about a time of O(n)? is that possible? By: Hamed Kiani (Sep. 14, 2015) ****************************************************************************************** ******************************************************************************************/ #include "stdafx.h" #include <iostream> using namespace std; class sortedStack{ private: int *_mainStack; // main ordered stack int *_auxStack; // auxulary stack for ordering int _size; // the max size of stack for overflow checking int _top; // index of the top element of main stack int _aux_top; // index of the top element of aux stack public: sortedStack(int n); // constructor ~sortedStack(); // destructor bool isEmpty(); // is the stack empty? bool isFull(); // is the stack full? void push(int data); // ordered push // void ordered_push(int data); void pop(); // normal pop operation int peek(); // peek function void print(); // print the main stack }; //////////////////////////////////////////////////////////// sortedStack::sortedStack(int n) { _size = n; _top = -1; _aux_top = -1; // initializaing the main and aux stacks _mainStack = (int*) malloc(sizeof(int) * _size); _auxStack = (int*) malloc(sizeof(int) * _size); } //////////////////////////////////////////////////////////// sortedStack::~sortedStack() { free(_mainStack); free(_auxStack); } //////////////////////////////////////////////////////////// bool sortedStack::isEmpty() { return (_top == -1); } //////////////////////////////////////////////////////////// bool sortedStack::isFull() { return (_top == _size-1); } //////////////////////////////////////////////////////////// void sortedStack::push(int data) { // is full, not possible to push a new element if (isFull()) { cout << " stack overflow!" << endl; return; } // if the stack is empty or the new element is smaller // than the top value just do simple push int top_data = peek(); if ((data >= top_data) | (isEmpty())) { _mainStack[++_top] = data; return; } // otherwise, use aux-stack to push the new element in the right place while(~isEmpty() & (top_data > data )) { _auxStack[++_aux_top] = top_data; pop(); top_data = peek(); } _mainStack[++_top] = data; // re-push the lements in aux-stack back to the main stack while(_aux_top >= 0) { _mainStack[++_top] = _auxStack[_aux_top--]; } return; } //////////////////////////////////////////////////////////// void sortedStack::pop() { if (isEmpty()) { cout << " stack unerflow!" << endl; return; } _top--; } //////////////////////////////////////////////////////////// int sortedStack::peek() { if (isEmpty()) { cout << " stack is empty!" << endl; return INT_MAX; } return _mainStack[_top]; } void sortedStack::print() { if (isEmpty()) { cout << " stack is empty!" << endl; return; } cout << " the elemets of stack " << endl; for (int i=0; i<=_top; i++) cout << _mainStack[i] << " " ; cout << endl; } //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// int _tmain(int argc, _TCHAR* argv[]) { sortedStack myStack(10); myStack.push(1); myStack.push(15); myStack.push(32); myStack.push(4); myStack.push(1); myStack.print(); myStack.pop(); myStack.pop(); myStack.push(77); myStack.push(10); myStack.pop(); myStack.push(-15); myStack.print(); return 0; }