013.队列和栈-链表、数组实现

前置知识：链表

建议：比较初级，会的可以跳过，但是要注意环形队列用数组实现这个高频考点

队列和栈都是逻辑结构（受限的线性表），具体实现可以使用链表和数组

队列 §

从一端进，从另一端出，先进先出（first in first out, “FIFO”），入端叫队尾，出端叫队头；入队列叫入队（enqueue），出队列叫出队（dequeue）

链表实现 §

package linkedqueue
 
type LinkedQueue[T any] struct {
  head, tail *LinkedNode[T]
  Len       int
}
 
type LinkedNode[T any] struct {
  Val  T
  Next *LinkedNode[T]
}
 
func New[T any]() *LinkedQueue[T] {
  return &LinkedQueue[T]{}
}
 
// 入队
func (q *LinkedQueue[T]) Enqueue(val T) { // Offer
  node := new(LinkedNode[T])
  node.Val = val
 
  if q.tail == nil {
    q.tail = node
    q.head = q.tail
  } else {
    q.tail.Next = node
    q.tail = node
  }
 
  q.Len++
}
 
// 出队
// 这里队空，则返回零值
// 看如何设计了，也可以是直接 panic，或者多加一个 bool 返回值，标识出队是否成功
func (q *LinkedQueue[T]) Dequeue() (res T) { // Poll
  if q.Len == 0 {
    return
  }
 
  res = q.Head()
  q.head = q.head.Next
  q.Len--
  return
}
 
// 看队头
func (q *LinkedQueue[T]) Head() (res T) { // Peek
  if q.Len == 0 {
    return
  }
  res = q.head.Val
  return
}
 
// 看队尾
func (q *LinkedQueue[T]) Tail() (res T) {
  if q.Len == 0 {
    return
  }
  res = q.tail.Val
  return
}

数组实现 ^2 §

package arrayqueue
 
type ArrayQueue[T any] []T
 
func New[T any]() *ArrayQueue[T] {
  return &ArrayQueue[T]{}
}
 
// 队的长度
func (q *ArrayQueue[T]) Len() int {
  return len(*q)
}
 
// 入队
func (q *ArrayQueue[T]) Enqueue(val T) { // Offer
  *q = append(*q, val)
}
 
// 出队
// 这里队空，则返回零值
// 看如何设计了，也可以是直接 panic，或者多加一个 bool 返回值，标识出队是否成功
func (q *ArrayQueue[T]) Dequeue() (res T) { // Poll
  n := q.Len()
  if n == 0 {
    return
  }
 
  res = (*q)[0]
  *q = (*q)[1:n]
  return
}
 
// 看队头
func (q *ArrayQueue[T]) Head() (res T) { // Peek
  if q.Len() == 0 {
    return
  }
  return (*q)[0]
}
 
// 看队尾
func (q *ArrayQueue[T]) Tail() (res T) {
  n := q.Len()
  if n == 0 {
    return
  }
  return (*q)[n-1]
}

可以看到，这里有很严重的空间浪费问题，总空间占用是所有入队元素的总和，出队并不会释放空间（其实要看 GC 的实现细节了，这里已经没有切片指向已出队的元素了，GC 可以释放之）

当队列最大容量确定时，可使用 循环队列 避免此问题

栈 §

只能从一端进出，后进先出（last in first out, “LIFO”），可出入的端叫栈顶，不可出入的端叫栈底；入栈叫压栈（push），出栈叫弹栈（pop）

数组实现 ^1 §

package stack
 
type Stack[T any] []T
 
func New[T any]() *Stack[T] {
  return &Stack[T]{}
}
 
// 栈高（栈的长度）
func (s *Stack[T]) Len() int {
  return len(*s)
}
 
// 压栈
func (s *Stack[T]) Push(val T) {
  *s = append(*s, val)
}
 
// 弹栈
// 这里栈空，则返回零值
// 看如何设计了，也可以是直接 panic，或者多加一个 bool 返回值，标识弹栈是否成功
func (s *Stack[T]) Pop() (res T) {
  n := s.Len()
  if n == 0 {
    return
  }
 
  res = (*s)[n-1]
  *s = (*s)[:n-1]
  return
}
 
// 看栈顶
func (s *Stack[T]) Top() (res T) { // Peek
  n := s.Len()
  if n == 0 {
    return
  }
  res = (*s)[n-1]
  return
}
 
// 看栈底
func (s *Stack[T]) Bottom() (res T) {
  if s.Len() == 0 {
    return
  }
  res = (*s)[0]
  return
}

也可以用链表实现栈，但相较于数组实现没有任何优势（而链表实现队列相较于数组实现队列没有无法复用空间的问题），所以就不实现了

这里数组实现的队列和栈都是用的切片（动态数组），会有扩容的时间消耗，如果最大容量确定时，可以使用数组（静态数组）代替会更好。队列：使用 head、tail 两个指针确定有效数据范围和队列长度；栈：使用 top 一个栈顶指针即可

循环队列 §

