016.双端队列-双链表和固定数组实现

前置知识：双链表

建议：用双链表实现双端队列比较初级，会的可以跳过；但是用固定数组的实现双端队列值得听

测试链接：641.设计循环双端队列

双端队列

可以在两端自由出入的线性表

双链表实现

这里为了通过力扣测试，没有写泛型，方法名也是按力扣给的，双向链表直接使用标准库的了，如果要写一个通用的实现，稍微修改一下即可

注意：力扣给了一个容量，其实双链表实现可以不用确定队列容量的

type MyCircularDeque struct {
	list     list.List
	Capacity int
}
 
func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		Capacity: k,
	}
}
 
func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.list.Len() == this.Capacity {
		return false
	}
	this.list.PushFront(value)
	return true
}
 
func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.list.Len() == this.Capacity {
		return false
	}
	this.list.PushBack(value)
	return true
}
 
func (this *MyCircularDeque) DeleteFront() bool {
	if this.list.Len() == 0 {
		return false
	}
	this.list.Remove(this.list.Front())
	return true
}
 
func (this *MyCircularDeque) DeleteLast() bool {
	if this.list.Len() == 0 {
		return false
	}
	this.list.Remove(this.list.Back())
	return true
}
 
func (this *MyCircularDeque) GetFront() int {
	if this.list.Len() == 0 {
		return -1
	}
	return this.list.Front().Value.(int)
}
 
func (this *MyCircularDeque) GetRear() int {
	if this.list.Len() == 0 {
		return -1
	}
	return this.list.Back().Value.(int)
}
 
func (this *MyCircularDeque) IsEmpty() bool {
	return this.list.Len() == 0
}
 
func (this *MyCircularDeque) IsFull() bool {
	return this.list.Len() == this.Capacity
}
 
/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

切片实现（不确定队列容量、效率低）

package deque
 
type Deque[T any] []T
 
func New[T any]() *Deque[T] {
  return &Deque[T]{}
}
 
// 队列长度
func (q *Deque[T]) Len() int {
  return len(*q)
}
 
// 向尾部插入元素
func (q *Deque[T]) Push(val T) { // PushBack、offerLast
  *q = append(*q, val) // 问题 1：动态扩容
}
 
// 向头部插入元素
func (q *Deque[T]) Unshift(val T) { // PushFront、offerFirst
  *q = append([]T{val}, (*q)...)
  // 问题 2：要复制原切片到新切片，时间复杂度 O(n)
}
 
// 弹出尾部元素
func (q *Deque[T]) Pop() (res T, ok bool) { // PopBack、pollLast
  res, ok = q.Back()
  if !ok {
    return
  }
  *q = (*q)[:q.Len()-1]
  return
}
 
// 弹出头部元素
func (q *Deque[T]) Shift() (res T, ok bool) { // PopFront、pollFirst
  res, ok = q.Front()
  if !ok {
    return
  }
  *q = (*q)[1:] // 问题 3：无法复用头部弹出位置的空间
  return
}
 
// 查看尾部元素
func (q *Deque[T]) Back() (res T, ok bool) { // peekLast
  n := q.Len()
  if n == 0 {
    ok = false
    return
  }
  res = (*q)[n-1]
  ok = true
  return
}
 
// 查看头部元素
func (q *Deque[T]) Front() (res T, ok bool) { // peekFirst
  if q.Len() == 0 {
    ok = false
    return
  }
  res = (*q)[0]
  ok = true
  return
}
 
// 清空队列
func (q *Deque[T]) Clear() {
  clear(*q)
}

这里是 JavaScript 数组方法的命名方式；Offer、Poll、Peek 系列是 Java 的命名方式

数组实现（确定队列容量、效率高）

同样，使用切片会有扩容时间、无法复用头部弹出位置空间的问题，而且向头部插入元素时要复制整个数组的内容，时间复杂度是 O(n)!

所以如果知道双端队列的容量，采用循环队列的思路，改用数组会解决上面的三个问题，高效很多

package deque
 
type Deque[T any] struct {
	data       []T
	head, tail int // [head, tail)
	Capacity   int
}
 
func New[T any](cap int) *Deque[T] {
	if cap < 0 {
		panic("容量为负")
	}
 
	return &Deque[T]{
		data:     make([]T, cap+1),
		Capacity: cap,
	}
}
 
// 队列长度
func (q *Deque[T]) Len() int {
	return (q.tail + q.dataLen() - q.head) % q.dataLen()
}
 
// 是否队空
func (q *Deque[T]) IsEmpty() bool {
	return q.tail == q.head
}
 
// 是否队满
func (q *Deque[T]) IsFull() bool {
	return (q.tail+1)%q.dataLen() == q.head
}
 
// 向尾部插入元素
func (q *Deque[T]) Push(val T) bool { // PushBack、offerLast
	if q.IsFull() {
		return false
	}
 
	q.data[q.tail] = val
	q.tail = (q.tail + 1) % q.dataLen()
	return true
}
 
// 向头部插入元素
func (q *Deque[T]) Unshift(val T) bool { // PushFront、offerFirst
	if q.IsFull() {
		return false
	}
 
	q.head = (q.head - 1 + q.dataLen()) % q.dataLen()
	q.data[q.head] = val
	return true
}
 
// 弹出尾部元素
func (q *Deque[T]) Pop() (res T, ok bool) { // PopBack、pollLast
	res, ok = q.Back()
	if !ok {
		return
	}
	q.tail = (q.tail - 1 + q.dataLen()) % q.dataLen()
	return
}
 
// 弹出头部元素
func (q *Deque[T]) Shift() (res T, ok bool) { // PopFront、pollFirst
	res, ok = q.Front()
	if !ok {
		return
	}
	q.head = (q.head + 1) % q.dataLen()
	return
}
 
// 查看尾部元素
func (q *Deque[T]) Back() (res T, ok bool) { // peekLast
	if q.IsEmpty() {
		ok = false
		return
	}
	res = q.data[(q.tail-1+q.dataLen())%q.dataLen()]
	ok = true
	return
}
 
// 查看头部元素
func (q *Deque[T]) Front() (res T, ok bool) { // peekFirst
	if q.IsEmpty() {
		ok = false
		return
	}
	res = q.data[q.head]
	ok = true
	return
}
 
// 清空队列
func (q *Deque[T]) Clear() {
	clear(q.data)
	q.head = 0
	q.tail = 0
}
 
func (q *Deque[T]) dataLen() int {
	return q.Capacity + 1
	// 或：len(q.data)
}

力扣提交版

type MyCircularDeque struct {
	data       []int
	head, tail int // [head, tail)
	Capacity   int
}
 
func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		data:     make([]int, k+1),
		Capacity: k,
	}
}
 
func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	this.head = (this.head - 1 + this.dataLen()) % this.dataLen()
	this.data[this.head] = value
	return true
}
 
func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	this.data[this.tail] = value
	this.tail = (this.tail + 1) % this.dataLen()
	return true
}
 
func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.head = (this.head + 1) % this.dataLen()
	return true
}
 
func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.tail = (this.tail - 1 + this.dataLen()) % this.dataLen()
	return true
}
 
func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.data[this.head]
}
 
func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.data[(this.tail-1+this.dataLen())%this.dataLen()]
}
 
func (this *MyCircularDeque) IsEmpty() bool {
	return this.tail == this.head
}
 
func (this *MyCircularDeque) IsFull() bool {
	return (this.tail+1)%this.dataLen() == this.head
}
 
func (q *MyCircularDeque) dataLen() int {
	return q.Capacity + 1
}
 
/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

备注

备注