题目

用栈实现队列
虽然感觉这道题有点多此一举,比如用一个切片就可以完成,而且代码更简洁
准确说用两个切片数组来当栈
压栈的时候不做判断,
pop的时候,判断outstack是否为空,不为空就直接从outstack里删除最后一个元素
为空就从instack里颠倒元素到outstack,然后返回outstack栈顶元素
peek的时候,也是先做判断,如果outstack里面有元素,就直接从这里面返回元素,
如果没有,就把instack里把元素移动到outstack
这里面有几个注意事项, 移动元素的时候,一定要倒序遍历,否则顺序是错的

代码题解

type MyQueue struct {
    instack []int
    outstack []int
}


func Constructor() MyQueue {
    return MyQueue{
        instack:  make([]int, 0),
        outstack: make([]int, 0),
    }
}

func (this *MyQueue) Push(x int) {
    // 压栈
    this.instack = append(this.instack, x)
}

func (this *MyQueue) Pop() int {
    // 判断outstack是否为空
    if len(this.outstack) != 0 {
        // 将栈顶元素弹出
        ret := this.outstack[len(this.outstack)-1]
        //fmt.Println(this.outstack)
        this.outstack = this.outstack[:len(this.outstack)-1]
        return ret
    }
    if len(this.instack) != 0 {
        for i := len(this.instack) - 1; i >= 0; i-- {
            this.outstack = append(this.outstack, this.instack[i])
        }
        this.instack = []int{}
    }
    ret := this.outstack[len(this.outstack)-1]
    this.outstack = this.outstack[:len(this.outstack)-1]
    return ret
}

func (this *MyQueue) Peek() int {
    // 返回队列开头的元素
    // 判断outstack是否为空
    if len(this.outstack) != 0 {
        // 返回栈顶元素
        ret := this.outstack[len(this.outstack)-1]
        return ret
    } else {
        // 要把元素搬家,给instack元素移动到outstack,然后返回栈顶元素
        for i := len(this.instack) - 1; i >= 0; i-- {
            this.outstack = append(this.outstack, this.instack[i])
        }
        this.instack = []int{}
        ret := this.outstack[len(this.outstack)-1]
        return ret
    }

}

func (this *MyQueue) Empty() bool {
    return len(this.outstack) == 0 && len(this.instack) == 0
}
func (this *MyQueue) Show() {
    fmt.Println("\n------------instack:", this.instack)
    fmt.Println("------------outstack:", this.outstack)
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:460579 人次
ICP备案号: 辽ICP备20003309号