JZ29 用两个栈实现队列 (opens new window)

这道题看着扑朔迷离，按着官方的题解来的，这删除时间复杂度是 O*(n)*

package main

import "fmt"

var stack1 []int
var stack2 []int

func Push(node int) {
	stack1 = append(stack1, node)
}

func Pop() int {
	stack2 = []int{}
	for len(stack1) != 0 {
		stack2 = append(stack2, stack1[len(stack1)-1])
		stack1 = stack1[:len(stack1)-1]
	}
	v := stack2[len(stack2)-1]
	stack2 = stack2[:len(stack2)-1]
	stack1 = []int{}
	for len(stack2) != 0 {
		stack1 = append(stack1, stack2[len(stack2)-1])
		stack2 = stack2[:len(stack2)-1]
	}
	return v
}

func main() {
	Push(1)
	Push(2)
	fmt.Println(Pop())
	fmt.Println(Pop())
}

JZ30 包含min函数的栈 (opens new window)

思路

栈操作简单，关键难点在取最小值，很巧妙的一个办法，假设第一个入栈元素最小，然后入栈一个，和前面的最小值比较，用单独的一个栈存储这个最小值，形成如此的关系：min(min(min(a,b),c),d)

这是官方提供的图示：

代码

package main

import "fmt"

type DataType = int
type Node struct {
	Data DataType
	Next *Node
}
type Stack struct {
	Head *Node
}

func NewStack() *Stack {
	stack := new(Stack)
	stack.Head = &Node{}
	return stack
}

func (s *Stack) Push(d DataType) {
	newNode := &Node{Data: d}
	newNode.Next = s.Head.Next
	s.Head.Next = newNode
}
func (s *Stack) Pop() DataType {
	if s.Head.Next == nil {
		panic(nil)
	}
	node := s.Head.Next
	s.Head.Next = node.Next
	return node.Data
}
func (s *Stack) Top() DataType {
	if s.Head.Next == nil {
		panic(nil)
	}
	return s.Head.Next.Data
}
func (s *Stack) Empty() bool {
	return s.Head.Next == nil
}

var stack = NewStack()
var seqStack = NewStack()

func Push(node int) {
	stack.Push(node)
	if seqStack.Empty() {
		seqStack.Push(node)
	} else {
		min := seqStack.Top()
		if node < min {
			seqStack.Push(node)
		} else {
			seqStack.Push(min)
		}
	}
}
func Pop() {
	stack.Pop()
	seqStack.Pop()
}
func Top() int {
	return stack.Top()
}
func Min() int {
	return seqStack.Top()
}

func main() {
	Push(-1)
	Push(2)
	fmt.Println(Min())
	fmt.Println(Top())
	Pop()
	Push(-1)
	fmt.Println(Top())
	fmt.Println(Min())
}