-
它是一种只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作的受限线性表。
-
又称为先进先出（FIFO—first in first out）线性表。
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理：
- 队头指针 front，它指向队头元素。
- 队尾指针 rear，它指向下一个入队元素的存储位置。
顺序队列主要的操作有如下三个：
- 每次在队尾插入一个元素是，rear 增 1
- 每次在队头删除一个元素时，front 增 1
- 当 front=rear 时，队列中没有任何元素，称为空队列
顺序队列中的溢出现象：
- "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
- "真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
- "假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
为了解决顺序队列中出现的"假上溢"现象，使队列空间能重复使用，于是便设计了循环队列。
循环队列主要的操作有如下四个：
- 每次在队尾插入一个元素是，rear 增 1，一旦 rear 指针超出了所分配的队列空间，就让它指向这片连续空间的起始位置，从 MaxSize-1 增 1 变到 0，可用取余运算 rear%MaxSize
- 每次在队头删除一个元素时，front 增 1，一旦 front 指针超出了所分配的队列空间，就让它指向这片连续空间的起始位置，从 MaxSize-1 增 1 变到 0，可用取余运算 front%MaxSize
- 当 front=rear 时，队列中没有任何元素，称为空队列。
- 当 front=（rear+1）%MaxSize 时，队列为满队列。
空队列时如下所示,front = rear = 1：
满队列时如下所示,front=(rear+1)%5=(5+1)%5=1：
或者,front=(rear+1)%5=(2+1)%5=3:
利用 go 语言的 slice 语法可以非常轻松的实现队列数据结构。
插入可以利用 append 函数实现。
删除可以利用 slice 的切片操作实现。
type Element interface{}
type Queue interface {
Offer(e Element)
Poll() Element
Clear() bool
Size() int
IsEmpty() bool
}
type sliceEntry struct {
element []Element
}
func NewQueue() *sliceEntry {
return &sliceEntry{}
}
func (entry *sliceEntry) Offer(e Element) {
entry.element = append(entry.element, e)
}
func (entry *sliceEntry) Poll() Element {
if entry.IsEmpty() {
return nil
}
first := entry.element[0]
entry.element = entry.element[1:]
return first
}
func (entry *sliceEntry) Clear() bool {
if entry.IsEmpty() {
return false
}
for i := 0; i < len(entry.element); i++ {
entry.element[i] = nil
}
entry.element = nil
return true
}
func (entry *sliceEntry) Size() int {
return len(entry.element)
}
func (entry *sliceEntry) IsEmpty() bool {
return entry.Size() == 0
}