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

Write a program to sort a stack in ascending order. c++

9/15/2015

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



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