首页 > C语言的单链表实现队列

C语言的单链表实现队列

队列是一种FIFO（先入先出）的数据结构

C++的STL std::queue q; 相关的队列操作，包括

q.empty() 判读队列是否为空
q.front() 返回队列的首元素
q.back() 返回队列的末尾元素
q.pop() 弹出队列的头部
q.push(x) 将x添加至队列
q.size() 返回队列的大小

本文使用C语言的链表，实现队列以上操作(文末有测试代码)

  • empty
    bool empty(Queue *head){ if (head == NULL)return true;else return false;
}
  • front 取队列的头元素，即返回链表的首节点
    Queue front(Queue *head) { Queue fro;if (NULL == head) { fro.next = NULL;return fro;}fro.data = head->data;//返回链表的首节点fro.next = head;return fro;
}
  • back 返回队列的尾元素，即返回链表的尾节点
    Queue back(Queue *head) { Queue back;if (NULL == head) { back.next = NULL;return back;}while (head -> next) //获取到链表的尾节点{ head = head ->next;}back.data = head->data;back.next = head;return back;
}
  • pop 弹出队列的首元素，即删除链表的头节点
    Queue *pop(Queue *head) { if (head ->next == NULL || head == NULL)head = NULL;head = head ->next; //删除链表的头节点return head;
}
  • push 插入指定元素到队列，即向使用尾插法插入新节点到链表
    Queue *push(Queue *head, Queue node) { if (head == NULL) { return NULL;}Queue *r = head;while(r -> next) {  //获取到链表的尾节点的上一个节点r = r -> next;}node.next = NULL;r ->next = &node; //使用尾插法，插入节点r = &node;return head;
}
  • size 返回队列的大小，计算链表的长度
    int size(Queue *head) { int s_num = 0;if (head == NULL) { return s_num;}while (head){ s_num ++;head = head->next;       }return s_num;
}

测试代码如下

#include 
#include typedef struct  List
{ int data;struct List *next;
}Queue;void print_list(Queue *p) { if (NULL == p) { printf("link list is NULL
");return ;}while (p){ printf("%d ", p -> data);p = p->next;}printf("
");
}Queue *insert_tail(int n) { Queue *head = (Queue *)malloc(sizeof(Queue));head ->next = NULL;Queue *r = head;while (n --){ Queue *p = (Queue *)malloc(sizeof(Queue));int tmp ;scanf("%d",&tmp);p -> data = tmp;p -> next = NULL;r -> next = p;r = p;}return head ->next;
}Queue *pop(Queue *head) { if (head ->next == NULL || head == NULL)head = NULL;head = head ->next;return head;
}Queue front(Queue *head) { Queue fro;if (NULL == head) { fro.next = NULL;return fro;}fro.data = head->data;fro.next = head;return fro;
}Queue back(Queue *head) { Queue back;if (NULL == head) { back.next = NULL;return back;}while (head -> next){ head = head ->next;}back.data = head->data;back.next = head;return back;
}Queue *push(Queue *head, Queue node) { if (head == NULL) { return NULL;}Queue *r = head;while(r -> next) { r = r -> next;}node.next = NULL;r ->next = &node;r = &node;return head;
}bool empty(Queue *head){ if (head == NULL)return true;else return false;
}int size(Queue *head) { int s_num = 0;if (head == NULL) { return s_num;}while (head){ s_num ++;head = head->next;       }return s_num;
}int main() { printf("constuct queue 
");Queue *p = insert_tail(3);Queue node;node.data = 10;printf("push 
");Queue *q = push(p,node);print_list(q);printf("constuct queue 
");p = insert_tail(3);printf("pop 
");Queue *po = pop(p);print_list(po);printf("front %d
",front(po).data);printf("size %d
",size(po));printf("back %d
",back(po).data);return 0;
}

输出如下：

constuct queue 
1 2 3
push 
1 2 3 10 
constuct queue 
1 2 3
pop 
2 3 
front 2
size 2
back 3

更多相关：

  • 剑指offer：面试题35. 复杂链表的复制

    题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...

  • leetcode-86 分隔链表

    给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...

  • leetcode-142 环形链表II

    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...

  • leetcode-92 反转链表II

    题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...

  • leetcode-206 反转链表

    描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...

  • 简单C++线程池包装类源码示例

    这里给出一个简单的C++线程池包装类,该类具有的特点是: 1.线程池大小是固定的, 一创建后,就不具有伸缩特性. 一般建议是 CPU核心数的2倍或1倍. 2.简单但是很可靠. 3.资源占用极低. 在开启100个线程时, 4核CPU的占用率只有20%不到, 30个线程时, 占用7%以下.实践证明, 使用信号量和互斥锁进行多线程的同...

  • Go 分布式学习利器（11）-- Go语言通过单链表 实现队列

    一个小实验，将之前学习的Go相关的语法做个总结。 包括： Go语言接口特性Go语言封装特性Go语言 变量，指针，函数 语法GO语言 条件和循环语句 的语法GO语言的测试程序 通过链表实现一个队列，元素在其中 拥有先进先出的特性。 简单实用。 package data_structureimport ("fmt""testing"...

  • C++ STL：stack和queue

    http://blog.csdn.net/wallwind/article/details/6858634 http://blog.csdn.net/chao_xun/article/details/8037420 http://blog.163.com/jackie_howe/blog/static/1994913472011114...

  • C++ 中NULL 和 nullptr 的区别

    在使用空时，习惯这么赋值  int *p = NULL;  编译器进行解释程序时，NULL会被直接解释成0，所以这里的参数根本就不是大家所想的NULL，参数已经被编译器偷偷换成了0，0是整数。  因此这面的问题就尴尬了 不好意思图片引用于网络中。 为啥呢不是this is the ptr function…这个。这就是C++中的...

  • js在post后台接口的时候，一行代码完成删除对象中所有值为null、undefined或为空字符串““的属性

    var d= {a: 1,b: null,c: 3,d: undefined };Object.keys(d).forEach(k=>d[k]==null&&delete d[k]);//去掉值为null或undefined的对象属性//Object.keys(d).forEach(k=>(d[k]==null||d[k]==='')...

  • 【全网最精简写法】ES6获取浏览器url跟参

    //ES6获取浏览器url跟参 public getUrlParam = a => (a = location.search.substr(1).match(new RegExp(`(^|&)${a}=([^&]*)(&|$)`)),a?a[2]:null);...

  • 设计模式 之美 -- 工厂方法模式

    文章目录1. 解决问题2. 应用场景3. 实现如下C++实现C语言实现4. 缺点 1. 解决问题 在简单工厂模式中，我们使用卖衣服进行举例，同一种工厂可以卖很多不同种类的衣服，工厂只是将衣服的生产过程进行了封装。 当我们增加衣服种类的时候，在简单工厂模式中需要修改工厂的代码，破坏了类的开闭原则（对扩展开发， 对修改关闭），...

  • AnsiToUtf8 和 Utf8ToAnsi

    在服务端数据库的处理当中，涉及中文字符的结构体字段，需要转为Utf8后再存储到表项中。从数据库中取出包含中文字符的字段后，如果需要保存到char *类型的结构体成员中，需要转为Ansi后再保存。从数据库中取出类型数字的字段后，如果需要保存到int型的结构体成员中，需要调用atoi函数进行处理后再保存。 1 static char *...

©2024 11GX.COM