This program demonstrates how to sort the elements in a stack using another temporary stack. The idea is to use the main stack for pushing elements and another stack to temporarily hold elements in sorted order. At the end of the process, the elements in the stack will be in ascending order.

Program Explanation

The algorithm involves transferring elements between two stacks in such a way that we maintain a sorted order in the auxiliary (temporary) stack. The process works as follows:

1. Pop an element from the original stack.
2. While the temporary stack is not empty and the top of the temporary stack is greater than the popped element:
   • Pop elements from the temporary stack and push them back into the original stack.
3. Push the popped element from the original stack into the temporary stack.
4. Repeat the process until the original stack is empty.

At the end of the process, the temporary stack will contain the elements in sorted order (ascending).

C Program Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Stack structure
struct Stack {
    int arr[MAX];
    int top;
};

// Initialize the stack
void initStack(struct Stack *s) {
    s->top = -1;
}

// Check if stack is full
int isFull(struct Stack *s) {
    return s->top == MAX - 1;
}

// Check if stack is empty
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// Push an element onto the stack
void push(struct Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
}

// Pop an element from the stack
int pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

// Peek the top element of the stack
int peek(struct Stack *s) {
    if (isEmpty(s)) {
        return -1;
    }
    return s->arr[s->top];
}

// Function to sort elements in a stack using another stack
void sortStack(struct Stack *s) {
    struct Stack tempStack;
    initStack(&tempStack);

    while (!isEmpty(s)) {
        // Pop an element from the original stack
        int current = pop(s);

        // While temporary stack is not empty and top of temp stack is greater than current
        while (!isEmpty(&tempStack) && peek(&tempStack) > current) {
            push(s, pop(&tempStack));
        }

        // Push current element onto the temporary stack
        push(&tempStack, current);
    }

    // Transfer sorted elements back into the original stack
    while (!isEmpty(&tempStack)) {
        push(s, pop(&tempStack));
    }
}

// Function to display stack elements
void displayStack(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return;
    }

    printf("Stack elements (top to bottom): ");
    for (int i = s->top; i >= 0; i--) {
        printf("%d ", s->arr[i]);
    }
    printf("\n");
}

// Main driver function
int main() {
    struct Stack s;
    initStack(&s);

    // Pushing some elements onto the stack
    push(&s, 34);
    push(&s, 3);
    push(&s, 31);
    push(&s, 98);
    push(&s, 92);
    push(&s, 23);

    printf("Original stack:\n");
    displayStack(&s);

    // Sorting the stack
    sortStack(&s);

    printf("\nSorted stack:\n");
    displayStack(&s);

    return 0;
}
    

Code Explanation

1. Stack Structure: The program defines a stack structure using an array and an integer to represent the top of the stack. The stack can hold a maximum of MAX elements, where MAX is defined as 100.

2. Basic Stack Operations:

• push() – Adds an element to the top of the stack if it’s not full.
• pop() – Removes the top element from the stack if it’s not empty.
• peek() – Returns the top element without removing it.
• isEmpty() and isFull() – Check if the stack is empty or full, respectively.

3. Sorting Function:
The sortStack() function is the core of the program. It sorts the elements of the stack using an additional temporary stack:

• The function pops elements from the original stack and compares them with the top of the temporary stack.
• Elements from the temporary stack are moved back to the original stack if they are larger than the current element.
• Once the correct position is found, the current element is pushed onto the temporary stack.
• Finally, the sorted elements are pushed back from the temporary stack to the original stack.

4. Display Function:
The displayStack() function prints the contents of the stack from top to bottom. It traverses the stack and prints each element.

Sample Output

Original stack:
Stack elements (top to bottom): 23 92 98 31 3 34 

Sorted stack:
Stack elements (top to bottom): 3 23 31 34 92 98 
    

Conclusion

This program efficiently sorts a stack using another temporary stack. The sorting algorithm is based on transferring elements between the original stack and the temporary stack while maintaining the sorted order. This approach allows for sorting with minimal extra space (just one additional stack) and ensures that the original stack is sorted in ascending order.