Back to Repositories

Testing Queue Implementation Patterns in hello-algo

This test suite validates queue implementations in Go, covering both array-based and linked list-based queue structures. It includes comprehensive testing of basic queue operations, performance benchmarking, and edge cases.

Test Coverage Overview

The test suite provides extensive coverage of queue operations including:

Basic queue operations (push, pop, peek)
Empty queue handling
Circular array implementation testing
Size and capacity management
Performance comparison between array and linked list implementations

Implementation Analysis

The testing approach implements three distinct test functions focusing on different queue implementations:

Standard Go list package usage as queue
Custom array-based queue implementation
Custom linked list queue implementation

Each implementation is validated through systematic operation testing and performance benchmarking.

Technical Details

Testing infrastructure includes:

Go testing package (testing.T and testing.B)
Container/list package for standard queue implementation
Custom queue interfaces and implementations
Benchmark functions for performance analysis
Helper functions for queue visualization and debugging

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Comprehensive edge case coverage
Performance benchmarking comparisons
Clear test structure and organization
Proper error handling and validation
Consistent testing patterns across implementations

krahets/hello-algo

zh-hant/codes/go/chapter_stack_and_queue/queue_test.go

            
// File: queue_test.go
// Created Time: 2022-11-28
// Author: Reanon ([email protected])

package chapter_stack_and_queue

import (
	"container/list"
	"fmt"
	"testing"

	. "github.com/krahets/hello-algo/pkg"
)

func TestQueue(t *testing.T) {
	/* 初始化佇列 */
	// 在 Go 中，將 list 作為佇列來使用
	queue := list.New()

	/* 元素入列 */
	queue.PushBack(1)
	queue.PushBack(3)
	queue.PushBack(2)
	queue.PushBack(5)
	queue.PushBack(4)
	fmt.Print("佇列 queue = ")
	PrintList(queue)

	/* 訪問佇列首元素 */
	peek := queue.Front()
	fmt.Println("佇列首元素 peek =", peek.Value)

	/* 元素出列 */
	pop := queue.Front()
	queue.Remove(pop)
	fmt.Print("出列元素 pop = ", pop.Value, "，出列後 queue = ")
	PrintList(queue)

	/* 獲取佇列的長度 */
	size := queue.Len()
	fmt.Println("佇列長度 size =", size)

	/* 判斷佇列是否為空 */
	isEmpty := queue.Len() == 0
	fmt.Println("佇列是否為空 =", isEmpty)
}

func TestArrayQueue(t *testing.T) {

	// 初始化佇列，使用佇列的通用介面
	capacity := 10
	queue := newArrayQueue(capacity)
	if queue.pop() != nil {
		t.Errorf("want:%v,got:%v", nil, queue.pop())
	}

	// 元素入列
	queue.push(1)
	queue.push(3)
	queue.push(2)
	queue.push(5)
	queue.push(4)
	fmt.Print("佇列 queue = ")
	PrintSlice(queue.toSlice())

	// 訪問佇列首元素
	peek := queue.peek()
	fmt.Println("佇列首元素 peek =", peek)

	// 元素出列
	pop := queue.pop()
	fmt.Print("出列元素 pop = ", pop, ", 出列後 queue = ")
	PrintSlice(queue.toSlice())

	// 獲取隊的長度
	size := queue.size()
	fmt.Println("隊的長度 size =", size)

	// 判斷是否為空
	isEmpty := queue.isEmpty()
	fmt.Println("隊是否為空 =", isEmpty)

	/* 測試環形陣列 */
	for i := 0; i < 10; i++ {
		queue.push(i)
		queue.pop()
		fmt.Print("第", i, "輪入列 + 出列後 queue =")
		PrintSlice(queue.toSlice())
	}
}

func TestLinkedListQueue(t *testing.T) {
	// 初始化隊
	queue := newLinkedListQueue()

	// 元素入列
	queue.push(1)
	queue.push(3)
	queue.push(2)
	queue.push(5)
	queue.push(4)
	fmt.Print("佇列 queue = ")
	PrintList(queue.toList())

	// 訪問佇列首元素
	peek := queue.peek()
	fmt.Println("佇列首元素 peek =", peek)

	// 元素出列
	pop := queue.pop()
	fmt.Print("出列元素 pop = ", pop, ", 出列後 queue = ")
	PrintList(queue.toList())

	// 獲取隊的長度
	size := queue.size()
	fmt.Println("隊的長度 size =", size)

	// 判斷是否為空
	isEmpty := queue.isEmpty()
	fmt.Println("隊是否為空 =", isEmpty)
}

// BenchmarkArrayQueue 8 ns/op in Mac M1 Pro
func BenchmarkArrayQueue(b *testing.B) {
	capacity := 1000
	queue := newArrayQueue(capacity)
	// use b.N for looping
	for i := 0; i < b.N; i++ {
		queue.push(777)
	}
	for i := 0; i < b.N; i++ {
		queue.pop()
	}
}

// BenchmarkLinkedQueue 62.66 ns/op in Mac M1 Pro
func BenchmarkLinkedQueue(b *testing.B) {
	queue := newLinkedListQueue()
	// use b.N for looping
	for i := 0; i < b.N; i++ {
		queue.push(777)
	}
	for i := 0; i < b.N; i++ {
		queue.pop()
	}
}