Answer to Question #198408 in C++ for MUQADAS

Question

Sort the data stored in 1) stack 2) queue and 3) linked list entered in part 1. Attach the code and output

Answer 1

#include<iostream>
#include<stack>
#include<bits/stdc++.h>
using namespace std;


class Node{
	public:
		int data;
		Node* next;
		
		Node(int data)
		{
			this->data = data;
			this->next = NULL;
		}
};


void insertEnd(Node *head, int data)
{
	if(head==NULL)
	{
		Node* new_node= new Node(data);
		head=new_node;
		
	}
	else{
		Node* new_node= new Node(data);
		Node *temp=head;
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=new_node;
			
	}
}




int findMin(queue<int> &q, int sortedIndex)
{
    int min_index = -1;
    int min_val = INT_MAX;
    int n = q.size();
    for (int i=0; i<n; i++)
    {
        int curr = q.front();
        q.pop();  
  
        if (curr <= min_val && i <= sortedIndex)
        {
            min_index = i;
            min_val = curr;
        }
        q.push(curr);  
    }
    return min_index;
}
  


void minToRear(queue<int> &q, int min_index)
{
    int min_val;
    int n = q.size();
    for (int i = 0; i < n; i++)
    {
        int curr = q.front();
        q.pop();
        if (i != min_index)
            q.push(curr);
        else
            min_val = curr;
    }
    q.push(min_val);
}
  
void sortHelper(queue<int> &q)
{
    for (int i = 1; i <= q.size(); i++)
    {
        int min_index = findMin(q, q.size() - i);
        minToRear(q, min_index);
    }
}
  




int main()
{
	cout<<"1. Stack"<<endl<<"2. Queue"<<endl<<"3.Linked List"<<endl;
	cout<<"Choose option in which type u want to store data : "<<endl;
	int option;
	cin>>option;
	cout<<"Enter number of elements : ";
	int n;
	cin>>n;
	
	switch(option)
	{
		case 1:
			{
			cout<<endl<<"Enter the elements of stack"<<endl;
			stack<int>s;
			for(int i=0; i<n; i++)
			{
				int a;
				cin>>a;
				s.push(a);
			}
			
			stack<int> tmpStack;
		    while (!s.empty())
		    {
		        int tmp = s.top();
		        s.pop();


		        while (!tmpStack.empty() && tmpStack.top() > tmp)
		        {
		            s.push(tmpStack.top());
		            tmpStack.pop();
		        }


		        tmpStack.push(tmp);
		    }
		    
		    stack<int>s1;
		    while(!tmpStack.empty())
		    {
		    	s1.push(tmpStack.top());
		    	tmpStack.pop();
			}
			
			cout<<endl<<"Elements of Stack in sorted order"<<endl;
			while(!s1.empty())
		    {
				cout<<s1.top()<<" ";
		    	s1.pop();
			}
			break;
	}
		case 2:
			{
			cout<<endl<<"Enter the elements of Queue"<<endl;
			queue<int>q;
			for(int i=0; i<n; i++)
			{
				int a;
				cin>>a;
				q.push(a);
			}
			
			sortHelper(q);
			cout<<endl<<"Elements of Queue in sorted order"<<endl;
			while(!q.empty())
			{
				cout<<q.front()<<" ";
				q.pop();
			}
			break;
	}
		case 3:
			{
			cout<<endl<<"Enter the elements of Linked List"<<endl;
			Node* head;
			vector<int>v;
			for(int i=0; i<n; i++)
			{
				int a;
				cin>>a;
				v.push_back(a);
				if(i == 0)
				{
					head = new Node(a);
				}
				else{
					insertEnd(head,a);
				}
			}
			sort(v.begin(), v.end());
			
			int i=0;
			cout<<endl<<"Elements of Linked List in sorted order"<<endl;
			while(head!= NULL)
			{
				head->data = v[i];
				cout<<head->data<<" ";
				head = head->next;
				i++;
			}
			break;
		}
		
	}
	
	
}