【数据结构】银行排队取票机的原理是什么？详解队列

miya 发布于2021-09-14 17:57 / 848人阅读

摘要：哦，我之前还真没来过银行，第一次见这个取号机。取号机吐出来一张写有号码的单子，然后等到柜台工作人员用电子提示音叫到你的号码时，就是轮到你去办理业务了。数据入队列的一端叫做队尾，数据出队列的一端叫做队头。现在，取票机组建了一个队列。

1.摘要

本文主要介绍队列的概念以及队列的代码实现

2.银行排队取票机的原理

最近临近开学，大一的小伙伴们一定在收到录取通知书的同时，也受到了一张来自学校的学子卡吧，那大家有没有亲自去线下网点激活学子卡呢？

我一踏进银行的自动门，工作人员就让我在前面的一台机器上扫码区号了。哦，我之前还真没来过银行，第一次见这个取号机。取号机吐出来一张写有号码的单子，然后等到柜台工作人员用电子提示音叫到你的号码时，就是轮到你去办理业务了。

那我不禁在想了，为什么银行要推出这样一台排队取票机呢？

放在以前，来到银行，都是往一个柜台后面排队，等排前面的人办理完了，自然轮到了你。但大家有没有想过，比如你和你的朋友恰好都来银行办理业务，你在1号窗口排队，你的朋友比你晚到10分钟，在2号窗口排队。这时，1号窗口排在你的前面的客户出了点问题，工作人员花了半个小时才解决了问题。这时，你转头一看，你的朋友已经办完业务转身离开了，而你还在排队！

明明你比你朋友先到的啊！

于是，银行为了保证先来后到的公平，推出了排队取票机。先来的人领取到号小的票，后来的人领取到号大的票，只要柜台一有空闲，
柜员就会按按钮让当前等候的手持号最小票的客户上前办理业务。

“请xx号客户前往xx号柜台办理业务···请xx号客户前往xx号柜台办理业务···”

这就避免了业务办理速度对排队公平的影响。

3.队列的概念

谈了这么一大堆，有人不禁要问了：我们今天不是要聊队列的吗？队列在哪里啊？

唉，别急啊，队列，排队排好，先来后到，难道不是队列了吗？

让我们先给出队列的定义：队列是只允许一端进行插入数据操作，另一端进行删除数据操作的特殊线性表。

队列具有先进先出的性质(First in First out)。

数据入队列的一端叫做队尾，数据出队列的一端叫做队头。

再次想象一下银行排队的问题，我们把一个个排队的客户想象成一个个数据元素。

现在，取票机组建了一个队列。先来的客户先进入队列，后来的客户后进入队列。

当柜员叫号时，叫的永远是位于队头的客户的号码，该客户便出队列。如果又来了一个新客户，那么他取号后，便在队尾入队列。

循此以往，先来后到的准则将被严格地遵守。

先进先出！先进先出！先进先出！重要的事情说三遍！

4.队列的代码实现

4.1.队列结构体

我们想一下，队列最最重要的操作是什么呢？

对了，是入队列和出队列

入队列是在队头，需要操作头部元素。出队列是在队尾，需要操作尾部元素。

我们知道，队列是特殊的线性表。那么想一下，如果用顺序表来实现的话，头插操作的时间复杂度华为O(N)，太麻烦了。那改用链表呢？有人说，链表的尾插不也是O(N)的时间复杂度吗？对，那么，我们就在头指针的基础上，再加一个尾指针！

既有头指针，又有尾指针，那何不把头指针和尾指针封装到同一个结构体里去呢？

这样的操作带来了另外一个好处：只需传入该结构体的地址，就能修改头/尾指针以及头尾指针对应的节点的内容，避免了使用二级指针带来的不便。

于是，便有了一下的结构体的创建：

a)队列节点的结构体

typedef struct QueueNode{	QueueDataType data;	struct QueueNode* next;}QueueNode;

b)队列头/尾指针的结构体

typedef struct Queue{	QueueNode* head;	QueueNode* tail;}Queue;

4.2.头文件

#pragma once#include #include #include #include typedef int QueueDataType;typedef struct QueueNode{	QueueDataType data;	struct QueueNode* next;}QueueNode;typedef struct Queue{	QueueNode* head;	QueueNode* tail;}Queue;void QueueInit(Queue* que);void QueueDestroy(Queue* que);void QueuePush(Queue* que, QueueDataType x);void QueuePop(Queue* que);QueueDataType QueueTop(Queue* que);int QueueEmpty(Queue* que);size_t QueueSize(Queue* que);

4.3.接口文件

