【栈与队列】由两个栈组成的队列

xmge · 2020-04-11 21:00:13 · 1846 次点击 · 预计阅读时间 2 分钟 · 大约8小时之前开始浏览

这是一个创建于 2020-04-11 21:00:13 的文章，其中的信息可能已经有所发展或是发生改变。

【题目】

编写一个结构体，用两个栈实现队列，支持队列的基本操作（push、poll、peek）

【难度】

★★☆☆

【解答】

package main

import (
    "container/list"
    "errors"
    "fmt"
)

func main() {
    q := NewQueue()
    q.Push(1)
    fmt.Println(q.Peek())
    q.Push(2)
    fmt.Println(q.Peek())
    fmt.Println(q.Poll())
    fmt.Println(q.Peek())
    fmt.Println(q.Poll())
    fmt.Println(q.Poll())
    fmt.Println(q.Peek())
}

type TwoStackQueue struct {
    stackPush *list.List
    stackPop *list.List
}

func NewQueue() *TwoStackQueue {
    queue := new(TwoStackQueue)
    queue.stackPush = list.New().Init()
    queue.stackPop = list.New().Init()
    return queue
}

func (q *TwoStackQueue)pushToPop()  {
    if q.stackPop.Len() == 0 {
        for q.stackPush.Len() != 0 {
            q.stackPop.PushFront(q.stackPush.Front())
            q.stackPush.Remove(q.stackPush.Front())
        }
    }
}

func (q *TwoStackQueue)Push(num int64)  {
    q.stackPush.PushFront(num)
    q.pushToPop()
}

func (q *TwoStackQueue)Poll() (int64,error) {
    if q.stackPop.Len() == 0 && q.stackPush.Len() == 0{
        return -1,errors.New("Your queue is empty")
    }
    q.pushToPop()
    num := q.stackPop.Front().Value.(*list.Element).Value.(int64)
    q.stackPop.Remove(q.stackPop.Front())
    return num,nil
}

func (q *TwoStackQueue)Peek() (int64,error) {
    if q.stackPop.Len() == 0 && q.stackPush.Len() == 0{
        return -1,errors.New("Your queue is empty")
    }
    q.pushToPop()
    num := q.stackPop.Front().Value.(*list.Element).Value.(int64)
    return num,nil
}