《数据结构初阶》实现顺序循环队列和链式队列 |
您所在的位置：网站首页 › 顺序循环队列的元素个数怎么求出来 › 《数据结构初阶》实现顺序循环队列和链式队列 |
《数据结构初阶》实现顺序循环队列和链式队列
|
鸿鹄高飞云霄外,剑映豪气贯长虹
目录 一、🌱本章重点 二、🌱顺序循环队列 2.1💯什么是队列？ 2.2💯顺序循环队列 三、🌱链式队列 四、总结 一、🌱本章重点 实现顺序循环队列实现链式队列总结 二、🌱顺序循环队列 2.1💯什么是队列？💦队列：一种特殊的线性表，只允许一端进行插入，另一段进行删除。 💦实现队列的方式有多种：静态数组、动态数组、单链表、双链表。 以静态数组实现顺序队列为例。 💦与动态数组相比：静态数组不能增容，而动态数组在空间不够时，可以自动增容。 💦静态数组实现顺序队列：可以采取头删和尾插的方式，该方式：出队列：头删。入队列：尾插。 💦头删：int head记录头的下标，起初为0，如果要出队列，则head++即可。 💦尾插：int tail记录最后元素的下一个下标，初始为0，即代表整个队列元素的个数。 该方式实现队列的结构体为： #define MAXSIZE 10 typedef int SQDataType; typedef struct SequenceQueue { SQDataType data[MAXSIZE]; int head; int tail; }SeqQueue;尾插视图：
头删视图：
当我们以这这方式删除的时候：当tail==MAXSIZE队列就满了，但前面删除空出来的空间就不好使用了，这种状态我们称之为假溢出。 为了解决假溢出的问题，我们可以这样做，当tail==MAXSIZE时，我们可以把tail置为0，或者对它进行取模操作（tail%=MAXSIZE）。这种方式类似于一个环，因此被叫做顺序循环队列。 2.2💯顺序循环队列顺序循环队列与顺序队列差不多，只是多了这一步：要完全利用前面删除数据空出来的空间 队列的结构体是一样的 #define MAXSIZE 10 typedef int SQDataType; typedef struct SequenceQueue { SQDataType data[MAXSIZE]; int head; int tail; }SeqQueue;🎲接口1：循环队列初始化函数 void CQueueInit(CQ* p);初始状态：head==tail=0； 参考代码： void CQueueInit(CQ* p) { assert(p); p->head = p->tail = 0; }🎲接口2：实现队列是否为空函数 SeqQueueEmpty(SeqQueue* sqp)队列为空有两种情况： 第一种：未插入任何数据。
第二种：插入了一些数据，最后都删除了，导致队列为空。
参考代码： bool SeqQueueEmpty(SeqQueue* sqp) { return sqp->head == sqp->tail }🎲接口3：实现队列是否满的函数 bool SeqQueueFull(SeqQueue* seq)怎么判断队列满呢？ 第一种：没有删数据一直入数据满了。
如果在放一个数据，那么tail==head，那么这个判断条件到底是满还是空呢？ 为了解决这一判断条件相同的问题，我们就想到了浪费最后一个空间的思路。 因此空间满的判断条件是 ((p->tail+1) % MAXSIZE) == p->head % MAXSIZE。 参考代码： bool CQueueFull(CQ* p) { assert(p); return ((p->tail+1) % MAXSIZE) == p->head % MAXSIZE; }🎲接口4：循环队列插入函数 bool CQueuePush(CQ* p, CQDataType x);首先p不能为空，要assert断言一下。 然后判断该队列是否满了，如果满了则返回false。 最后插入x，由于tail记录的是下一个要插入位置的下标，但一直插入x，tail会一直增大，因此要对tail取模。 所以插入操作为： p->data[p->tail % MAXSIZE] = x; p->tail++;参考代码： bool CQueuePush(CQ* p, CQDataType x) { assert(p); if (CQueueFull(p)) { return false; } p->data[p->tail % MAXSIZE] = x; p->tail++; return true; }🎲接口5：删除头部的数据，即出队列。 bool CQueuePop(CQ* p);出队列好办，直接p->head++；即可。 但在之前要判断队列是否为空，为空就不能出队列了，返回false。 同时也要判断p不能为NULL。 因为你不能防止别人这样调用函数：CQueuePop（NULL）； 参考代码： bool CQueuePop(CQ* p) { assert(p); if (CQueueEmpty(p)) { return false; } p->head++; return true; }🎲接口6：取对头数据的函数 CQDataType CQueueFront(CQ* p);取对头数据也好办，p->[p->head]即可，要不要取模呢？ 答案是要，因为可能在此之前，插入了很多数据，也删除了很多数据。head是有可能大于MAXSIZE-1的，因此要进行取模。 同样的要判断p不为空并且队列也不为空。 参考代码： CQDataType CQueueFront(CQ* p) { assert(p); if (CQueueEmpty(p)) { return -1; } return p->data[p->head % MAXSIZE]; }🎲接口7：取对尾数据的函数 CQDataType CQueueRear(CQ* p);同理，要先保证p不能为空，同时队列不为空。 由于tail%MAXSZIE代表的是下一个元素的下标。队尾数据可以这样取吗？ p-data[tail%MAXSIZE-1]
但如果tail==8时，tail%MAXSIZE==0，那么你取的就是p->data[-1]了，这显然不对。 换种方式:p->data[(tail-1)%MAXSZIE] 所以队尾数据为p->data[(tail-1)%MAXSZIE] 参考代码： CQDataType CQueueRear(CQ* p) { assert(p); if (CQueueEmpty(p)) { return -1; } return p->data[(p->tail - 1) % MAXSIZE]; }🎲接口8：计算循环队列元素个数 size_t CQueueSize(CQ* p);如何计算循环队列的元素个数？ 让我们先从简单情况计算。 情况1：只插入数据，不删除数据。
如图连续插入7个数据。 元素个数为tail-head。 情况2：插入了7个数据，删除了3个数据
此时tail=7，head=2。 元素个数为：tail-head。 情况3：先插入7个数据，删除3个，再插入2个数据。 此时tail=7+2=9，head=3 元素个数为：6 可以写成：tail-head 因此：我们可以总结循环队列的元素个数为tail-head。 参考代码： size_t CQueueSize(CQ* p) { return p->tail - p->head; }🎲接口9：打印循环队列元素 void CQueuePrint(CQ* p);先调用求队列元素的接口求出要打印的元素个数，然后一个for循环语句解决。 参考代码： void CQueuePrint(CQ* p) { int i = 0; int n = CQueueSize(p); for (i = 0; i < n; i++) { printf("%d ", CQueueFront(p)); CQueuePop(p); } printf("\n"); }🎲接口10：destroy循环队列函数 void CQueueFree(CQ* p)参考代码： void CQueueFree(CQ* p) { assert(p); p->head = p->tail = 0; } 三、🌱链式队列💦链式队列：单链表实现的链式队列 为了方便我们实现先进先出，出队：头删，入队：尾插。 💦单链表头删：用head记录头节点的地址，管理队列的头。 💦单链表尾插：需要不断的找尾，为了方便我们可以用tail节点指针记录尾部节点的地址，管理队列的尾。 因此结构体为： typedef int QTypeData; typedef struct QueueNode { struct QueueNode* next; QTypeData val; }QN; typedef struct Queue { QN* head; QN* tail; }Queue;我们要实现的接口： void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QTypeData x); void QueuePop(Queue* pq); QN* QueueBack(Queue* pq); QN* QueueFront(Queue* pq); size_t QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);🎲接口1：队列初始化接口 void QueueInit(Queue* pq);队列头指针和尾指针指向NULL。 参考代码： void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }🎲接口2：Destroy队列接口 void QueueDestroy(Queue* pq);链表节点的回收：用一个while循环。 并将head和tail置为空。 参考代码： void QueueDestroy(Queue* pq) { assert(pq); QN* cur = pq->head; while (cur) { QN* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }🎲接口3：入队列，即尾插 void QueuePush(Queue* pq, QTypeData x);malloc一个新节点 QN* newnode = (QN*)malloc(sizeof(QN)); assert(newnode); newnode->next = NULL; newnode->val = x;然后尾插至head和tail管理的队列。 尾插有两种情况： 第一种：一个节点都没的情况，即head==tail==NULL if (pq->head == NULL) { pq->head = pq->tail = newnode; }第二种：队列有一个以上的节点。 else { pq->tail->next = newnode; pq->tail = newnode; }参考代码： void QueuePush(Queue* pq, QTypeData x) { assert(pq); QN* newnode = (QN*)malloc(sizeof(QN)); assert(newnode); newnode->next = NULL; newnode->val = x; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }🎲接口4：出队列，即头删 void QueuePop(Queue* pq);1.要保证pq不为空 assert(pq) 2.要保证队列不为空 assert(tail) 4.删除2个及2个以上的节点 node* temp=head。 head=head->next free（temp） 3.删除一个节点 这样删除行吗？ node* temp=head。 head=head->next free（temp） 如果这样删除的话，tail会变成野指针，有安全隐患。
因此可以分情况判断 参考代码： void QueuePop(Queue* pq) { assert(pq); assert(pq->tail); QN* next = pq->head->next; if (next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { free(pq->head); pq->head = next; } }🎲接口5：取队尾数据 QN* QueueBack(Queue* pq)先要保证pq和队列不为空 队尾数据：pq->tail 参考代码： QN* QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail; }🎲接口6：取对头数据 QN* QueueFront(Queue* pq)与取队尾数据一样，先要保证pq和队列不为空。 QN* QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head; }🎲接口7：求队列元素个数的接口 size_t QueueSize(Queue* pq);遍历一遍链表，也可在head和tail的队列结构体多加一个size计数器，在push时，size++。在pop时，size--。 参考代码： size_t QueueSize(Queue* pq) { assert(pq); QN* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; }🎲接口8：判断队列为空接口 bool QueueEmpty(Queue* pq);参考代码： bool QueueEmpty(Queue* pq) { assert(pq); return pq->tail==NULL && pq->head==NULL; }这里也可为 bool QueueEmpty(Queue* pq) { assert(pq); return pq->tail==NULL; } 四、总结由于循环队列有多种实现方式：如数组、单链表、双链表。 并且接口的实现也可能是不一样的，但效果是一样的。 有的push或者pop数据之后，函数会把rear或者front进行取模重赋值，让front和rear对应队列头和队列尾下标。不取模重赋值也是完全可以的。 实现接口按照自己思路来就好，同时这要确保考虑是全面的。 |
【本文地址】
今日新闻 |
推荐新闻 |