void QueueInit(Queue* que){	assert(que);	que->head = NULL;	que->tail = NULL;}void QueueDestroy(Queue* que){	assert(que);	QueueNode* cur = que->head;	while (cur)	{		QueueNode* next = cur->next;		free(cur);		cur = next;	}	que->tail = NULL;}void QueuePush(Queue* que, QueueDataType x){	assert(que);	if (que->head == NULL)	{		que->head = que->tail = (QueueNode*)malloc(sizeof(QueueNode));		que->head->data = x;		que->head->next = NULL;	}	else	{		que->tail->next = (QueueNode*)malloc(sizeof(QueueNode));		que->tail = que->tail->next;		que->tail->data = x;		que->tail->next = NULL;	}}void QueuePop(Queue* que){	assert(que);	assert(!QueueEmpty(que));	QueueNode* next = que->head->next;	free(que->head);	que->head = next;}QueueDataType QueueTop(Queue* que){	assert(que);	assert(!QueueEmpty(que));	return que->head->data;}int QueueEmpty(Queue* que){	return que->head == NULL;}size_t QueueSize(Queue* que){	assert(que);	QueueNode* cur = que->head;	size_t count = 0;	while(cur)	{		++count;		cur = cur->next;	}	return count;}

4.4.测试文件

void Test1(){	Queue q;	QueueInit(&q);	QueuePush(&q, 1);	QueuePush(&q, 2);	QueuePush(&q, 3);	QueuePush(&q, 4);	printf("%d/n", QueueSize(&q));	printf("%d/n", QueueTop(&q));	QueuePop(&q);	printf("%d/n", QueueTop(&q));	QueuePop(&q);	printf("%d/n", QueueTop(&q));	QueuePop(&q);	printf("%d/n", QueueTop(&q));	QueuePop(&q);	printf("%d/n", QueueSize(&q));	QueueDestroy(&q);}int main(){	Test1();	return 0;}

私有云云服务器电影院取票机取票流程银行排队 95382是什么银行消息队列是什么

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119943.html

ES6的常用语法

摘要：和命令和类似于中的的使用都是用来声明变量的，只是都存在各自的特殊用法。解构数组和对象是中最常用也是最重要表示形式。实例生成以后，可以用方法分别指定状态和状态的回调函数。这个迭代器对象拥有一个叫做的方法来帮助你重启函数并得到下一个值。 let和const命令 let和const类似于javascript中的var的使用,都是用来声明变量的，只是都存在各自的特殊用法。在javascrip...

gougoujiang 2019-08-22 17:09 评论0 收藏0
前端进阶系列(八):JS执行机制

摘要：一直以来，对的执行机制都是模棱两可，知道今天看了文章这一次，彻底弄懂执行机制和的规范和实现，才对的执行机制有了深入的理解，下面是我的学习总结。个要点是单线程语言是的执行机制，为了实现主线程的不阻塞，就这么诞生了。一直以来，对JS的执行机制都是模棱两可，知道今天看了文章—《这一次，彻底弄懂JavaScript执行机制》和《Event Loop的规范和实现》，才对JS的执行机制有了深入的...

JackJiang 2019-08-23 12:25 评论0 收藏0
图解AQS原理之ReentrantLock详解-公平锁

摘要：概述前面已经讲解了关于的非公平锁模式，关于非公平锁，内部其实告诉我们谁先争抢到锁谁就先获得资源，下面就来分析一下公平锁内部是如何实现公平的如果没有看过非公平锁的先去了解下非公平锁，因为这篇文章前面不会讲太多内部结构，直接会对源码进行分析前文概述前面已经讲解了关于AQS的非公平锁模式，关于NonfairSync非公平锁，内部其实告诉我们谁先争抢到锁谁就先获得资源，下面就来分析一下公平...

Taonce 2019-08-16 17:48 评论0 收藏0
Java版-数据结构-队列（数组队列）

摘要：队列的操作方式和栈类似，唯一的区别在于队列只允许新数据在后端进行添加。前言看过笔者前两篇介绍的Java版数据结构数组和栈的盆友，都给予了笔者一致的好评，在这里笔者感谢大家的认可！！！由于本章介绍的数据结构是队列，在队列的实现上会基于前面写的动态数组来实现，而队列又和栈不论是从特点上和操作上都有类似之处，所以在这里对这两种数据结构不了解的朋友，可以去看一下笔者前两篇文章介绍的数据结...

khs1994 2019-08-16 16:10 评论0 收藏0
(十六)java多线程之优先队列PriorityBlockingQueue

摘要：本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言在银行排队办理业务通常会有一个通道让一些有贵宾卡的优先办理业务而不需要排队这就是我们今天要讲的优先队列例子假设在这么一个场景下银行开始办理业务之前已经来了个客户而且银行认本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github...

helloworldcoding 2019-08-16 10:32 评论0 收藏0