[数据结构]C语言队列的实现

我个人把链表、队列、栈分为一类,然后图、树分为一类。(串不考虑),分类的理由就是每一类有规律可循,即你能通过修改极少数的代码把链表变成队列、栈。(这里我们不考虑其他诸如设计模式等因素),因此本贴在讲完队列之后还会归纳一下这一类数据结构的规律,帮助大家更好理解数据结构

首先需要知道队列是什么,这里给一个定义:队列是只允许一段进行插入操作,一段进行删除操作的线性表,队列是先进先出的结构,允许插入成为队尾,允许删除成为队头

如上图就是一个队列,这里我相信你已经对队列有了一个概念了吧,于是就可以继续看下面了

队列同样存在插入删除操作,由于我们这里讨论的是链式队列的实现,所以不存在队列满的情况

学了这么多章数据结构我相信你能很容易的写出队列的结构了:

struct node{
	char data;
	struct node *next;
};

struct queue{
	struct node *front;
	struct node *rear;
};

就如上完成了一个队列的结构定义,然后是创建一个空队列:

struct queue *create_queue(){
	struct queue *q=new queue;
	q->front=NULL;
	q->rear=NULL;
	return q;
}

这没什么说的,队头队尾都指向NULL表示空队列。

然后来考虑入队操作:

如上图,我们希望把e节点插入到这个队列里面,其实细心的朋友可能已经发现了这其实就是链表的尾部插入,没错,等一下我会总结一下这些规律 ,这里暂且不谈。

我们能很容易写出下面插入节点到队列的代码(如果不能你就要发反思是否认真学习了):

void en_queue(struct queue *q,char c){
    struct node *e=new node;
    if(!n){
        return;
    }
    e->data=c;
    e->next=NULL;
    if(q->rear==NULL){
    	q->front=q->rear=e;
    }else{
    	q->rear->next=e;
    	q->rear=e;
    }
}

这里稍作解释,后面的if用于判断是否队列为空,如果为空就让队头等于队尾等于新节点,然后新节点为队尾。如果队列不是空就按链表式尾插法进行插入

然后出队:

看着上面的图片如果你能与链表联系起来并想到这就是链表的头插法的逆向,那就说明你真的学懂了

我们只需要把front的next指向a2,然后把,然后删除a1即可完成出队,同样,要想删除a1就应该创建一个临时变量

代码如下:

void out_queue(struct queue *q){
   struct node * temp;
 
   if(q->front==NULL)
      return;
   if(q->front==q->rear)
   {
      q->front=q->rear=NULL;
      return;
   }
 
   temp=q->front;
   q->front=temp->next;
   delete temp;
}

这里也简单解释一下,首先判断如果队列为空就不存在出队了,所以直接返回,如果队头等于队尾,也就是只有一个元素,就让队头队尾指向NULL(其实这里还可以删除队头),最后返回

遍历操作也顺利成章:

void print(struct queue *q){
    struct node *n=q->front;
    while(n!=NULL){
       std::cout<< n->data;
       n=n->next;
    }
}

至此队列结束,考虑到排版问题,对着三种结构的总结放到下面一片文章。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenssy

【死磕Sharding-jdbc】---group by的SQL重写为limit Integer.MAX_VALUE的无奈

这篇文章源于【死磕Sharding-jdbc】-----重写的遗留问题,相关sharding-jdbc源码如下:

9730
来自专栏熊二哥

单例模式深入理解

最近去平安系面试时,遇到了个人技术领域认定的一大偶像吴大师(Cat作者),他随口问了个单例的问题,要求基于Java技术栈,给出几种单例的方案,并给出单元测试代码...

246100
来自专栏滕先生的博客

runtime官方文档翻译版本通过OC源代码通过NSObject中定义的方法直接调用运行时的函数消息传递机制使用隐藏参数获取方法地址动态方法解析动态加载消息转发转发和多继承代理对象转发和继承类型编码声

29670
来自专栏CSDN技术头条

JavaScript内存管理机制以及四种常见的内存泄漏解析

几个星期前,我们开始编写深入研究JavaScript工作原理的系列文章。通过阅读这些文章,你可以了解到JavaScript的构建块及其交互原理,从而能够编写出更...

206100
来自专栏Java Web

Java 7的新特性

前言 看大佬推荐的书单买了一本《Java 8实战》,总觉得在了解Java 8之前,是不是也应该去了解了解一下Java 7的一些特性?所以就自己百度了一些资料来...

36550
来自专栏黑白安全

php代码审计之弱类型引发的灾难

有人说php是世界上最好的语言,这可能是对开发人员来说,确实有这方面的特点,因为它开发起来不像其他语言那样麻烦,就比如:弱类型,它不需要像java等语言那样明确...

9420
来自专栏杂烩

duubo分组聚合 原

除了官网上有这部分的简单介绍外,在别的地方几乎找到真正可行的测试了,这里自己捣鼓一下,已做备忘。

9010
来自专栏java一日一条

Java初学者必知:Java语言的11大特点

Java是一种简单的,面向对象的,分布式的,解释型的,健壮安全的,结构中立的,可移植的,性能优异、多线程的静态语言。那么java语言的特点是什么呢?

9020
来自专栏小勇DW3

自己平时用到的设计模式总结

作为对象的创建模式,单例模式确保其某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例,这个类称为单例类。单例模式有以下特点:

14540
来自专栏Python

python常用模块

 python常用模块 什么是模块?    常见的场景:一个模块就是一个包含了python定义和声明的文件,文件名就是模块名字加上.py的后缀。    但其实i...

385110

扫码关注云+社区

领取腾讯云代金券