队列

 1package Queue
 2type MyQueue interface {
 3   Size() int                //大小
 4   Front() interface{}       //第一个元素
 5   End() interface{}         //最后一个
 6   IsEmpty() bool            //是否为空
 7   EnQueue(data interface{}) //入队
 8   DeQueue() interface{}     //出队
 9   Clear()                   //清空
10}
11
12type Queue struct {
13   dataStore []interface{} //队列的数据存储
14   theSize   int           //队列的大小
15}
16
17func NewQueue() *Queue {
18   myqueue := new(Queue) //初始化，开辟结构体
19   myqueue.dataStore = make([]interface{}, 0)
20   myqueue.theSize = 0
21   return myqueue
22}
23
24func (myq *Queue) Size() int {
25   return myq.theSize
26}
27
28//取出第一个
29func (myq *Queue) Front() interface{} {
30   if myq.Size() == 0 {
31      return nil
32   }
33   return myq.dataStore[0]
34}
35//取出最后一个
36func (myq *Queue) End() interface{} {
37   if myq.Size() == 0 {
38      return nil
39   }
40   return myq.dataStore[myq.Size()-1]
41}
42
43func (myq *Queue) IsEmpty() bool {
44   return myq.theSize == 0
45}
46
47func (myq *Queue) EnQueue(data interface{}) {
48   myq.dataStore = append(myq.dataStore, data) //入队
49   myq.theSize++
50}
51
52func (myq *Queue) DeQueue() interface{} {
53   if myq.Size() == 0 {
54      return nil
55   }
56   data := myq.dataStore[0]
57   if myq.Size() > 1 {
58      myq.dataStore = myq.dataStore[1:myq.Size()]
59   } else {
60      myq.dataStore = make([]interface{}, 0)
61   }
62   myq.theSize--
63   return data //返回数据
64}
65
66func (myq *Queue) Clear() {
67   myq.dataStore = make([]interface{}, 0)
68   myq.theSize = 0
69}

 1package main
 2
 3import (
 4	"Queue"
 5	"fmt"
 6)
 7
 8func main() {
 9	myq := Queue.NewQueue()
10	myq.EnQueue(1)
11	myq.EnQueue(2)
12	myq.EnQueue(3)
13	myq.EnQueue(4)
14	fmt.Println(myq.DeQueue())
15	fmt.Println(myq.DeQueue())
16	fmt.Println(myq.DeQueue())
17	fmt.Println(myq.DeQueue())
18	myq.EnQueue(14)
19	myq.EnQueue(114)
20	fmt.Println(myq.DeQueue())
21	fmt.Println(myq.DeQueue())
22	myq.EnQueue(11114)
23	fmt.Println(myq.DeQueue())
24}

 1package queue
 2
 3import "errors"
 4
 5//循环队列
 6const QueueSize = 5 //最多存储QueueSize-1个数据
 7//空一个空格标识满格
 8type CricleQueue struct {
 9	data  [QueueSize]interface{} //存储数据的结构
10	front int                    //头部的位置
11	rear  int                    //尾部的位置
12}
13
14func InitQueue(q *CricleQueue) { //初始化，头部尾部重合，为空
15	q.front = 0
16	q.rear = 0
17}
18func Queuelength(q *CricleQueue) int { //队列长度
19	return (q.rear - q.front + QueueSize) % QueueSize
20}
21func EnQueue(q *CricleQueue, data interface{}) (err error) {
22	if (q.rear+1)%QueueSize == q.front%QueueSize {
23		return errors.New("队列已经满了")
24	}
25	q.data[q.rear] = data             //入队
26	q.rear = (q.rear + 1) % QueueSize //循环 6，1
27	return nil
28}
29
30func DeQueue(q *CricleQueue) (data interface{}, err error) {
31	if q.rear == q.front {
32		return nil, errors.New("队列为空")
33	}
34	res := q.data[q.front]              //取出第一个数据
35	q.data[q.front] = 0                 //清空数据
36	q.front = (q.front + 1) % QueueSize //小于5  + 1，6回到1的位置
37	return res, nil
38}

 1package queue
 2
 3type Node struct {
 4	data  interface{}
 5	pNext *Node
 6}
 7
 8// 链表队列
 9type QueueLink struct {
10	rear  *Node
11	front *Node
12}
13
14type LinkQueue interface {
15	length() int
16	Enqueue(value interface{})
17	Dequeue() interface{}
18}
19
20func NewLinkQueue() *QueueLink {
21	return &QueueLink{}
22}
23
24func (qlk *QueueLink) length() int {
25	pnext := qlk.front
26	length := 0
27	for pnext.pNext != nil {
28		pnext = pnext.pNext //节点循环跳跃
29		length++            //追加
30	}
31	return length //返回长度
32}
33func (qlk *QueueLink) Enqueue(value interface{}) {
34	newnode := &Node{value, nil} //新节点
35	if qlk.front == nil {
36		qlk.front = newnode //插入接一个节点
37		qlk.rear = newnode
38	} else {
39		qlk.rear.pNext = newnode
40		qlk.rear = qlk.rear.pNext
41	}
42
43}
44func (qlk *QueueLink) Dequeue() interface{} {
45	if qlk.front == nil {
46		return nil
47	}
48	newnode := qlk.front       //记录头部位置
49	if qlk.front == qlk.rear { //只剩下一个
50		qlk.front = nil
51		qlk.rear = nil
52	} else {
53		qlk.front = qlk.front.pNext //删除一个
54	}
55	return newnode.data
56
57}

 1package queue
 2
 3import "testing"
 4
 5func TestLinkQueue(t *testing.T) {
 6	myq := NewLinkQueue()
 7	for i := 1; i < 10000000; i++ {
 8		myq.Enqueue(i)
 9	}
10	for data := myq.Dequeue(); data != nil; data = myq.Dequeue() {
11		t.Log(data)
12	}
13}