【数据结构】进阶线性表【队列】

定义

• 队列也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。
• 插入端为队尾，删除端为队头

顺序存储结构

顺序队

算法要素

• 队空条件：q->front == r->rear
• 队满条件：q->rear == Maxsize-1（data数组的最大下标）
• 进队操作：先将rear增1，然后将元素e放在data数组的rear位置
• 出队操作：先将front增1，然后取出data数组中front位置的元素

环形队

算法要素

• 队空条件：q->rear == q->front
• 队满条件：(q->rear +1)%Maxsize == q->front
• 进队操作：rear = (q->rear+1)%Maxsize
• 出队操作：front = (front+1)%Maxsize
• 队内元素数目：(q->rear - q->front + Maxsize)%Maxsize

链式存储结构

算法要素

• 队空条件：q->rear ==NULL（也可以为q->front == NULL）
• 队满条件：不考虑
• 进队操作：新建结点元素e（由p指向它），将结点p作为尾结点插入
• 出队操作：取出队首结点的data值并将其删除

双端队列

定义：两端都可以进行出队和入队操作的队列就是双端队列