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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

/******************************************************************************************
*******************************************************************************************
Chapter 4 Trees and Graphs

This is a class implementation of Binary Search Tree (BST), containing:

   inser(): insert a value in a BST
   isBalanced(): check if a BST is balanced, a BST is balanced if the difference of left and right subtrees height is atmost one!
   getHeight(): returns the height of a BST
   deleteBST(): deletes a BST      
   inOrder():      prints a BST i in-order fashion
   preOrder(): prints a BST i pre-order fashion
   postOrder(): prints a BST i post-order fashion

By: Hamed Kiani (Sep. 18, 2015)
******************************************************************************************
******************************************************************************************/

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

// tree node, including left and right pointers, data 
struct Node{
        Node(int value): data(value), left(NULL), right(NULL) {}
        int data;
        Node *left;
        Node *right;
};

/////////////////////////////////////////////////////////////////////////////////////////
// BST class
class BST{
private:
        Node *_root;
        void insert(Node *treeNode, int data);
        bool isBalanced(Node *treeNode);
        int  getHeight(Node *treeNode);
        void deleteBST(Node *treeNode);
        void inOrder(Node * treeNode);
        void preOrder(Node * treeNode);
        void postOrder(Node * treeNode);
public:

        BST();  // constructor     
        ~BST();     // destractor

        void insert(int data){ insert(_root, data);}       

        int getHeight(){return getHeight(_root);}
        Node * getMaxNode();
        Node * getMinNode();

        void deleteBST() {deleteBST(_root);}

        bool isBalanced(){return isBalanced(_root);        }

        void inOrder() {inOrder(_root);}
        void preOrder(){preOrder(_root);}
        void postOrder(){postOrder(_root);}
};

/////////////////////////////////////////////////////////////////////////////////////////
BST::BST()
{
        _root = NULL;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::insert(Node *treeNode, int data)
{
        if (!treeNode)
        {
                treeNode = new Node(data);           
                _root = treeNode;           
        }
        else
        {
                if (data < treeNode->data)
                {
                        if (!treeNode->left)
                        {
                                Node *treeTemp = new Node(data);
                                treeNode->left = treeTemp;
                        }
                        else
                                insert(treeNode->left, data);
                }
                else
                {
                        if (!treeNode->right)
                        {
                                Node *treeTemp = new Node(data);                         
                                treeNode->right = treeTemp;
                        }
                        else
                                insert(treeNode->right, data);
                }
        }
}

/////////////////////////////////////////////////////////////////////////////////////////
int BST::getHeight(Node *treeNode)
{
        if (!treeNode)
                return 0;
        return 1 + max(getHeight(treeNode->left) , getHeight(treeNode->right));
}

/////////////////////////////////////////////////////////////////////////////////////////
bool BST::isBalanced(Node *treeNode)
{
        if (!treeNode)
                return false;
        int leftHeight = getHeight(treeNode->left);
        int rightHeight = getHeight(treeNode->right);

        if (abs(leftHeight - rightHeight) > 1)
                return false;
        return true;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMaxNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->right)
                treeNode = treeNode ->right;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMinNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->left)
                treeNode = treeNode ->left;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::deleteBST(Node *treeNode) 
{
        if (!treeNode)
                return;

        Node * curTreeNode = treeNode;
        Node * leftTreeNode = treeNode->left;
        Node * rightTreeNode = treeNode->right;
        delete(curTreeNode);
        deleteBST(leftTreeNode);
        deleteBST(rightTreeNode);
}

/////////////////////////////////////////////////////////////////////////////////////////
BST::~BST()
{
        deleteBST();
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::inOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        inOrder(treeNode->left);
        cout << treeNode->data << " " ;
        inOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::preOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        cout << treeNode->data << " ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::postOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout << treeNode->data << " ";
}

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
        BST myBST;
        myBST.insert(5);
        myBST.insert(10);
        myBST.insert(3);

        myBST.insert(51);
        myBST.insert(110);
        myBST.insert(13);
        
        int h = myBST.getHeight();
        cout << "the height of this BSt is : " << h << endl;

        Node * mx = myBST.getMaxNode();
        cout << "max value: " << mx->data << endl;

        Node * mi = myBST.getMinNode();
        cout << "min value: " << mi->data << endl;

        bool isbal = myBST.isBalanced();
        if (isbal)
                cout << "BST is balanced! " << endl;
        else
                cout << "BST is not balanced! " << endl;

        cout << " in-order traverse is : " << endl;
        myBST.inOrder();cout << endl;
        cout << " pre-order traverse is : " << endl;
        myBST.preOrder();cout << endl;
        cout << " post-order traverse is : " << endl;
        myBST.postOrder();cout << endl;
}

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

  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
