Write a program that sorts a stack of integers in descending order with the smal

Question

Write a program that sorts a stack of integers in descending order with the smallest item on top. You are allowed to use one stack to hold your data and another stack as an auxiliary data structure. You may not use any other data structures such as array etc. to help you solve the problem.
Hint
You have push(), pop(), top() and isEmpty() methods to help you solve the problem.
Input
This program does not need to input any data from the console, instead you create a random number between 0 to 20 and then this number shows you the number of randoms that you should generate as your inputs. Inputs should be between 0 to 50. For example, if the first random number generated is 10, you need to generated 10 more random numbers and push them into the stack for sorting purpose.
Output
You first print the content of the stack and then print the sorted item.
e.g.
Random Number = 13
Initial Stack: [4, 7, 18, 39, 42, 8, 35, 23, 50, 0, 23, 11, 6]
Sorted Stack: [0, 4, 6, 7, 8, 11, 18, 23, 23, 35, 39, 42, 50]

Explanation / Answer

// C program to sort a stack using recursion
#include <stdio.h>
#include <stdlib.h>
#include<time.h>

// Stack is represented using linked list
struct stack
{
int data;
struct stack *next;
};

// Utility function to initialize stack
void initStack(struct stack **s)
{
*s = NULL;
}

// Utility function to chcek if stack is empty
int isEmpty(struct stack *s)
{
if (s == NULL)
return 1;
return 0;
}

// Utility function to push an item to stack
void push(struct stack **s, int x)
{
struct stack *p = (struct stack *)malloc(sizeof(*p));

if (p == NULL)
{
fprintf(stderr, "Memory allocation failed. ");
return;
}

p->data = x;
p->next = *s;
*s = p;
}

// Utility function to remove an item from stack
int pop(struct stack **s)
{
int x;
struct stack *temp;

x = (*s)->data;
temp = *s;
(*s) = (*s)->next;
free(temp);

return x;
}

// Function to find top item
int top(struct stack *s)
{
return (s->data);
}

// Recursive function to insert an item x in sorted way
void sortedInsert(struct stack **s, int x)
{
// Base case: Either stack is empty or newly inserted
// item is greater than top (more than all existing)
if (isEmpty(*s) || x > top(*s))
{
push(s, x);
return;
}

// If top is greater, remove the top item and recur
int temp = pop(s);
sortedInsert(s, x);

// Put back the top item removed earlier
push(s, temp);
}

// Function to sort stack
void sortStack(struct stack **s)
{
// If stack is not empty
if (!isEmpty(*s))
{
// Remove the top item
int x = pop(s);

// Sort remaining stack
sortStack(s);

// Push the top item back in sorted stack
sortedInsert(s, x);
}
}

// Utility function to print contents of stack
void printStack(struct stack *s)
{
while (s)
{
printf("%d ", s->data);
s = s->next;
}
printf(" ");
}

// Driver Program
int main(void)
{
struct stack *top;
int randomvalue;
srand(time(NULL));
randomvalue=(rand()%(20+1-0))+0; // generate the randam value(0-20) and store it in a variable.
printf("%d ",randomvalue);
initStack(&top);
int loopcontrol=0;
int secondrand=0;
for(loopcontrol=0;loopcontrol<randomvalue;loopcontrol++)
{   
   secondrand=(rand()%(50 + 1 - 0)) + 0;
push(&top,secondrand);

}

printf("Stack elements before sorting: ");
printStack(top);

sortStack(&top);
printf(" ");

printf("Stack elements after sorting: ");
printStack(top);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.