ALGORITHM SERIES | Dog-Cat Queue
Overview
Requirements
Dog and cat have implemented the Pet interface, you can use getPetType() to view the corresponding animal type; NewDog(), NewCat() can create new dog and cat objects respectively.
1type Pet interface {
2 getPetType() string
3}
4
5type fatherPet struct {
6 Type string
7}
8
9func (fp *fatherPet) getPetType() string {
10 return fp.Type
11}
12
13type Dog struct {
14 fatherPet
15}
16
17func NewDog() *Dog {
18 fmt.Println("new dog")
19 return &Dog{fatherPet{Type: "dog"}}
20}
21
22func (dog *Dog) getPetType() string {
23 return dog.fatherPet.Type
24}
25
26type Cat struct {
27 fatherPet
28}
29
30func NewCat() *Cat {
31 fmt.Println("new cat")
32 return &Cat{fatherPet{Type: "cat"}}
33}
34
35func (cat *Cat) getPetType() string {
36 return cat.fatherPet.Type
37}
You need to implement a dog-cat queue structure with the following requirements:
- the user can call the add method to place instances of the cat class or the dog class into the queue;
- the user can call the pollAll method to pop all the instances in the queue in the order of the queue;
- the user can call the pollDog method to pop the instances of the dog class in the queue in the order in which they entered the queue;
- the user may call the pollCat method to populate the queue with instances of the cat class in the order in which they entered the queue;
- the user can call the isEmpty method to check if there are still instances of dog or cat in the queue
- the user can call the isDogEmpty method to check if there are instances of the dog class in the queue
- the user can call the isCatEmpty method to check if there is an instance of the cat class in the queue.
Solution
According to the question, you need to determine the queue may have dog or cat, with two queues to store dog and cat instances; as for how to determine whether the elements of the dog queue is earlier into the queue or the elements of the cat queue is earlier into the queue need to have a field to store the incoming queue time (globally unique), here you can package a struct to save pet and time;
Then if you want to look at dog, look at dogqueue, if you want to look at cat, look at catqueue; if you want to see the order of the total queue, take the time of the latest element of both dogqueue and catqueue to compare the order of the total queue.
Golang Implementation
Create a new struct ready to be placed in the queue, including the Pet object and the Time field:
1type TimePet struct {
2 Pet Pet
3 Time int
4}
5
6func NewTimePet(pet Pet, time int) *TimePet {
7 return &TimePet{
8 Pet: pet,
9 Time: time,
10 }
11}
12
13func (tp *TimePet) getPet() Pet {
14 return tp.Pet
15}
16
17func (tp *TimePet) getTime() int {
18 return tp.Time
19}
Then the dogcatqueue body includes the following logic:
1type DogCatQueue struct {
2 DogQueue *customQueue
3 CatQueue *customQueue
4 Time int
5}
6
7func NewDogCatQueue() *DogCatQueue {
8 return &DogCatQueue{
9 DogQueue: newCustomQueue(),
10 CatQueue: newCustomQueue(),
11 // Globally unique Time, used to identify the total order
12 Time: 0,
13 }
14}
15
16// Adding is relatively simple, dogs into the dog queue, cats into the cat queue
17func (dcqueue *DogCatQueue) add(pet Pet) {
18 if pet.getPetType() == "dog" {
19 dcqueue.Time++
20 dcqueue.DogQueue.Enqueue(NewTimePet(pet, dcqueue.Time))
21 } else if pet.getPetType() == "cat" {
22 dcqueue.Time++
23 dcqueue.CatQueue.Enqueue(NewTimePet(pet, dcqueue.Time))
24 } else {
25 fmt.Errorf("err, not dog or cat")
26 }
27}
28
29// When pollAll, you need to compare the Time of the latest element of the dog queue and the cat queue who is smaller, who is smaller means who is the first queue
30func (dcqueue *DogCatQueue) pollAll() Pet {
31 if !dcqueue.isDogQueueEmpty() && !dcqueue.isCatQueueEmpty() {
32 if dcqueue.DogQueue.Front().(*TimePet).getTime() < dcqueue.CatQueue.Front().(*TimePet).getTime() {
33 return dcqueue.DogQueue.Dequeue().(*TimePet).getPet()
34 } else {
35 return dcqueue.CatQueue.Dequeue().(*TimePet).getPet()
36 }
37 } else if !dcqueue.isDogQueueEmpty() {
38 return dcqueue.DogQueue.Dequeue().(*TimePet).getPet()
39 } else if !dcqueue.isCatQueueEmpty() {
40 return dcqueue.CatQueue.Dequeue().(*TimePet).getPet()
41 } else {
42 fmt.Errorf("err, dogcatqueue is empty")
43 return nil
44 }
45}
46
47// pollDog can be deleted directly from the dog queue
48func (dcqueue *DogCatQueue) pollDog() Pet {
49 if !dcqueue.isDogQueueEmpty() {
50 fmt.Println("delete latest dog")
51 return dcqueue.DogQueue.Dequeue().(*TimePet).getPet()
52 } else {
53 fmt.Errorf("err, dogcatqueue don't have dog")
54 return nil
55 }
56}
57
58// vice versa
59func (dcqueue *DogCatQueue) pollCat() Pet {
60 if !dcqueue.isCatQueueEmpty() {
61 fmt.Println("delete latest cat")
62 return dcqueue.CatQueue.Dequeue().(*TimePet).getPet()
63 } else {
64 fmt.Errorf("err, dogcatqueue don't have cat")
65 return nil
66 }
67}
68
69func (dcqueue *DogCatQueue) isEmpty() bool {
70 return dcqueue.DogQueue.Empty() && dcqueue.CatQueue.Empty()
71}
72
73func (dcqueue *DogCatQueue) isDogQueueEmpty() bool {
74 return dcqueue.DogQueue.Empty()
75}
76
77func (dcqueue *DogCatQueue) isCatQueueEmpty() bool {
78 return dcqueue.CatQueue.Empty()
79}
Test Cases
1package main
2
3import (
4 "testing"
5
6 "github.com/stretchr/testify/assert"
7)
8
9func TestDogCatQueue(t *testing.T) {
10 // define a getmin stack
11 tests := []struct {
12 name string
13
14 val func(tq *DogCatQueue) []bool
15
16 wantRes []bool
17 }{
18 {
19 name: "operate1",
20 val: operate1,
21 wantRes: []bool{true, false, false},
22 },
23 {
24 name: "operate2",
25 val: operate2,
26 wantRes: []bool{true, false, false},
27 },
28 {
29 name: "operate3",
30 val: operate3,
31 wantRes: []bool{true, true, true},
32 },
33 {
34 name: "operate4",
35 val: operate4,
36 wantRes: []bool{true, true, true},
37 },
38 {
39 name: "operate5",
40 val: operate5,
41 wantRes: []bool{true, true, true},
42 },
43 }
44 for _, tt := range tests {
45 // new TwoStackQueue
46 tq := NewDogCatQueue()
47 // add test cases
48 adddogcat(tq)
49 t.Run(tt.name, func(t *testing.T) {
50 res := tt.val(tq)
51 assert.Equal(t, tt.wantRes, res)
52 })
53 }
54}
55
56func adddogcat(tq *DogCatQueue) {
57 tq.add(NewDog())
58 tq.add(NewCat())
59 tq.add(NewCat())
60 tq.add(NewCat())
61 tq.add(NewDog())
62}
63
64func operate1(tq *DogCatQueue) (queStatus []bool) {
65 tq.pollAll()
66 tq.pollAll()
67 tq.pollCat()
68 tq.pollCat()
69 queStatus = []bool{tq.isCatQueueEmpty(), tq.isDogQueueEmpty(), tq.isEmpty()}
70 return queStatus
71}
72
73func operate2(tq *DogCatQueue) (queStatus []bool) {
74 tq.pollAll()
75 tq.pollAll()
76 tq.pollCat()
77 tq.pollCat()
78 tq.pollCat()
79 queStatus = []bool{tq.isCatQueueEmpty(), tq.isDogQueueEmpty(), tq.isEmpty()}
80 return queStatus
81}
82
83func operate3(tq *DogCatQueue) (queStatus []bool) {
84 tq.pollAll()
85 tq.pollAll()
86 tq.pollCat()
87 tq.pollCat()
88 tq.pollDog()
89 queStatus = []bool{tq.isCatQueueEmpty(), tq.isDogQueueEmpty(), tq.isEmpty()}
90 return queStatus
91}
92
93func operate4(tq *DogCatQueue) (queStatus []bool) {
94 tq.pollAll()
95 tq.pollAll()
96 tq.pollCat()
97 tq.pollCat()
98 tq.pollAll()
99 queStatus = []bool{tq.isCatQueueEmpty(), tq.isDogQueueEmpty(), tq.isEmpty()}
100 return queStatus
101}
102
103func operate5(tq *DogCatQueue) (queStatus []bool) {
104 tq.pollCat()
105 tq.pollCat()
106 tq.pollCat()
107 tq.pollDog()
108 tq.pollDog()
109 queStatus = []bool{tq.isCatQueueEmpty(), tq.isDogQueueEmpty(), tq.isEmpty()}
110 return queStatus
111}
Result:
1$ go test -run ^TestDogCatQueue$ . -v
2=== RUN TestDogCatQueue
3=== RUN TestDogCatQueue/operate1
4=== RUN TestDogCatQueue/operate2
5=== RUN TestDogCatQueue/operate3
6=== RUN TestDogCatQueue/operate4
7=== RUN TestDogCatQueue/operate5
8--- PASS: TestDogCatQueue (0.00s)
9 --- PASS: TestDogCatQueue/operate1 (0.00s)
10 --- PASS: TestDogCatQueue/operate2 (0.00s)
11 --- PASS: TestDogCatQueue/operate3 (0.00s)
12 --- PASS: TestDogCatQueue/operate4 (0.00s)
13 --- PASS: TestDogCatQueue/operate5 (0.00s)
14PASS
15ok dogcatqueue 0.008s
The length is not short, but the difficulty is very low, note that the topic requires not to modify the original data structure, so define a new structure including Time.
What's More: Use Golang Chain Table To Implement Queue
In fact, using slice can also implemente Chain Table, but if the slice is full, the underlying array will be copied once. Using a chain table does not have this problem, the implementation is as follows (accept interface{} as queue elements):
1package main
2
3import (
4 "container/list"
5)
6
7type customQueue struct {
8 queue *list.List
9}
10
11func newCustomQueue() *customQueue {
12 return &customQueue{queue: list.New()}
13}
14
15func (c *customQueue) Enqueue(value interface{}) {
16 c.queue.PushBack(value)
17}
18
19func (c *customQueue) Dequeue() interface{} {
20 if c.queue.Len() > 0 {
21 ele := c.queue.Front()
22 c.queue.Remove(ele)
23 return ele.Value
24 }
25 return nil
26}
27
28func (c *customQueue) Front() interface{} {
29 if c.queue.Len() > 0 {
30 return c.queue.Front().Value
31 }
32 return nil
33}
34
35func (c *customQueue) Size() int {
36 return c.queue.Len()
37}
38
39func (c *customQueue) Empty() bool {
40 return c.queue.Len() == 0
41}
Reference:
https://www.delftstack.com/zh/howto/go/queue-implementation-in-golang/