171
172
173
174
175
176
177
178
179
180
181
182
183
184

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Implement a MyQueue class which implements a queue using two stacks.
We use two stacks, s1 and s2 for enqueue and dequeue. 
 
By: Hamed Kiani (Sep. 7, 2015)
******************************************************************************************
******************************************************************************************/

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

struct Node{
        int data;
        Node *next;
};

class MyQueue{
private:
        Node *_s1_head;     // enQueue is done using s1
        Node *_s2_head;     // s2 is used for dequeue
        int _s1_size;    // the size of s1 stack    
        int _s2_size;    // the size of s2 stack
        
public:
        MyQueue();
        ~MyQueue();
        void enQueue(int data);    // enqueue data value using s1
        Node* deQueue();             // dequeue using s1 and s2
        void print_s1();          // print elements of s1 stack
        void print_s2();          // print elements of s2 stack
        bool isEmpty(Node *); // check if s1 or s2 are empty
        int get_s1_size(){return _s1_size;}        // return size of s1
        int get_s2_size(){return _s2_size;}        // return size of s2
};

////////////////////////////////////////////////////////////////////
MyQueue::MyQueue()
{
        _s1_head = NULL;
        _s2_head = NULL; 
        _s1_size = 0;
        _s2_size = 0;
        cout << "the stack and queue are initialized! " << endl;
}

////////////////////////////////////////////////////////////////////
MyQueue::~MyQueue()
{
        Node *temp;
        
        while(_s1_head != NULL)
        {
                temp = _s1_head;
                _s1_head = _s1_head->next;
                delete temp;
        }

        while(_s2_head != NULL)
        {
                temp = _s2_head;            
                _s2_head = _s2_head->next;
                delete temp;
        }
        cout << "the stack and queue are deleted! " << endl;
}

////////////////////////////////////////////////////////////////////
// enQueue data at begin of s1 (push s1 stack)
void MyQueue::enQueue(int data)
{
        Node *temp = new Node;
        temp->data = data;
        temp->next = _s1_head;
        _s1_head = temp;
        _s1_size++;  
        cout << " the enQueue value is: " << data << endl;
}

////////////////////////////////////////////////////////////////////
// For deQueue, 
// we copy all from s1 to ss except the last node of s1 O(n)
// re-copy s2 to s1 in reverse order O(n)
// update the s1_size and s2_size
Node* MyQueue::deQueue()
{
        // the queue is empty and dequeue is not possible
        if ((_s1_size == 0) )
        {
                cout<< "dequeue is not possible !" << endl;
                return NULL;                 
        }

        // there is just one element in queue
        if ((_s1_size == 1) )
        {
                Node * temp = _s1_head;
                _s1_head = NULL;
                _s1_size--;
                cout << " the dequeue value is: " << temp->data << endl;
                return temp;
        }

        // there are more than one element in the queue
        _s2_head = _s1_head;
        _s1_head = NULL;
        Node * temp;
        temp = _s2_head;
        _s1_size--;
        while(temp->next->next != NULL)
        {
                temp = temp->next;
        }
        Node * temp2;
        temp2 = temp->next;
        temp->next = NULL;       
        _s1_head = _s2_head;
        _s2_head = NULL;
        cout << " the dequeue value is: " << temp2->data << endl;
        return temp2;
}

////////////////////////////////////////////////////////////////////
void MyQueue::print_s1()
{
        if (_s1_head == NULL)
        {
                cout << " stack s1 is empty" << endl;
                return;
        }
        Node* temp;
        temp = _s1_head;
        while(temp)
        {
                cout << temp->data << " " ;
                temp = temp->next;
        }
        cout << endl;
}

//////////////////////////////////////////////////////////
void MyQueue::print_s2()
{
        if (_s2_head == NULL)
        {
                cout << " stack s2 is empty" << endl;
                return;
        }
        Node* temp;
        temp = _s2_head;
        while(temp)
        {
                cout << temp->data << " " ;
                temp = temp->next;
        }
        cout << endl;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        MyQueue queue;
        queue.enQueue(1);        
        cout << queue.get_s1_size() << endl;
        cout << queue.get_s2_size() << endl;
        queue.print_s1();
        queue.print_s2();
        Node * temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        queue.print_s1();
        queue.print_s2();
        queue.enQueue(3);
        queue.enQueue(4);
        queue.print_s1();
        queue.print_s2();
        return 0;
}

  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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Imagine a (literal) stack of plates.
