程序员面试金典03.05_go_栈排序题目栈排序。编写程序

题目【程序员面试金典03.05_go_栈排序】栈排序。编写程序，对栈进行排序使最小元素位于栈顶。
最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
该栈支持如下操作：push、pop、peek 和 isEmpty 。当栈为空时， peek 返回 -1 。
示例1:输入：["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：[null,null,null,1,null,2]
示例2:输入： ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：[null,null,null,null,null,true]
说明:栈中的元素数目在[0, 5000]范围内。
解题思路分析1、双栈；时间复杂度O(n) ，空间复杂度O(n)
文章插图
type SortedStack struct { stack []int temp[]int}func Constructor() SortedStack { return SortedStack{}}func (this *SortedStack) Push(val int) { for len(this.stack) > 0 && val >= this.stack[len(this.stack)-1] {this.temp = append(this.temp, this.stack[len(this.stack)-1])this.stack = this.stack[:len(this.stack)-1] } this.stack = append(this.stack, val) for len(this.temp) > 0 {this.stack = append(this.stack, this.temp[len(this.temp)-1])this.temp = this.temp[:len(this.temp)-1] }}func (this *SortedStack) Pop() { if len(this.stack) == 0 {return } this.stack = this.stack[:len(this.stack)-1]}func (this *SortedStack) Peek() int { if len(this.stack) == 0 {return -1 } return this.stack[len(this.stack)-1]}func (this *SortedStack) IsEmpty() bool { return len(this.stack) == 0}总结Medium题目，根据题目意思，使用双栈，核心是：push的时候，借助辅助栈来插入数字