数据结构与算法 -- 队列

一、队列定义

        先进者先出，这就是典型的“队列”。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。队列跟栈一样，也是一种操作受限的线性表数据结构。

                       

 

        用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。 队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

二、复杂度分析

        顺序栈：

        在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。出队操作的时间复杂度仍然是 O(1)，入队操作的时间复杂度也是 O(1) 。

                                 

 

        链栈：

         出队操作的时间复杂度仍然是 O(1)，入队操作的时间复杂度也是 O(1) 。

                     

三、特殊队列

1、循环队列

        用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响，可以通过循环队列解决这一问题。 

                                     

        使用好循环队列的关键就是确定好队空和队满的判定条件，队列为空的判断条件仍然是 head == tail，当队满时，(tail+1)%n=head。

 2、优先级队列

 3、双向队列 

四、队列的实现

//顺序队列的实现
 
package main
 
import "fmt"
 
type Queue struct {
	element []int
}
 
//创建一个新队列
func NewQueue()*Queue{
	return &Queue{}
}
 
//判断队列是否为空
func (s *Queue)IsEmpty()bool{
	if len(s.element) == 0 {
		return true
	}else {
		return false
	}
}
 
//求队列的长度
func (s *Queue)GetQueueLength()int{
	return len(s.element)
}
 
//进队操作
func (s *Queue)Push(value int) {
	s.element = append(s.element, value)
}
 
//出队操作
func (s *Queue)Pop()bool{
	if s.IsEmpty(){
		return false
	}else{
		s.element = s.element[1:]
	}
	return true
}
 
//打印队列
func (s *Queue)Print(){
	for i := 0;i <= s.GetQueueLength()-1;i++{
		fmt.Printf("%d ", s.element[i])
	}
	fmt.Printf("\n")
}
 
func main(){
	queue := NewQueue()
	queue.Push(1)
	queue.Push(3)
	queue.Push(5)
	queue.Print()
	queue.Pop()
	queue.Print()
}

//链队列
 
//链式队列
 
package main
 
import "fmt"
 
//节点
type Node struct {
	next *Node
	data int
}
 
//链式队列
type LinkQueue struct {
	head *Node
	tail *Node
	length int
}
 
//创建节点
func CreateNode(value int) *Node{
	return &Node{
		nil,
		value,
	}
}
 
//创建链队列，初始化一个空头节点
func CreateLinkQueue() *LinkQueue{
	return &LinkQueue{
		&Node{
			nil,
			0,
		},
		&Node{
			next: nil,
			data: 0,
		},
		0,
	}
}
 
//判断队列是否为空
func (queue *LinkQueue)QueueEmpty()bool{
	return queue.head == queue.tail
}
 
//进队操作
func (queue *LinkQueue)EnQueue(data int){
	p := CreateNode(data)
	queue.tail.next = p
	queue.tail = p
	queue.length++
}
 
//出队操作
func (queue *LinkQueue)DeQueue()int{
	result := queue.head.next.data
	if queue.head.next != nil {
		queue.head = queue.head.next
		queue.length--
	}
	return result
}
 
//打印队列
func (queue *LinkQueue)PrintQueue(){
	p := queue.head.next
	for p != nil {
		fmt.Println(p.data)
		p = p.next
	}
}
 
//获取队列长度
func (queue *LinkQueue)GetLinkLength() int {
	return queue.length
}
 
func main(){
	queue := CreateLinkQueue()
	queue.tail = queue.head
 
	fmt.Println(queue.QueueEmpty())
 
	queue.EnQueue(1)
	queue.EnQueue(2)
	queue.EnQueue(3)
	queue.PrintQueue()
	fmt.Println(queue.GetLinkLength())
 
	fmt.Println()
	queue.DeQueue()
	queue.PrintQueue()
	fmt.Println(queue.GetLinkLength())
}

五、队列的应用

1、实现一个循环队列

2、实现一个双端队列

3、实现一个优先级队列

4、滑动窗口最大值

声明：本文参考极客时间《数据结构与算法之美》