`
yangzhizhen
  • 浏览: 75552 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

数据结构之队列(C实现)

    博客分类:
  • C
阅读更多

一、队列是什么

    队列是一种可以实现“先进先出”的存储结构。其实,说简单点,队列就是排队,跟我们日常生活中到银行取钱排队,排队打饭在道理上是一样的。

    队列通常可以分为两种类型:
       ①链式队列(由链表实现)。
       ②静态队列(由数组实现),静态队列通常都必须是循环队列。
    由于链式队列跟链表差不多,所以在这里只针对循环队列来说明并实践。
    循环队列的两个参数:
       ①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语言数据结构的队列实现,新建队列,入队列,出队列,删除队列

    数据结构队列用C语言描述.rar

    总之,"数据结构队列用C语言描述"这个项目提供了一个学习和实践数据结构的好机会,不仅能够巩固C语言基础,还能深入理解数据结构的原理和应用。通过实际操作和调试代码,可以提升编程技能,为未来的IT职业生涯打下...

    数据结构中队列c语言实现

    在计算机科学中,数据结构是组织、...C语言虽然不提供内置的队列实现,但通过自定义结构体和操作函数,我们可以轻松地创建自己的队列数据结构。理解并熟练掌握这些基本操作对于学习更高级的数据结构和算法至关重要。

    数据结构 队列实现 数据结构 队列实现

    ### 数据结构:队列实现详解 #### 一、队列概念与特性 在计算机科学领域,**队列**是一种常见的线性数据结构,遵循先进先出(First In First Out, FIFO)的原则。也就是说,最早添加到队列中的元素将是最先被移除的...

    C语言-数据结构-栈队列实现

    本主题关注的是如何使用C语言来实现数据结构中的栈和队列,这是两种基础但非常重要的抽象数据类型(ADT)。 栈(Stack)是具有后进先出(LIFO)特性的数据结构。它类似于一个堆叠的盘子,最新的元素被放在顶部,...

    数据结构 严蔚敏 C语言版 循环队列

    通过严蔚敏教授的《数据结构》中的讲解,读者不仅可以理解循环队列的基本原理,还能学习到如何在C语言中有效地实现这一数据结构。书中可能包含了各种操作循环队列的示例代码,通过分析和实践这些代码,可以加深对...

    数据结构-队列的实现代码(C语言版).rar

    数据结构 -- C语言版 -- 队列的部分实现代码,详细介绍参考数据结构--队列的系列博文。链接为:https://blog.csdn.net/songshuai0223/category_9742561.html。

    数据结构循环队列的C语言实现

    数据结构循环队列的C语言实现

    C语言数据结构用队列求解迷宫最短路径

    从给定的代码片段来看,这是一段使用C语言实现迷宫最短路径求解的程序,主要通过队列(Queue)与栈(Stack)的数据结构来完成算法的设计与实现。下面将对这段代码涉及的关键知识点进行详细解析。 ### C语言中的数据...

    数据结构实验 队列 c语言写的控制台程序

    在C语言中实现队列,我们可以选择动态数组或者链表作为底层数据结构。动态数组允许我们在运行时调整大小,而链表则提供了更灵活的插入和删除操作。这个实验可能包括以下基本操作: 1. 初始化队列:创建一个新的空...

    数据结构:链队列

    链队列,顾名思义,是基于链表实现的队列数据结构。队列是一种遵循“先进先出”(FIFO,First In First Out)原则的数据结构,类似于现实生活中的排队等待。在链队列中,元素按照加入的顺序排列,第一个加入的元素被...

    C语言数据结构优先队列实现

    在C语言中实现优先队列,通常会选择使用堆数据结构,因为它可以保证插入、删除和查找操作的时间复杂度为O(logn),其中n是队列中的元素数量。堆是一种近似完全二叉树的结构,可以分为大顶堆和小顶堆。小顶堆的性质是...

    C语言实现栈与队列

    本项目是用C语言实现的栈和队列,提供了可加载和使用的源代码,这对于理解这两种数据结构的工作原理以及在C语言中如何实现它们非常有帮助。 首先,让我们详细了解栈和队列的概念: 1. 栈(Stack):栈是一种后进先...

    数据结构---队列的应用--c实现

    ### 数据结构——队列的应用与C语言实现 #### 背景介绍 本文将通过一个经典的算法问题“农夫过河”来探讨队列在实际编程中的应用,并使用C语言进行实现。这个问题不仅考验对数据结构的理解,还涉及到位运算等计算机...

    C++数据结构与算法之双缓存队列实现方法详解

    C++数据结构与算法之双缓存队列实现方法详解 本文主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项。 知识点一:双缓存队列的定义 双缓存队列是一...

    简单的数据结构单链队列的VC实现

    单链队列是一种常用的数据结构,它在计算机科学中扮演着重要的角色,特别是在处理序列操作时。本节我们将深入探讨单链队列的概念、它的实现原理以及如何在VC6.0环境下进行具体实现。 首先,我们需要理解数据结构中...

    51单片机串口接收使用队列C语言实现

    本文将深入探讨如何使用C语言实现51单片机的串口接收,并结合队列的数据结构来处理接收到的数据。队列作为一种先进先出(FIFO)的数据结构,非常适合用于串口接收中的数据缓冲,可以有效避免数据丢失和处理冲突。 ...

    数据结构栈和队列解决迷宫问题

    数据结构栈和队列解决迷宫问题 本文档详细介绍了利用栈和队列解决迷宫问题的步骤,对于初学者学习数据结构能很好的进行辅导。本文档主要涉及到数据结构的两个重要概念:栈和队列,并介绍了如何使用这两个数据结构来...

Global site tag (gtag.js) - Google Analytics