队列 维基百科:
队列,又称为伫列(queue),是先进先出(FIFO,First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。
队列的顺序存储:
通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
#define Maxsize <储存数据元素的最大个数> typedef struct { ElementType Data[Maxsize]; int rear; int front; } Queue; void AddQ( Queue *PtrQ,ElementType item)//入队列 { if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) { printf(“队列满”); return; } PtrQ->rear = (PtrQ->rear+1)% MaxSize; PtrQ->Data[PtrQ->rear] = item; } ElementType DeleteQ ( Queue *PtrQ )//出队列 { if ( PtrQ->front == PtrQ->rear ) { printf(“队列空”); return ERROR; } else { PtrQ->front = (PtrQ->front+1)% MaxSize; return PtrQ->Data[PtrQ->front]; } }
队列的链式存储结构:
typedef struct Node { ElementType Data; struct Node *Next; } QNode; typedef struct /* 链队列结构 */ { QNode *rear; /* 指向队尾结点 */ QNode *front; /* 指向队头结点 */ } LinkQueue; LinkQueue *PtrQ ; //不带头结点的链式队列出队操作的一个示例: ElementType DeleteQ ( LinkQueue *PtrQ ) { Qnode *FrontCell; ElementType FrontElem; if ( PtrQ->front == NULL) { printf(“队列空”); return ERROR; } FrontCell = PtrQ->front; if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */ PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */ else PtrQ->front = PtrQ->front->Next; FrontElem = FrontCell->Data; free( FrontCell ); /* 释放被删除结点空间 */ return FrontElem; }