也叫环形队列，可以重用底层数组中已出队的位置，要提前确定最大队列容量，否则达到最大容量就入不了队了

head 指针指向队头； tail 指针指向队尾的下一个位置，即：有效位置范围 [head, tail)

设计成 [head, tail] 可以吗？也可以，不过队空的时候 tail 要设成 -1，不太“美”（设计之美）

但是设计成 [head, tail) 的话有个问题，队空和队满，head 和 tail 都指向同一位置，解决方法有两个：

• 加一个 size 变量记录队列的长度
• 队列容量多加一个长度，这个位置（head 的前一个位置）不用做数据存储，仅用于置放 tail 指针，以区分队空、队满情况

加 size 变量 §

package circularqueue
 
type CircularQueue[T any] struct {
  data       []T
  head, tail int
  Size       int
  Capacity   int
}
 
func New[T any](cap int) *CircularQueue[T] {
  if cap < 0 {
    panic("容量为负")
  }
  return &CircularQueue[T]{
    data:     make([]T, cap),
    Capacity: cap,
  }
}
 
// 判断队空
func (q *CircularQueue[T]) IsEmpty() bool {
  return q.Size == 0
}
 
// 判断队满
func (q *CircularQueue[T]) IsFull() bool {
  return q.Size == q.Capacity
}
 
// 入队
func (q *CircularQueue[T]) Enqueue(val T) bool { // Offer
  if q.IsFull() {
    return false
  }
  q.data[q.tail] = val
  if q.tail == q.Capacity-1 {
    q.tail = 0
  } else {
    q.tail++
  }
  q.Size++
  return true
}
 
// 出队
func (q *CircularQueue[T]) Dequeue(val T) (res T, ok bool) { // Poll
  if q.IsEmpty() {
    ok = false
    return
  }
 
  res = q.data[q.head]
  if q.head == q.Capacity-1 {
    q.head = 0
  } else {
    q.head++
  }
  q.Size--
  ok = true
  return
}
 
// 看队头
func (q *CircularQueue[T]) Head() (res T, ok bool) { // Peek
  if q.IsEmpty() {
    ok = false
    return
  }
 
  res = q.data[q.head]
  ok = true
  return
}
 
// 看队尾
func (q *CircularQueue[T]) Tail() (res T, ok bool) {
  if q.IsEmpty() {
    ok = false
    return
  }
 
  last := q.tail - 1
  if q.tail == 0 {
    last = q.Capacity - 1
  }
  res = q.data[last]
  ok = true
  return
}

空一位置 §

package circularqueue
 
type CircularQueue[T any] struct {
  data       []T
  head, tail int
  Capacity   int
}
 
func New[T any](cap int) *CircularQueue[T] {
  if cap < 0 {
    panic("容量为负")
  }
 
  return &CircularQueue[T]{
    data:     make([]T, cap+1), // 注意这里
    Capacity: cap,
  }
}
 
// 队列长度
func (q *CircularQueue[T]) Len() int {
  return (q.tail + q.Capacity + 1 - q.head) % (q.Capacity + 1)  // 注意；不是 Capacity
  // 这里展示用模运算代替判断，判断和模运算都是可以的
  // 以下同理，不再重复说明
}
 
// 判断队空
func (q *CircularQueue[T]) IsEmpty() bool {
  return q.head == q.tail
}
 
// 判断队满
func (q *CircularQueue[T]) IsFull() bool {
  lastPlusOne := q.tail + 1
  if lastPlusOne == q.Capacity + 1 { // 注意；不是 Capacity
    lastPlusOne = 0
  }
  return lastPlusOne == q.head
  
}
 
// 入队
func (q *CircularQueue[T]) Enqueue(val T) bool { // Offer
  if q.IsFull() {
    return false
  }
 
  q.data[q.tail] = val
  if q.tail == q.Capacity { // 注意；不是 Capacity - 1
    q.tail = 0
  } else {
    q.tail++
  }
  return true
}
 
// 出队
func (q *CircularQueue[T]) Dequeue(val T) (res T, ok bool) { // Poll
  if q.IsEmpty() {
    ok = false
    return
  }
 
  res = q.data[q.head]
  if q.head == q.Capacity { // 注意；不是 Capacity - 1
    q.head = 0
  } else {
    q.head++
  }
  ok = true
  return
}
 
// 看队头
func (q *CircularQueue[T]) Head() (res T, ok bool) { // Peek
  if q.IsEmpty() {
    ok = false
    return
  }
  res = q.data[q.head]
  ok = true
  return
}
 
// 看队尾
func (q *CircularQueue[T]) Tail() (res T, ok bool) {
  if q.IsEmpty() {
    ok = false
    return
  }
  last := q.tail - 1
  if q.tail == 0 {
    last = q.Capacity // 注意；不是 Capacity - 1
  }
  res = q.data[last]
  ok = true
  return
}

一般用 空一位置，而不用 加 size 变量，同理：设计之美（更优雅）

测试链接：622.设计循环队列

备注 §

队列、栈、双端队列 可以组成非常多重要的数据结构

将在【必备】课程里继续