Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.4 kB
2
Indexable
Never


ANSWER:-

C++ Code:-

#include <bits/stdc++.h>

using namespace std;

bool insertionCriteria1(int x, stack<int> st)

{

if (st.empty() == true || x < st.top())

{

return true;

}

return false;

}

bool insertionCriteria2(int x, stack<int> st)

{

if (st.empty() == true || x > st.top())

{

return true;

}

return false;

}

void print_stack_content(stack<int> st)

{

while (st.empty() == false)

{

cout << st.top() << " ";

st.pop();

}

}

int main()

{

int NN;

cin >> NN;

int arr[NN];

for (int i = 0; i < NN; i++)

{

cin >> arr[i];

}

queue<int> q;

stack<int> st1, st2;

for (int i = 0; i < NN; i++)

{

if (insertionCriteria1(arr[i], st1))

{

st1.push(arr[i]);

}

else if (insertionCriteria2(arr[i], st2))

{

st2.push(arr[i]);

}

else

{

bool stack_1_chosen = true;

if (abs(st1.top() - arr[i]) < abs(st2.top() - arr[i]))

{

stack_1_chosen = true;

}

else

{

stack_1_chosen = false;

}

if (stack_1_chosen)

{

while (!insertionCriteria1(arr[i], st1) && !insertionCriteria2(arr[i], st2))

{

int x = st1.top();

st1.pop();

q.push(x);

}

if (insertionCriteria1(arr[i], st1))

{

st1.push(arr[i]);

}

else if (insertionCriteria2(arr[i], st2))

{

st2.push(arr[i]);

}

while (!q.empty())

{

int size = q.size();

size--;

while (size--)

{

q.push(q.front());

q.pop();

}

st1.push(q.front());

q.pop();

}

}

else

{

while (!insertionCriteria1(arr[i], st1) && !insertionCriteria2(arr[i], st2))

{

int x = st2.top();

st2.pop();

q.push(x);

}

if (insertionCriteria1(arr[i], st1))

{

st1.push(arr[i]);

}

else if (insertionCriteria2(arr[i], st2))

{

st2.push(arr[i]);

}

while (!q.empty())

{

int size = q.size();

size--;

while (size--)

{

q.push(q.front());

q.pop();

}

st2.push(q.front());

q.pop();

}

}

}

}

// reverse st2;

queue<int> temp;

while (st2.empty() == false)

{

temp.push(st2.top());

st2.pop();

}

while (temp.empty() == false)

{

st2.push(temp.front());

temp.pop();

}

int insertion = 1;

while (st1.empty() == false || st2.empty() == false)

{

if (st1.empty())

{

q.push(st1.top());

st1.pop();

}

else if (st2.empty())

{

q.push(st2.top());

st2.pop();

}

else

{

if (st1.top() < st2.top())

{

q.push(st1.top());

st1.pop();

}

else

{

q.push(st2.top());

st2.pop();

}

}

cout << "Insertion : " << insertion << "\n";

insertion++;

cout << "st1 : ";

print_stack_content(st1);

cout << "\n";

cout << "st2 : ";

print_stack_content(st2);

}

}