赞
踩
队列的定义查一下百度百科就可以,很简单,本文只谈顺序队列,不涉及循环队列。
文章主要目的是为了用链表的形式实现队列常用的接口函数,一般有初始化,销毁,队尾插入,删除队头,返回队头,返回队尾,判空和返回当前队列元素个数。
首先先给出队列元素的定义和整个队列的形式
- typedef int QDataType;
- typedef struct QueueNode
- {
- struct QueueNode* next;
- QDataType data;
- }QNode;
-
- typedef struct Queue
- {
-
- QNode* head;
- QNode* tail;
- }Queue;
初始化
- void QueueInit(Queue* pq)
- {
- assert(pq);
- pq->head = pq->tail = NULL;
- }
销毁
- void QueueDestroy(Queue* pq)
- {
- assert(pq);
- QNode* cur = pq->head;
- while (cur)
- {
- QNode* next = cur->next;
- free(cur);
- cur=next;
- }
-
- pq->head = pq->tail = NULL;
- }
队尾插入
- void QueuePush(Queue* pq, QDataType x)
- {
- assert(pq);
- QNode* newnode = (QNode*)malloc(sizeof(QNode));
- if (newnode == NULL)
- {
- printf("malloc fail\n");
- exit(-1);
- }
- newnode->data = x;
- newnode->next = NULL;
-
- if (pq->tail == NULL)
- {
- pq->head = pq->tail = newnode;
- }
- else
- {
- pq->tail->next = newnode;
- pq->tail = newnode;
- }
- }
删除队头
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- //
- //
- if (pq->head->next == NULL)
- {
- free(pq->head);
- pq->head = pq->tail = NULL;
- }
- else
- {
- QNode* next = pq->head->next;
- free(pq->head);
- pq->head = next;
- }
- }
返回队头
- QDataType QueueFront(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- return pq->head->data;
- }
返回队尾
- QDataType QueueBack(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- return pq->tail->data;
- }
判空
- bool QueueEmpty(Queue* pq)
- {
- assert(pq);
- return pq->head == NULL;
- }
返回当前队列元素个数
- int QueueSize(Queue* pq)
- {
- assert(pq);
- QNode* cur = pq->head;
- int size = 0;
- while (cur)
- {
- ++size;
- cur = cur->next;
- }
-
- return size;
- }
队列也是相对而言比较简单的,但是这里的OJ题并不简单,准确地说使用C语言实现并不简单,接下来会更新关于栈和队列地相互实现以及循环队列的OJ题。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。