This program demonstrates a special stack that supports standard push and pop operations and can also return the minimum element in constant time. The stack utilizes an auxiliary stack that tracks the minimum values efficiently.

Program Code

package main

import (
    "fmt"
    "math"
)

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack:    make([]int, 0),
        minStack: make([]int, 0),
    }
}

func (this *MinStack) Push(x int) {
    this.stack = append(this.stack, x)
    min := x
    if len(this.minStack) > 0 && this.minStack[len(this.minStack)-1] < x {
        min = this.minStack[len(this.minStack)-1]
    }
    this.minStack = append(this.minStack, min)
}

func (this *MinStack) Pop() {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

func main() {
    minStack := Constructor()
    minStack.Push(-2)
    minStack.Push(0)
    minStack.Push(-3)
    fmt.Println("Current Minimum:", minStack.GetMin())  // Returns -3
    minStack.Pop()
    fmt.Println("Top element:", minStack.Top())          // Returns 0
    fmt.Println("Current Minimum:", minStack.GetMin())  // Returns -2
}

Explanation

• Structure: The MinStack structure includes two slices: one for the stack itself and another for keeping track of the minimum values.
• Stack Operations:
  • Push operation adds an element to the main stack and updates the minimum stack. If the new element is less than the current minimum, it becomes the new minimum; otherwise, the current minimum is repeated.
  • Pop operation removes the top element from both the main stack and the minimum stack, thus maintaining the minimum tracking accurately.
  • Top returns the top element of the main stack without removing it.
  • GetMin returns the top element of the minimum stack, which is the minimum element of the main stack.

Running the Program

To execute this Go program:

1. Save the code in a file named minstack.go.
2. Open a terminal or command prompt.
3. Navigate to the directory where the file is stored.
4. Run the program by typing go run minstack.go.

The output will demonstrate the functionality of the special stack, showing how the minimum value can be retrieved in constant time even as elements are pushed and popped from the stack. Adjust the main function to test different inputs and observe how the stack maintains the minimum value efficiently.