一、队列是什么
队列是一种可以实现“先进先出”的存储结构。其实,说简单点,队列就是排队,跟我们日常生活中到银行取钱排队,排队打饭在道理上是一样的。
队列通常可以分为两种类型:
①链式队列(由链表实现)。
②静态队列(由数组实现),静态队列通常都必须是循环队列。
由于链式队列跟链表差不多,所以在这里只针对循环队列来说明并实践。
循环队列的两个参数:
①front,front指向队列的第一个元素。
②rear,rear指向队列的最后一个有效元素的下一元素。
队列的两个基本操作:出队和入队。
二、队列的结构
下面是一个循环队列(基于数组实现)的结构图:
三、队列的操作
入队(尾部入队)
①将值存入rear所代表的位置。
②rear = (rear+1)%数组的长度。
出队(头部出队)
front = (front+1)%数组的长度。
队列是否为空
front和rear的值相等,则该队列就一定为空。
队列是否已满
注意:循环队列中,有n个位置,通常放n-1个值,空1个
在循环队列中,front和rear指向的值不相关,无规律。front可能比rear指向的值大,也可能比rear指向的值小,也可能两者相等。
算法:
①多增加一个标识参数。
②少用一个元素,rear和front指向的值紧挨着,则队列已满。
四、队列的实现
基于数组的循环队列的具体实现
#include<stdio.h>
#include<malloc.h> //包含了malloc函数
/*
*循环队列,用数组实现
*/
//队列结构体定义
typedef struct Queue
{
int * pBase; //用于动态分配内存,pBase保存数组的首地址
int front; //指向头结点
int rear; //指向最后一个元素的下一结点
} QUEUE;
//函数声明
void initQueue(QUEUE * pQueue); //队列初始化的函数
bool isEmpty(QUEUE * pQueue); //判断队列是否为空的函数
bool isFull(QUEUE * pQueue); //判断队列是否满的函数
bool enQueue(QUEUE * pQueue, int value); //入队的函数
bool outQueue(QUEUE * pQueue, int * pValue); //出队的函数,同时保存出队的元素
void traverseQueue(QUEUE * pQueue); //遍历队列的函数
/*
*主程序
*/
int main(void)
{
int value; //用于保存出队的元素
//创建队列对象
QUEUE queue;
//调用初始化队列的函数
initQueue(&queue);
//调用出队函数
enQueue(&queue, 1);
enQueue(&queue, 2);
enQueue(&queue, 3);
enQueue(&queue, 4);
enQueue(&queue, 5);
enQueue(&queue, 6);
enQueue(&queue, 7);
enQueue(&queue, 8);
//调用遍历队列的函数
traverseQueue(&queue);
//调用出队函数
if(outQueue(&queue, &value))
{
printf("出队一次,元素为:%d\n", value);
}
traverseQueue(&queue);
if(outQueue(&queue, &value))
{
printf("出队一次,元素为:%d\n", value);
}
traverseQueue(&queue);
getchar();
return 0;
}
/*
*初始化函数的实现
*/
void initQueue(QUEUE * pQueue)
{
//分配内存
pQueue->pBase = (int *)malloc(sizeof(int) * 6); //分配6个int型所占的空间
pQueue->front = 0; //初始化时,front和rear值均为0
pQueue->rear = 0;
return;
}
/*
*入队函数的实现
*/
bool enQueue(QUEUE * pQueue, int value)
{
if(isFull(pQueue))
{
printf("队列已满,不能再插入元素了!\n");
return false;
}
else
{
//向队列中添加新元素
pQueue->pBase[pQueue->rear] = value;
//将rear赋予新的合适的值
pQueue->rear = (pQueue->rear+1) % 6;
return true;
}
}
/*
*出队函数的实现
*/
bool outQueue(QUEUE * pQueue, int * pValue)
{
//如果队列为空,则返回false
if(isEmpty(pQueue))
{
printf("队列为空,出队失败!\n");
return false;
}
else
{
*pValue = pQueue->pBase[pQueue->front]; //先进先出
pQueue->front = (pQueue->front+1) % 6; //移到下一位置
return true;
}
}
/*
*遍历队列的函数实现
*/
void traverseQueue(QUEUE * pQueue)
{
int i = pQueue->front; //从头开始遍历
printf("遍历队列:\n");
while(i != pQueue->rear) //如果没有到达rear位置,就循环
{
printf("%d ", pQueue->pBase[i]);
i = (i+1) % 6; //移到下一位置
}
printf("\n");
return;
}
/*
*判断队列是否满的函数的实现
*/
bool isFull(QUEUE * pQueue)
{
if((pQueue->rear+1) % 6 == pQueue->front) //队列满
return true;
else
return false;
}
/*
*判断队列是否为空函数的实现
*/
bool isEmpty(QUEUE * pQueue)
{
if(pQueue->front == pQueue->rear)
return true;
else
return false;
}
五、队列的应用
在我们去打饭的时候总要排队,排队是与时间有关的,排在前面的人多,我们打到饭用的时间就比较长,相反,如果前面的排队的人相对较少,我们能打到饭的用的时间也就相对较短,所以说,队列总是与时间相关的。可以肯定地说:任何与时间相关的操作,基本上都会牵扯到队列。
六、结语
最后再声明一下:附件中的工程是在Visual Studio 2010 中建的。
分享到:
相关推荐
c语言数据结构的队列实现,新建队列,入队列,出队列,删除队列
数据结构中队列的操作很重要,这是本人用C语言编写的程序绝对原创!不能说经典但很实用!!
数据结构中的队列各种入队出队插入清空新建等各种操作的C语言实现
数据结构 -- C语言版 -- 队列的部分实现代码,详细介绍参考数据结构--队列的系列博文。链接为:https://blog.csdn.net/songshuai0223/category_9742561.html。
数据结构循环队列的C语言实现
数据结构实验 队列 c语言写的控制台程序 实现了对队列的多种基本操作
C语言-数据结构-栈队列实现
数据结构课设,程序可直接运行,含有实验报告。实现队列的增删改查
数据结构栈和队列C语言实现.pdf
简单的数据结构单链队列的VC实现 仅供学习研究使用
队列 C语言 数据结构队列
一. 优先队列的定义 优先队列是0个或多个...二. 实现本优先队列的初始化,查找,插入,删除操作,并且控制其查找,插入,删除操作的算法时间复杂度为O(logn)。采用堆正好能实现该时间复杂度。相关代码实现如下:
用队列实现杨辉三角 队列杨辉三角 c实现杨辉三角 c用队列实现杨辉三角 用队列实现杨辉三角 队列杨辉三角 c实现杨辉三角 c用队列实现杨辉三角
C语言实现的数据结构中的循环队列 包含源码(.c文件),linux环境下编译生成的可执行文件,头文件,以及测试用的main.c文件 用于C语言以及数据结构的学习 循环队列的.c和.h文件实现了以下功能: 创建循环队列 入队列...
主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项,需要的朋友可以参考下
本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。 分解代码没有包含在内的代码如下: #include #include #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status; 2.代码...
# 常见数据结构与算法C语言实现 内容包含常见基本数据结构实现(C语言版)如各自排序、链表、栈、队列、各种树以及应用、图算法、字符串匹配算法、回溯、并查集等 以及包含各个数据结构常见算法题的解答(C语言版...
数据结构 严蔚敏 C语言版 链队列表示与实现 很给劲哦 绝对不会令您失望的。
软 件 学 院 上 机 实 验 报 告 课程名称: 数据结构 实验项目: 队列的应用 实 验 室: 耘 慧420 姓 名: 学 号 专业班级: 实验时间: 2016.11.17 "实验成绩 "评阅教师 " " " " "实验目的及要求 " "(一) 目的 " "1...
用C语言编写数据结构代码。C语言实现数据结构的代码,像单链表,栈,队列,二叉树,图等数据结构,用c来实现