单数组实现双端队列

72 阅读 0 评论 48 点赞

我是靠谱客的博主迷人芝麻，最近开发中收集的这篇文章主要介绍单数组实现双端队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

栈插入和删除元素只能在同一端进行，队列的插入操作和删除操作分别在两端进行，与它们不同的，有一种双端队列(deque)，其插入和删除操作都可以在两端进行。写出4个时间均为O(1)的过程，分别实现在双端队列插入和删除元素的操作，该队列使用一个数组实现的。

package main

// 一个数组实现双端队列
const maxSize = 10

type Deque struct {
	leftHead  int
	rightHead int
	size      int // 记录现有元素数量
	arr       [maxSize]int
}

func (d *Deque) isEmpty() bool {
	return d.size == 0
}

func (d *Deque) isFull() bool {
	if d.size == len(d.arr) {
		return true
	}
	return false
}

func (d *Deque) pre(position int) int {
	if position == 0 {
		return len(d.arr) - 1
	}
	return position - 1
}

func (d *Deque) next(position int) int {
	if position == len(d.arr)-1 {
		return 0
	}
	return position + 1
}

func (d *Deque) LeftInsert(val int) bool {
	if d.isFull() {
		return false
	}
	if d.isEmpty() {
		d.rightHead = d.next(d.rightHead)
	}
	d.arr[d.leftHead] = val
	d.size++
	d.leftHead = d.pre(d.leftHead)
	return true
}

func (d *Deque) RightInsert(val int) bool {
	if d.isFull() {
		return false
	}
	if d.isEmpty() {
		d.leftHead = d.pre(d.leftHead)
	}
	d.arr[d.rightHead] = val
	d.size++
	d.rightHead = d.next(d.rightHead)
	return true
}

func (d *Deque) LeftDelete() (int, bool) {
	if d.isEmpty() {
		return 0, false
	}
	d.leftHead = d.next(d.leftHead)
	if d.isEmpty() {
		d.rightHead = d.pre(d.rightHead)
	}
	val := d.arr[d.leftHead]
	d.size--
	return val, true
}

func (d *Deque) RightDelete() (int, bool) {
	if d.isEmpty() {
		return 0, false
	}
	d.rightHead = d.pre(d.rightHead)
	if d.isEmpty() {
		d.leftHead = d.next(d.leftHead)
	}
	val := d.arr[d.rightHead]
	d.size--
	return val, true
}

var deque = Deque{
	leftHead:  0,
	rightHead: 0,
	arr:       [maxSize]int{},
}