leetcode232 用栈实现队列 golang

lucasgao · · 412 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

解题思路

使用栈模拟队列，
栈的特性：先进后出
队列特性：先进先出。

所以可以使用2个栈，S1 pop的数据放到S2那么我们就可以保证 S2 pop出的数据是先进先出的。

代码里没有保证空指针出错。

这里自定义了一个stack，因为go里没有栈，所以用数组进行了模拟，并把栈的相关方法暴露出来。

代码

// 因为go 没有栈这样的数据结果，所以先实现一个栈出来。
type Stack struct{
    A []int
}

func (s *Stack) Push(x int){
    s.A = append(s.A,x)
}

func (s *Stack) Pop()int{
    l := s.Size()
    t := s.A[l-1]
    s.A = s.A[:l-1]
    return t
}

func (s *Stack) Top()int{
    l := s.Size()
    t := s.A[l-1]
    return t
}

func (s *Stack)Size() int{
    return len(s.A)
}

func (s *Stack)Empty()bool{
    return s.Size() == 0
}

type MyQueue struct {
    S1,S2 Stack
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{}
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.S1.Push(x)
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    // 当S2空的时候，需要把S1的数据放到S2中
    if this.S2.Empty(){
        for !this.S1.Empty(){
            t := this.S1.Pop()
            this.S2.Push(t)
        }
    }
    return this.S2.Pop()
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
  // 当S2空的时候，需要把S1的数据放到S2中
    if this.S2.Empty(){
        for !this.S1.Empty(){
            t := this.S1.Pop()
            this.S2.Push(t)
        }
    }
    return this.S2.Top()
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return this.S1.Empty() && this.S2.Empty()
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

有疑问加站长微信联系（非本文作者）