Plz do part b and use C++ language plz 3. Sorting. Implement a generic Stack lin
ID: 3752842 • Letter: P
Question
Plz do part b and use C++ language plz
3. Sorting. Implement a generic Stack linked list data structure for integers that supports these iin: a. i InsertionSort(), which runs an insertion sort algorithm on the stack Your insertionSort() algorithm should print to the console every time it makes a swap. Print the operation performed ("Swapped a with b") then on the next line print the current contents of the array. Print to the console when the sort has finished("Sort finished!") 1. ii. iii. iv. 2. Push(int data), which pushes values to the head of the stack Pop():, which pops values from the head of the stack and returns it Peek(), which returns a value from the head of the stackExplanation / Answer
//headerfile
#pragma once
#include<iostream>
using namespace std;
struct node
{
int data;
node *next;
};
class linkedList
{
node *head;
//void insrtedInOrder(node *sorted, node cur);
public:
linkedList();
void Push(int data);
void Pop();
int Peek();
void insertionSort();
void print();
int size();
};
-------------------------------------
//linked list implementation file
#include"Sep_23_linkedList.h"
linkedList::linkedList()
{
head = NULL;
}
void linkedList::Push(int data)
{
node *newNode,*tmp;
newNode = new node;
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
}
else
{
tmp = head;
head = newNode;
head->next = tmp;
}
}
void linkedList::Pop()
{
node *tmp = head;
head = head->next;
delete tmp;
}
int linkedList::Peek()
{
return head->data;
}
void linkedList::insertionSort()
{
if (head == NULL || head->next == NULL)
return ;
node *newNode = new node;
newNode->data = head->data;
newNode->next = NULL;
node *cur = head->next;
//go through each element in loop
while (cur != NULL)
{
//insert the elements into new list
node *pointer1 = newNode;
node *next = cur->next;
//data at head less than equal to next node data
if (cur->data <= newNode->data)
{
node *head1 = newNode;
newNode = cur;
newNode->next = head1;
}
else
{
while (pointer1->next != NULL)
{
if (cur->data > pointer1->data && cur->data <= pointer1->next->data)
{
node *next1= pointer1->next;
pointer1->next = cur;
cur->next = next1;
}
pointer1 = pointer1->next;
}
if (pointer1->next == NULL && cur->data > pointer1->data)
{
pointer1->next = cur;
cur->next = NULL;
}
}
cur = next;
}
head= newNode;
}
void linkedList::print()
{
node *cur = head;
while (cur != NULL)
{
cout << cur->data << " " << endl;
cur = cur->next;
}
cout << endl;
}
int linkedList::size()
{
node *cur = head;
int count = 0;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
-------------------------------------------------
//main file
#include<iostream>
#include"Sep_23_linkedList.h"
using namespace std;
int main()
{
linkedList list;
list.Push(10);
list.Push(4);
list.Push(14);
list.Push(9);
list.Push(3);
//list.Push(1);
//print linked list
cout << "Before sorting: " << endl;
list.print();
list.insertionSort();
cout << "After sorting: " << endl;
list.print();
cout << "Peek: "<<list.Peek()<<" data "<< list.Peek()<<" is popped" << endl;
list.Pop();
cout << "Peek: "<<list.Peek()<<" data "<<list.Peek()<<" is popped" << endl;
list.Pop();
cout << "Peek: " << list.Peek() << endl;
}/*output:
Before sorting:
3
9
14
4
10
After sorting:
3
4
9
10
14
Peek: 3
data 3 is popped
Peek: 4
data 4 is popped
Peek: 9
*/