数据结构与算法-队列

一、概述

           队列也是一种表，是一种先进先出、从队头删除、从队尾删除的一种数据结构。队列这种数据结构在实际的项目中用的也是比较多，比如消息中间件 消息队列等。队列的插入我们称为入队操作。从队列中移除我们称为出队操作。队列和栈一样每个操作都是O(1)

 

 

 

            队列的基本操作有:

           1、初始化队列

           2、入队

           3、出队

           4、判空

           5、获取队头元素

          6、获取队尾元素

          7、获取队列的大小

 

 

下面是golang 实现

package queue

import (
	"fmt"
)

// define a node
type Node interface{}

// 队列
type Queue struct {
	Data Node
	Next *Queue
}

func InitQueue() *Queue {

	q := &Queue{}
	q.Next = nil
	return q
}

// 判空
func IsEmpty(q *Queue) bool {

	return q.Next == nil

}

// 入队
func EnQueue(q *Queue, data Node) {

	p := &Queue{}
	p.Data = data
	p.Next = nil

	if q.Next == nil {
		q.Next = p
	} else {
		s := q

		for s.Next != nil {

			s = s.Next
		}
		s.Next = p
	}

}

// 出队
func DeQueue(q *Queue) Node {

	if IsEmpty(q) {
		return nil
	} else {
		s := q.Next

		if s.Next == nil {
			q.Next = nil
		} else {
			q.Next = s.Next

		}
		return s.Data
	}
}

// 大小
func Size(q *Queue) int {

	if IsEmpty(q) {
		return 0
	}

	s := q
	var size int
	for s.Next != nil {
		size++
		s = s.Next
	}

	return size
}

//打印
func Print(q *Queue) {

	if IsEmpty(q) {
		return
	}

	s := q
	for s.Next != nil {

		fmt.Println(s.Data)
		s = s.Next
	}
}

// 头部
func Header(q *Queue) Node {

	if IsEmpty(q) {
		return nil
	}

	return q.Next.Data
}

// 尾部
func Tail(q *Queue) Node {

	if IsEmpty(q) {
		return nil
	}

	s := q
	for s.Next != nil {

		s = s.Next
	}

	return s.Next.Data
}