0%

由两个栈组成的队列

【题目】

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

【难度】

★★☆☆

【解答】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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() {
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 {
return -1,errors.New("Your queue is empty")
}
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 {
return -1,errors.New("Your queue is empty")
}
num := q.stackPop.Front().Value.(*list.Element).Value.(int64)
return num,nil
}