赞
踩
最近忙着写论文,好久没学C++,学习放松一下……
目录
队列存储数据-》有空间来存储数据--》空间的结构:连续或链式结构
队列:
尾部进行数据的插入
头部进行数据的删除
对于队列来说:采用顺序结构来实现尾插还行,但是头删时间复杂度为O(N).
用链表来说:
所以用链表实现队列更方便
常见操作如下
头文件
- #pragma once
- typedef int DataType;
-
- // 队列中底层链表中的节点的结构
- typedef struct QNode
- {
- struct QNode* next;
- DataType data;
- }QNode;
-
- // 队列的结构
- typedef struct Queue
- {
- QNode* front; // 指向队头
- QNode* back; // 指向队尾
- }Queue;
-
- void QueueInit(Queue* q); //队列结构初始化
- void QueuePush(Queue* q, DataType data); //队尾插入数据
- void QueuePop(Queue* q);
- int QueueSize(Queue* q); //队列有多少元素
- int QueueEmpty(Queue* q);
- DataType QueueBack(Queue* q); //获得队尾元素
- DataType QueueFront(Queue* q); //获得队头元素
-
- void QueueDestroy(Queue* q);
-
- // 测试队列
- void TestQueue();
函数功能的实现
- #include"queue.h"
- #include<stdio.h>
- #include<assert.h>
- #include<stdlib.h>
-
- //实现队列时采用不带头结点的单链表
- void QueueInit(Queue* q)
- {
- assert(q);
- q->back = NULL;
- q->front = NULL;
- }
-
- QNode* BuyQNode(DataType data) //创建结点
- {
- QNode* newNode = (QNode*)malloc(sizeof(QNode));
- if (NULL == newNode)
- {
- assert(0);
- return NULL;
- }
-
- newNode->data = data;
- newNode->next = NULL;
- return newNode;
- }
-
- void QueuePush(Queue* q, DataType data)//队尾插入数据 ;O(1)
- {
- assert(q);
- QNode* newNode = BuyQNode(data);//创建结点进行尾插
- //队列为空:即链表为空; 头尾都指向这个点
- if (QueueEmpty(q))
- {
- q->front = newNode;
- q->back = newNode;
- }
- else //队列不空,链表有节点
- {
- q->back->next = newNode;//给Back后插入结点
- q->back = newNode; //新的back为刚插入的点
- }
- return q;
- }
-
- void QueuePop(Queue* q) //头删
- {
- assert(q);
- if (QueueEmpty(q)) //空链表
- {
- return;
- }
- else if(q->back == q->front)//只有一个结点
- {
- free(q->back);
- q->back = NULL;
- q->front = NULL;
- }
- else
- {
- QNode* delNode = q->front;//要删除的结点保存
- q->front = delNode->next;
- free(delNode);
- }
- }
-
- int QueueSize(Queue* q) //队列有多少元素
- {
- assert(q);
- QNode* cur = q->front;
- int count = 0;
- while (cur)
- {
- count++;
- cur = cur->next;
- }
- return count;
- }
-
- int QueueEmpty(Queue* q)
- {
- assert(q);
- return NULL == q->front;
- }
-
- DataType QueueBack(Queue* q) //获得队尾元素
- {
- assert(q);
- return q->back->data;
- }
-
- DataType QueueFront(Queue* q) //获得队头元素
- {
- assert(q);
- return q->front->data;
- }
-
-
- void QueueDestroy(Queue* q)
- {
- QNode* cur = q->front;
- while (cur)
- {
- q->front = cur->next;
- free(cur);
- cur = q->front;
- }
- //删完了是空队列,所以指向置为空
- q->front = NULL;
- q->back = NULL;
- }
-
- // 测试队列
- void TestQueue()
- {
- Queue q;
- QueueInit(&q); //初始化队列
-
- QueuePush(&q, 1);
- QueuePush(&q, 2);
- QueuePush(&q, 3);
- QueuePush(&q, 4);
- QueuePush(&q, 5);
- QueuePush(&q, 6);
- printf("size= %d\n", QueueSize(&q));
- printf("front=%d\n", QueueFront(&q));
- printf("back=%d\n", QueueBack(&q));
-
- QueuePop(&q);
- QueuePop(&q);
- printf("size= %d\n", QueueSize(&q));
- printf("front=%d\n", QueueFront(&q));
- printf("back=%d\n", QueueBack(&q));
-
-
- QueueDestroy(&q);
-
- }
最后放在主函数中执行,输入自己想测试的功能,代码无误
- #include"Queue.h"
- int main()
- {
- TestQueue();
- return 0;
- }
出队列时为了达到0(1)的效率,每次让front往后移动
带来的问题:假溢出
在入队列的时候,back一直往后移动,当back移动到空间末尾的时候,认为队列已经满了,但是由于出队列是让front往后移动的,因此当back在空间末尾的时侯,空间起始位置如果有空余位置,这种情况称为顺序方式实现队列假溢出问题。
即:当队尾back在空间末尾的时候,队列中有效元素并没有将空间真正存储满
队列中有效元素已经彻底将空间填充满了,后续还需要继续入队列
一直在入队列,没有出队列
因此,顺序结构不适合用来实现队列
为了解决顺序队列中存在的假溢出问题,提出循环队列
当front == rear ,为空队列
问题:当front == rear 时,无法区分队列是空是满
解决方法:
法1.少用一个存储空间,如图(b)
(rear + 1) % N == front N是空间容量
法2.使用一个标记: flag,初始值设置为0
每次入队时,flag置为1,出队列为0
队列满的时候: front == rear && flag == 1
法3:使用计数count
入队列时count++ ,出队列时count--;
空队列时count为0 ;当count == N时,队列为满
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。