【数据结构】进阶线性表【队列】
定义
- 队列也是一种操作受限的线性表,其限制为仅允许在表的一端进行插入操作,而在表的另一端进行删除操作。
- 插入端为队尾,删除端为队头
顺序存储结构
顺序队
算法要素
- 队空条件: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值并将其删除
双端队列
定义:两端都可以进行出队和入队操作的队列就是双端队列