3. Sorting Implement a generic Stack linked list data structure for integers tha
ID: 3752506 • Letter: 3
Question
3. Sorting Implement a generic Stack linked list data structure for integers that supports these function:s 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. 2. ii. Push(int data), which pushes values to the head of the stack ili. Pop();, which pops values from the head of the stack and returns it iv. Peek(), which returns a value from the head of the stack b. Implement a pastPeek() function such that it always peeks the head of the stack prior to the sort taking place. When the head of the stack is popped from the sorted stack, update peek() to move to where the next head would have been.Explanation / 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
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.