[数据结构]6. 队列-Queue

1. 介绍

队列（queue） 是一种遵循先入先出规则的线性数据结构。将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

2. 队列实现

2.1 基于链表的实现

2.2 基于数组的实现

3. 队列操作

Create

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

Initialize

void QueueInit(Queue* pq) {assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

Destory

void QueueDestory(Queue* pq) {assert(pq);QNode* cur = pq->phead;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

Push

void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL) {assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

Pop

void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));// one nodeif (pq->phead->next == NULL) {free(pq->phead);pq->phead = pq->ptail = NULL;}// more nodeelse {QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

Front

QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

Back

QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}

Size

int QueueSize(Queue* pq) {assert(pq);return pq->size;
}

Empty

bool QueueEmpty(Queue* pq) {assert(pq);//return pq->phead == NULL && pq->ptail == NULL;return pq->size == 0;
}