If the stack gets too high, it might topple.
Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. 
Implement a data structure SetOfStacks that mimics this.
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
 
By: Hamed Kiani (Sep. 7, 2015)
******************************************************************************************
******************************************************************************************/

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

class SetOfStacks{
private:
        int _numOfStk;   // number of stacks
        int _thOfStk;    // threshold of stacks
        int _curStk;     // index of current stack
        int **_stacks;       // two-dim array to keep stacks elements
        int *_elmts; // number of elements in each stack

public:
        SetOfStacks(int n, int t);
        ~SetOfStacks();
        void push(int n);  // push the element n on the stack
        int pop();                        // pop operation
        int pop(int k);            // pop operation from stack k
        bool isFull(int k);        // is stack k full?
        bool isFull();            // is the stack full?
        bool isEmpty(int k);//        is the stack k empty?
        bool isEmpty();           // is the stack empty?
        void printAll();  // print all elements
        void printK(int k);        // print elemets of stack k
};

////////////////////////////////////////////////////////////       
SetOfStacks::SetOfStacks(int n, int t)
{
        _numOfStk = n;
        _thOfStk  = t;
        _curStk   = 0;

        // _elmts = new int[_numOfStk];
        _elmts = (int*) malloc(_numOfStk * sizeof(int));
        for(int i = 0; i < _numOfStk; i++)
                _elmts[i] = -1;  // all are empty


        _stacks = (int **) malloc(_numOfStk * sizeof(int *));
        for (int i = 0; i<_numOfStk; i++)
                _stacks[i] = (int *) malloc(_thOfStk * sizeof(int));
        cout << n << " stacks are created, windex 0,..., " << n-1 << endl;
        cout << " the threshold for each stack is " << t << " elements " << endl;
}

