栈与队列-1-设计一个有getMin功能的栈

设计一个有getMin功能的栈

题目

实现一个特殊功能的栈，在满足栈的基本功能的条件下，提供返回栈中最小元素的操作。
要求

pop、push、getMin操作的时间复杂度为O(1)
实现思路:

使用两个栈实现需求，一个栈用来保存正常栈的数据信息stackData，一个栈保存每一步的最小值stackMin。由stackData栈实现正常的pop和push，由stackMin栈实现获取当前栈的最小值。
实现方案
- 方案一
  
  对于stackMin保存每一步最小值，可以使用比较法进行保存，如果当前押入stackData的值小于等于stackMin栈顶的值，则将押入的数据保存stackMin栈中，大于stackMin栈顶的值，只押入stackData中。如果stackMin为空，则双栈都押入。弹出数据时，如果stackData弹出的数据等于当前stackMin栈顶元素，则stackMin栈顶元素也要弹出，即同步弹出。获取当前栈的最小值，直接获取stackMin栈顶元素即可。
- 方案二
  
  stackMin栈数据重复保存法。将数据押入stackData栈中，如果押入栈中的数据小于等于stackMin栈顶元素，则stackData和stackMin都押入当前元素。如果押入栈中的数据大于stackMin栈顶元素，则获取stackMin栈顶元素，重复押入。如果stackMin栈为空，则直接将数据押入stackMin栈和stackData栈中。该方案以空间换取了部分比较的操作，对于弹出操作，双栈弹出即可。获取当前栈最小值方式同上。

go实现代码

方案一实现

package main

import (
	"errors"
)

// 定义接口，要求实现push pop getMin三个方法
type GetMin interface{
	push(int)
	pop() (int, error)
	getMin() (int, error)
}

// 定义结构体，有存储数据的栈 保存最小值的栈
type GetMinStack struct {
	stackDate []int
	stackMin []int
}

// 使结构体实现所有方法，即GetMinStack结构体实现GetMin全部接口
// 数据押入
func (s *GetMinStack) push(num int) {
	// 实现押入方法
	s.stackDate = append(s.stackDate, num)
	if len(s.stackMin) == 0 {
		s.stackMin = append(s.stackMin, num)
	} else {
		// 取出最后一个
		if last := s.stackMin[len(s.stackMin)-1]; num <= last {
			s.stackMin = append(s.stackMin, num)
		}
	}
}

// 数据弹出
func (s *GetMinStack) pop()(num int, err error) {
	// 弹出最后一个元素
	length := len(s.stackDate)
	if length == 0 {
		return num, errors.New("stack is empty")
	}
	num = s.stackDate[length-1]
	if last := s.stackMin[len(s.stackMin)-1]; last == num {
		s.stackMin = s.stackMin[:len(s.stackMin)-1]
	}
	s.stackDate = s.stackDate[:length-1]
	return num, nil
}

// 获取当前栈中最小值
func (s *GetMinStack) getMin() (num int, err error){
	// 获取最小值
	if length := len(s.stackMin); length <= 0 {
		return num, errors.New("statck is empty")
	}
	num = s.stackMin[len(s.stackMin)-1]
	return num, nil
}

func main() {
	// 设计一个具有获取最小值的stack
	m := new(GetMinStack)
	m.stackMin = []int{}
	m.stackDate = []int{}
	var n GetMin = m
	n.push(2)
	n.push(2)
	n.push(3)
	n.push(4)
	n.push(1)
	fmt.Println(m.stackDate, m.stackMin)
	mindata, err := n.getMin()
	fmt.Println(mindata, err)
	data,err := n.pop()
	fmt.Println(data, err)
	fmt.Println(m.stackDate, m.stackMin)
	data1, err := n.pop()
	fmt.Println(data1, err)
	fmt.Println(m.stackDate, m.stackMin)
	data2, err := n.pop()
	fmt.Println(data2, err)
	fmt.Println(m.stackDate, m.stackMin)
	data3, err := n.pop()
	fmt.Println(data3, err)
	fmt.Println(m.stackDate, m.stackMin)
	data4, err := n.pop()
	fmt.Println(data4, err)
	mindata1, err := n.getMin()
	fmt.Println(mindata1, err)
}
// 输出结果
    [2 2 3 4 1] [2 2 1]
    1 <nil>
    1 <nil>
    [2 2 3 4] [2 2]
    4 <nil>
    [2 2 3] [2 2]
    3 <nil>
    [2 2] [2 2]
    2 <nil>
    [2] [2]
    2 <nil>
    0 statck is empty
符合预期

方案二实现

package main

import (
	"errors"
	"fmt"
)

type GetMin interface{
	push(int)
	pop() (int, error)
	getMin() (int, error)
}

type GetMinStack struct {
	stackDate []int
	stackMin []int
}

// 方法二 押入时，判断最小栈的值。进行重复押入
func (s *GetMinStack) push(num int) {
	// 实现押入方法
	s.stackDate = append(s.stackDate, num)
	if len(s.stackMin) == 0 {
		s.stackMin = append(s.stackMin, num)
	} else {
		// 取出最后一个
		last := s.stackMin[len(s.stackMin)-1]
		if num <= last {
			s.stackMin = append(s.stackMin, num)
		} else {
			// 重复押入
			s.stackMin = append(s.stackMin, last)
		}
	}
}

// 弹出时，双栈弹出
func (s *GetMinStack) pop()(num int, err error) {
	// 弹出最后一个元素
	length := len(s.stackDate)
	if length == 0 {
		return num, errors.New("stack is empty")
	}
	num = s.stackDate[length-1]
	s.stackDate = s.stackDate[:length-1]
	s.stackMin = s.stackMin[:len(s.stackMin)-1]
	return num, nil
}

// 获取最小值
func (s *GetMinStack) getMin() (num int, err error){
	// 获取最小值
	if length := len(s.stackMin); length <= 0 {
		return num, errors.New("statck is empty")
	}
	num = s.stackMin[len(s.stackMin)-1]
	return num, nil
}

func main() {
	// 设计一个具有获取最小值的stack
	m := new(GetMinStack)
	m.stackMin = []int{}
	m.stackDate = []int{}
	var n GetMin = m
	n.push(2)
	n.push(2)
	n.push(3)
	n.push(4)
	n.push(1)
	fmt.Println(m.stackDate, m.stackMin)
	mindata, err := n.getMin()
	fmt.Println(mindata, err)
	data,err := n.pop()
	fmt.Println(data, err)
	fmt.Println(m.stackDate, m.stackMin)
	data1, err := n.pop()
	fmt.Println(data1, err)
	fmt.Println(m.stackDate, m.stackMin)
	data2, err := n.pop()
	fmt.Println(data2, err)
	fmt.Println(m.stackDate, m.stackMin)
	data3, err := n.pop()
	fmt.Println(data3, err)
	fmt.Println(m.stackDate, m.stackMin)
	data4, err := n.pop()
	fmt.Println(data4, err)
	mindata1, err := n.getMin()
	fmt.Println(mindata1, err)
}

// 结果如下
    [2 2 3 4 1] [2 2 2 2 1]
    1 <nil>
    1 <nil>
    [2 2 3 4] [2 2 2 2]
    4 <nil>
    [2 2 3] [2 2 2]
    3 <nil>
    [2 2] [2 2]
    2 <nil>
    [2] [2]
    2 <nil>
    0 statck is empty
符合预期

设计一个有getMin功能的栈

~~ 欢迎 ~~

欢迎