This program sorts a stack of integers in ascending order using an additional stack. The main idea behind this method is to use the second stack as a temporary storage to reorder the elements such that the smallest elements end up on the top of the original stack.

Program Code

package main

import (
    "fmt"
)

// Stack type using a slice for storage
type Stack struct {
    elements []int
}

// Push a value onto the stack
func (s *Stack) Push(value int) {
    s.elements = append(s.elements, value)
}

// Pop removes the top element of the stack and returns it
func (s *Stack) Pop() int {
    if len(s.elements) == 0 {
        return -1 // Consider -1 as stack underflow
    }
    result := s.elements[len(s.elements)-1]
    s.elements = s.elements[:len(s.elements)-1]
    return result
}

// Peek returns the top element without removing it
func (s *Stack) Peek() int {
    if len(s.elements) == 0 {
        return -1 // Consider -1 as stack underflow
    }
    return s.elements[len(s.elements)-1]
}

// IsEmpty checks if the stack is empty
func (s *Stack) IsEmpty() bool {
    return len(s.elements) == 0
}

// SortStack sorts the original stack using a temporary stack
func SortStack(original *Stack) {
    tempStack := &Stack{make([]int, 0)}
    for !original.IsEmpty() {
        // Take the top element
        current := original.Pop()
        // While temporary stack is not empty and top of temporary stack is less than the current element
        for !tempStack.IsEmpty() && tempStack.Peek() > current {
            original.Push(tempStack.Pop())
        }
        // Push the current element onto the temporary stack
        tempStack.Push(current)
    }

    // Move the sorted elements back to the original stack
    for !tempStack.IsEmpty() {
        original.Push(tempStack.Pop())
    }
}

func main() {
    originalStack := &Stack{[]int{34, 3, 31, 98, 92, 23}}
    fmt.Println("Original stack:", originalStack.elements)
    SortStack(originalStack)
    fmt.Println("Sorted stack:", originalStack.elements)
}

Explanation

• Stack Operations: Basic stack operations such as Push, Pop, and Peek are implemented within the Stack struct to manage stack elements using slices.
• Sorting Mechanism: Elements are moved between the original and temporary stacks to sort them. If the temporary stack’s top element is less than the element being processed, it is moved back to the original stack to find the correct position for the processed element in the temporary stack.
• Reassembly: After all elements are processed and sorted in the temporary stack, they are moved back to the original stack to maintain the order from the smallest to largest when popped.

Running the Program

To execute the above program:

1. Save the code in a file with a .go extension, such as sortstack.go.
2. Open a terminal or command prompt.
3. Navigate to the directory containing your file.
4. Run the command go run sortstack.go.

The output will demonstrate the original stack and the stack after sorting, showing that the elements are sorted in ascending order when popped from the stack. Adjust the stack contents in the main function to test different scenarios.