////////////////////////////////////////////////////////////
SetOfStacks::~SetOfStacks()
{
        free(_elmts);
        free(_stacks);
        cout << " stacks are deleted!" << endl;
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull(int k)
{
        return (_elmts[k] == _thOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull()
{
        return isFull(_numOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty(int k)
{
        return (_elmts[k] == -1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty()
{
        return isEmpty(0);
}

////////////////////////////////////////////////////////////
void SetOfStacks::push(int n)
{
        if (isFull())
        {
                cout << "stack overflow! cann't push " << n << " value! " << endl;
                return;
        }       
        if (_elmts[_curStk] == _thOfStk - 1)
                _curStk++;
        cout << "value " << n << " pushed on stack " << _curStk <<  endl;
        _elmts[_curStk]++;
        _stacks[_curStk][_elmts[_curStk]] = n;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop()
{
        if (isEmpty())
        {
                cout << "stack under flow! " << endl;
                return INT_MAX;
        }
        int i = _stacks[_curStk][_elmts[_curStk]];
        cout << "value " << i << " is popped from stack " << _curStk << endl;
        _elmts[_curStk]--;  
        if ((_elmts[_curStk] == -1) & (_curStk > 0))
                _curStk--;
        
        return i;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop(int k)
{
        if (isEmpty(k))
        {
                cout << "stack under flow!" << endl;
                return INT_MAX;
        }

        if ((k > _numOfStk-1) | (k < 0))
        {
                cout << " stack index is out of range! " << endl;
                return INT_MAX;
        }

        
        int i = _stacks[k][_elmts[k]];
        cout << "value " << i << " is popped from stack " << k << endl;
        _elmts[k]--;
        if ((_elmts[k] == -1) & (k > 0) & (k == _curStk))
                _curStk--;
        return i;
}

////////////////////////////////////////////////////////////

void SetOfStacks::printAll()
{
        cout << "print all the stacks:" << endl;
        for (int i = 0; i < _numOfStk; i++)
        {
                if (isEmpty(i))
                        cout << "stack " << i <<  " is empty " << endl;
                else
                {
                        for (int j = 0; j <= _elmts[i]  ; j++)
                                cout << _stacks[i][j] << " " ;
                        cout << endl;
                }
        }
}

////////////////////////////////////////////////////////////
void SetOfStacks::printK(int k)
{
        if (k > _numOfStk-1)
        {
                cout << "index is more than the stack size!" << endl;
                return;
        }

        if (k < 0)
        {
                cout << "index is less than the stack size!" << endl;
                return;
        }

        if (isEmpty(k))
                        {
                                cout << "stack " << k <<  " is empty " << endl;
                                return;
        }
                else
                {
                        for (int j = 0; j <= _elmts[k]  ; j++)
                                cout << _stacks[k][j] << " " ;
                        cout << endl;
                }
}

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        int n = 2;
        int t = 3;
        SetOfStacks stacks(n,t);
        
        stacks.push(1);
        stacks.push(2);
         stacks.push(3);
        
        stacks.push(10);
        stacks.push(20);
        stacks.push(30);

        stacks.push(100);
        stacks.push(200);
        stacks.push(300);

        stacks.push(1000);
        stacks.push(2000);
        stacks.push(3000);
        stacks.push(3001);
        stacks.push(3002);       

        stacks.printK(0);
        stacks.printK(1);
        stacks.printK(2);
        stacks.printK(3);
        stacks.printK(4);

        stacks.printAll();

        stacks.pop();
        stacks.pop();
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(2);
        stacks.printAll();
        return 0;
}

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

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

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

  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

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

A simple class of Stack!
 
By: Hamed Kiani (Sep. 1, 2015)
******************************************************************************************
******************************************************************************************/

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


struct Node{
        int _data;
        Node* _next;
};

class myStack{
private:
        Node* _head;
        int _size;

public:
        myStack();
        ~myStack(); 
        void push(int data);
        void pop();
        Node* return_top();
        int get_size();
        bool is_empty();
        void clear();
        void print_stack();
};

// constructor
myStack::myStack()
{
        _head = NULL;
        _size = 0;
}
myStack::~myStack()
{
        clear();
}

// is empty function
bool myStack::is_empty()
{
        return (_size == 0);
}

// retrun the stack size
int myStack::get_size()
{
        return _size;
}

// puch on the top
void myStack::push(int data)
{
        Node* temp = new Node;
        temp->_data = data;
        temp->_next = _head;
        _head = temp;
        _size++;
}

// pop the top data
void myStack::pop()
{
        if (is_empty())
        {
                cout << " the stack is empty, poping faild" << endl;
                return;
        }

        Node* temp  = _head;
        _head = _head->_next;
        delete temp;
        _size--;
}

// return the pointer of the top value
Node* myStack::return_top()
{
        if (is_empty())
                return NULL;
        Node* temp = _head;
        return temp;
}

// empty the stack
void myStack::clear()
{
        while(_size)
                pop();
        cout << " stack is deleted" << endl;
}

// print the stack values
void myStack::print_stack()
{
        Node* temp = _head;
        while(temp != NULL){
                cout << temp->_data << " " ;
                temp = temp->_next;
        }
        cout << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
        myStack stack;  
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.print_stack();
        cout << stack.get_size() << endl;
        stack.pop();
        stack.print_stack();

        Node* temp = stack.return_top();
        cout << temp->_data << endl;

        return 0;
}

  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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683

/******************************************************************************************
*******************************************************************************************
Chapter 2 Linked List: a class and three interview questions

By: Hamed Kiani (July 25, 2015)
******************************************************************************************
******************************************************************************************/

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

// a struct of linked list node, 
// contains two elements, _data: the value of node, _next: a pointer to the next node/NULL
struct Node{
        int _data;
        Node* _next;
};


// LinkedList class, 
// private: 
//         _head: keeps the head address (first node)
//         _tail: keeps the tail address (last node)
//         _size: the number of nodes in a linked list

// public:
//         LinkedList(): constructor
//         ~LinkedList(): destructor
//         size(): return the _size of the list
//         addFront(data): add a node at begining/head of the list with _data = data 
//         addTail(data):  add a node at end/tail of the list with _data = data
//         deleteFront():  delete the first node of the list
//         deleteTail():   delete the tail node
//         getHead():              return the address of list's head
//         getTail():              return the address of list's tail
//         insertAfter(position, data):    instert a node with data value after the position address
//         deleteThisNode(position):               delete the node at the position address
//         searchInList(data):                             find data in the list
//         reverseList():                                  reverse the linked list
//         addWithList(listTemp):                  sum the list with the listTemp
//         appendTheList(listTemp):                append the listTemp to the end of the list
//         printList():                                    print the list
//         printListRecursion(temp):               recursion version of print list
//         remove_deuplicate_fun_1():              remove duplicate values in the list
//         nth_to_end_node(n):                             return the address of the n-th to end of the list


// class declaration

class LinkedList{

private:
        Node* _head;
        Node* _tail;
        int _size;

public:
        LinkedList();
        ~LinkedList();

        int size();

        void addFront(int data);
        void addTail(int data);

        void deleteFront();
        void deleteTail();

        Node* getHead();
        Node* getTail();

        void insertAfter(Node* position, int data);
        void deleteThisNode(Node* position);
        int searchInList(int data);

        void reverseList();

        void addWithList(const LinkedList *listTemp);
        void appendTheList(const LinkedList *listTemp);

        void printList();
        void printListRecursion(Node* temp);

        void remove_deuplicate_fun_1();
        Node* nth_to_end_node(int n);
};

LinkedList::LinkedList()
{
        _head = NULL;
        _tail = NULL;
        _size = 0;
}

LinkedList::~LinkedList()
{
        cout << "**********DESTRUCTOR***********" << endl;
        cout << "**********DESTRUCTOR***********" << endl;
        cout << "**********DESTRUCTOR***********" << endl;


        cout << "the destructor is called! deleting the linked list by calling deleteFront() function!" << endl;
        while (_size>0)
                deleteFront();
}

int LinkedList::size()
{
        return _size;
}

void LinkedList::addFront(int data)
{
        
        Node* nodeTemp = new Node;
        if (_head == NULL)
        {
                nodeTemp->_data = data;
                _head = nodeTemp;
                _tail = nodeTemp;
                nodeTemp->_next = NULL;
                _size = 1;
        }
        else
        {
                nodeTemp->_data = data;
                nodeTemp->_next = _head;
                _head = nodeTemp;
                _size++;
        }
        cout << "the value: " << data << " is added to the front of list! " <<
                "current size is: " << _size << endl;
}

void LinkedList::addTail(int data)
{
        Node* nodeTemp = new Node;
        nodeTemp->_data = data;
        nodeTemp->_next = NULL;

        if (_tail != NULL)
        {
                _tail->_next = nodeTemp;
                _tail = nodeTemp;
                _size++;
                cout << "the value: " << data << " is added to the tail of list! " <<
                        "current size is: " << _size << endl;
        }
        else
                addFront(data);
}

void LinkedList::printList()
{
        cout << "***********************************" << endl;
        cout << "The list containts: " << endl;
        int i = _size;
        Node* temp = _head;
        while (i>0)
        {
                cout << temp->_data << " " ;
                temp = temp->_next;
                i--;
        }
        cout << endl;
        cout << "***********************************" << endl;
}

void LinkedList::deleteFront()
{
        if (_head == NULL)
                return;
        int data = _head->_data;
        Node* temp;
        temp = _head;
        if (_head->_next == NULL)
        {
                _head = NULL;
                _tail = NULL;
        }
        else
                _head = _head->_next;
        _size--;
        delete temp;
        cout << "the value: " << data << " is deleted from the front of list! " <<
                "current size is: " << _size << endl;
}

void LinkedList::deleteTail()
{
        if (_tail == NULL)
                return;
        int data = _tail->_data;
        Node* temp = _head;
        while (temp->_next != _tail)
                temp = temp->_next;
        _tail = temp;
        temp = temp->_next;
        _tail->_next = NULL;
        delete temp;
        _size--;
        cout << "the value: " << data << " is deleted from the tail of list! " <<
                "current size is: " << _size << endl;
}


Node* LinkedList::getHead()
{
        return _head;
}

Node* LinkedList::getTail()
{
        return _tail;
}

void LinkedList::insertAfter(Node* position, int data)
{
        if (position == NULL)
        {
                addFront(data);
                return;
        }
        if (position->_next == NULL)
        {
                addTail(data);
                return;
        }

        Node* temp = new Node;
        temp->_data = data;
        temp->_next = position->_next;
        position->_next = temp;
        _size++;
}

void LinkedList::deleteThisNode(Node* position)
{
        if (position == NULL)
                return;
        if (position == _head)
        {
                deleteFront();
                return;
        }
        if (position->_next == NULL)
        {
                deleteTail();
                return;
        }
        Node * temp = _head;
        while (temp->_next != position)
                temp = temp->_next;
        temp->_next = position->_next;
        delete position;
        _size--;
}


int LinkedList::searchInList(int data)
{
        Node* temp = _head;
        int i = 1;
        while (temp != NULL)
        {
                if (temp->_data == data) return i;
                temp = temp->_next;
                i++;
        }
        return -1;
}

void LinkedList::reverseList()
{
        // keep the next node to add to reverse list. 
        Node* next;
        // keep the head of the reversed list so far.
        // at the first, the reversed list is empty - null
        Node* prev = NULL;
        // a loop to traverse the list
        while (_head)
        {
                next = _head->_next;
                _head->_next = prev;
                prev = _head;
                _head = next;
        }
        // at the end, the head of reversed list is pointed by prev
        _head = prev;

        // we need to update the tail too
        next = _head;
        while (next->_next != NULL)
                next = next->_next;
        _tail = next;
}


void LinkedList::addWithList(const LinkedList *listTemp)
{
        int s = listTemp->_size;
        if (s != _size)
                return;
        Node* t1 = listTemp->_head;
        Node* t2 = _head;

        while (t1 != NULL)
        {
                t2->_data += t1->_data;
                t1 = t1->_next;
                t2 = t2->_next;
        }
}

void LinkedList::appendTheList(const LinkedList *listTemp)
{
        Node* temp = listTemp->_head;
        while (temp != NULL)
        {
                Node* newNode = new Node;
                newNode->_data = temp->_data;
                newNode->_next = NULL;
                _tail->_next = newNode;
                _tail = _tail->_next;
                temp = temp->_next;
                _size++;
        }
}

void LinkedList::printListRecursion(Node* temp)
{
        if (temp == NULL)
                return;
        printListRecursion(temp->_next);
        cout << temp->_data << endl;
}


// inplace removing, O(n^2) time and O(1) additional space
void LinkedList::remove_deuplicate_fun_1()
{
        Node *head;
        Node *end;
        head = _head;
        int l = 0;
        if (!head)
                return;
        end = head->_next;
        Node *c;
        head = head->_next;
        while (head != NULL)
        {
                c = _head;
                while (c != end){
                        if (c->_data == head->_data)
                                break;
                        else
                                c = c->_next;
                }
                if (c == end)
                {
                        end->_data = head->_data;
                        end = end->_next;
                }
                head = head->_next;
        }
        head = _head;
        while (head->_next != end)
        {
                l++;
                head = head->_next;
                _tail = head;
        }
        _size = ++l;
        head->_next = NULL;
        _tail->_next = NULL;
}


Node* LinkedList::nth_to_end_node(int n)
{
        Node *p, *q;
        p = _head;
        q = _head;
        int i = 0;
        while (i < n & q != NULL)
        {
                q = q->_next;
                i++;
        }
        if (q == NULL)
                return NULL;
        while (q->_next != NULL)
        {
                q = q->_next;
                p = p->_next;
        }
        return p;
}


//         some useful functions and linked list questions
int pow(int a, int b)
{
        if (b == 0)
                return 1;
        return a*pow(a, b - 1);
}

// time: O(N), additional space:O(N)
void add_two_lists(LinkedList* l1, LinkedList* l2, LinkedList* l3)
{
        if (!l1 & !l2)
                return;
        if (!l1)
                l3 = l2;
        if (!l2)
                l3 = l1;

        // convert the linked list to a decimal digit
        int d1 = 0;
        int d2 = 0;
        int i  = 0;

        Node* temp1 = l1->getHead();
        Node* temp2 = l2->getHead();
        while (temp1 != NULL)
        {
                d1 += temp1->_data * pow(10, i);
                temp1 = temp1->_next;
                i++;
        }
        cout << "the digit of first link: " << d1 << endl;
        i = 0;
        while (temp2 != NULL)
        {
                d2 += temp2->_data * pow(10, i);
                temp2 = temp2->_next;
                i++;
        }
        cout << "the digit of 2nd link: " << d2 << endl;

        int add = d1 + d2;
        while ((add) > 0)
        {
                l3->addFront(add % 10);
                add /= 10;
        }
}

// without converting to decimal and re-digiting into the third linked list
void add_two_lists_2(LinkedList* l1, LinkedList* l2, LinkedList* l3)
{
        if (!l1 & !l2)
                return;
        if (!l1)
                l3 = l2;
        if (!l2)
                l3 = l1;
        int carry = 0;
        Node* temp1 = l1->getHead();
        Node* temp2 = l2->getHead();
        while (temp1 || temp2)
        {
                int t1 = (!temp1) ? 0 : temp1->_data;
                int t2 = (!temp2) ? 0 : temp2->_data;
                l3->addFront((t1 + t2 + carry) % 10);
                carry = (t1 + t2 + carry) / 10;
                if (temp1 != NULL)
                        temp1 = temp1->_next;
                if (temp2 != NULL)
                        temp2 = temp2->_next;
        }
        if (carry > 0)
                l3->addFront(1);
}

//         find the joint node of two linked list: time O(N), memory: O(N)
Node* find_joint_node_of_two_links(Node* h1, Node* h2)
{
        if (!h1 | !h2)
                return NULL;
        int l1, l2;
        l1 = 0;
        l2 = 0;
        Node *temp = h1;
        while (temp != NULL)
        {
                l1++;
                temp = temp->_next;
        }
        temp = h2;
        while (temp != NULL)
        {
                l2++;
                temp = temp->_next;
        }
        int diff = (l1 - l2>0) ? (l1 - l2) : (l2 - l1);
        for (int i = 0; i < diff; i++)
        {
                if (l1 > l2)
                        h1 = h1->_next;
                else
                        h2 = h2->_next;
        }

        while (h1 != NULL & h2 != NULL){
                if (h1 == h2)
                        return h1;
                h1 = h1->_next;
                h2 = h2->_next;
        }
        return NULL;
}

// check if there is a loop in the linked list
Node* is_loop_in_linkedlist(Node* head)
{
        Node* slow = head;      // moves one node
        Node* fast = head;      // moves two nodes

        if (!head)
                return NULL;

        while (fast != NULL & fast->_next != NULL & slow != NULL)
        {
                slow = slow->_next;
                fast = fast->_next->_next;
                if (fast == slow)
                        return slow;
        }
        return NULL;
}

// check the video and description in the post for more details
Node* find_the_first_node_of_loop(Node* head)
{
        Node* meetPoint = is_loop_in_linkedlist(head);
        if (meetPoint == NULL)
                return NULL;

        Node* temp;
        temp = head;
        while (temp != meetPoint)
        {
                temp = temp->_next;
                meetPoint = meetPoint->_next;
        }
        return temp;
}
void main() {
        // test the basics functions
        // a linked list object with five nodes
        LinkedList myList;
        myList.addFront(5);
        myList.addFront(4);
        myList.addFront(3);
        myList.addFront(2);
        myList.addFront(1);

        // print the list
        myList.printList();
        // myList.printListRecursion(myList.getHead());

        // add to the tail
        myList.addTail(1);
        myList.addTail(3);
        myList.addTail(3);

        // print the list
        myList.printList();

        cout << "delete from front" << endl;
        myList.deleteFront();
        myList.deleteTail();
        myList.printList();

        // print the head and tail values
        Node* tail = myList.getTail();
        Node* head = myList.getHead();

        cout << "the value in the first node is: " << head->_data << endl;
        cout << "the value in the last node is: "  << tail->_data << endl;

        // insert a node in the list
        cout << "insert a new value of " << 200 << " in the third place: " << endl;
        Node* position = myList.getHead();
        myList.insertAfter(position->_next, 200);
        myList.printList();
        
        // delete a node from the list
        cout << "delete the third node: " << endl;
        position = myList.getHead();
        myList.deleteThisNode(position->_next->_next);
        myList.printList();

        // search a value in the linked list
        int pos = myList.searchInList(10);
        (pos < 0) ? (cout << "the value 10 is no found" << endl) : (cout << "the value 10 is found at node : " << pos << endl);

        // reverse the list
        myList.reverseList();
        myList.printList();

        // a new linked list object
        LinkedList myList_2;
        myList_2.addFront(7);
        myList_2.addFront(6);
        myList_2.addFront(5);
        myList_2.addFront(4);
        myList_2.addFront(4);
        myList_2.addFront(4);

        // adding the myList_2 to myList
        myList.addWithList(&myList_2);
        myList.printList();

        // appending two lists
        myList.appendTheList(&myList_2);
        myList.printList();

        // remove duplicates form myList
        myList.remove_deuplicate_fun_1();
        myList.printList();

        // return the n-th node to the end
        int n = 4;
        position = myList.nth_to_end_node(n);
        if (position)
                cout << " the " << n << " to end element is :" << position->_data << endl;
        else
                cout << "is longer the length of the list ! " << endl;

        // Problem1: adding the values of two linked lists
        LinkedList myList_3;

        add_two_lists(&myList, &myList_2, &myList_3);
        // add_two_lists_2(&myList, &myList_2, &myList_3);
        myList_3.printList();

        // Problem 2: find the junction of two lists

        Node n1, n2, n3, n4, n5, n6;
        n1._data = 1;
        n2._data = 2;
        n3._data = 3;
        n4._data = 4;
        n5._data = 5;
        n6._data = 6;
        n1._next = &n2;
        n2._next = &n3;
        n3._next = &n4;
        n4._next = &n5;
        n5._next = NULL;
        n6._next = &n4;
        Node* conj = find_joint_node_of_two_links(&n1, &n6);
        if (!conj)
                cout << "there is no conjuction  " << endl;
        else
                cout << "the conjuction node contains the value of : " << conj->_data << endl;
        
        // Problem 3: is there a cycle in the linked list
        n1._next = &n2;
        n2._next = &n3;
        n3._next = &n4;
        n4._next = &n5;
        n5._next = &n2;
        conj = is_loop_in_linkedlist(&n1);
        if (conj)
                cout << "there is a loop" << endl;
        else
                cout << "there is not loop" << endl;

        // Problem 4: if there is a cycle in the linked list, return the start node of the loop
        
        conj = find_the_first_node_of_loop(&n1);
        if (conj)
                cout << "the value of the start-loop node is : " << conj->_data << endl;
        else
                cout << "there is not loop" << endl;               
}

  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

/******************************************************************************************
*******************************************************************************************
Chapter 1 Arrays and Strings

 * Assume you have a method isSubstring which checks if one word is a substring of another.
 * Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
 * only one call to isSubstring (i.e., "waterbottle" is a rotation of "erbottlewat")
 
By: Hamed Kiani (July 20, 2015)
******************************************************************************************
******************************************************************************************/

#include<iostream>
#include<cstring>

using namespace std;

bool is_sub_string(const char* s1, const char* s2)
{
        // check if two strings are not null
        if (!s1 || !s2)
                return false;
        // find the first char of s2, s2[0] in the s1, if found then check the rest of s2 over s1
        int i,j ;
        j = 0;
        for (i = 0; s1[i] != '\0'; i++)
        {
                if (s1[i] == s2[0]) {
                        for(j = 1; s2[j] != '\0'; j++)                    
                                // we are already sure that s1[i] == s2[0]
                                if (s2[j] != s1[i+j])
                                        break;
                }
                // if (s2[j] == '\0') means that we have similar chars till the end of s2
                if (s2[j] == '\0')
                        return true;
        }
        // is not s sub string
        return false;
}

// O(n) time, O(1) additional space.
bool is_rotation_fun1(const char* s1, const char* s2)
{
        if (!s1 || !s2)
                return false;
        if (strlen(s1) != strlen(s2))
                return false;

        while(*s2 != '\0')
                s2++;
        s2--;
        while(*s1 != '\0')
        {
                if (*s1 != *s2)
                        return false;
                s1++; s2--;
        }       
        return true;
}

// O(n) time, O(n) additional space.
// using is_rotation function
// the trick is that we append the inverse of s1 to s1 and then check:
// if is_sub_string(s1+inv(s1[1:length(s1)-1]), s2).
// name + man = nameman
// is is_sub_string(nameman, eman)
bool is_rotation_fun2(  char* s1,   char* s2)
{
        int l1;
        l1 = strlen(s1);            
        char* temp = (char *) malloc( sizeof(char) * l1 * 2);
        char *t1 = s1;   
        int i = 0;
        while(*t1 != '\0')
        {
                temp[i] = *t1;
                t1++; i++;
        }
        // move t1 pointin to end of s1 to next to last char. 
        // accordingly, we change l1 = l1 -2, since we ignore the last char of s1 
        //and consider length counter as [0...strlen(s1)-1]
        t1 -= 2; l1 -= 2;
        while(l1>=0)
        {
                temp[i] = s1[l1];
                l1--; i++;
        }       
        bool check = is_sub_string(temp, s2);
        free(temp);
        return check;
}

void main() {
        char str1[] = "check this string";
        char str2[] = "this";
        bool check ;
        check = is_sub_string(str1,str2);
        cout << check << endl;

        char str3[] = "siht";
        check = is_rotation_fun1(str3, str2);
        cout << check << endl;

        check = is_rotation_fun2(str3, str2);
        cout << check << endl;
}