Untitled
unknown
plain_text
3 years ago
2.4 kB
3
Indexable
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);
}
}
Editor is loading...