网站制作工作室制作平台,查企业哪个app最好,dw网页制作教程完整版,陕西做网站的公司地址队列#xff08;Queue#xff09;是一种特殊的线性表#xff0c;它的主要特点是先进先出#xff08;First In First Out#xff0c;FIFO#xff09;。队列只允许在一端#xff08;队尾#xff09;进行插入操作#xff0c;而在另一端#xff08;队头#xff09;进行删…队列Queue是一种特殊的线性表它的主要特点是先进先出First In First OutFIFO。队列只允许在一端队尾进行插入操作而在另一端队头进行删除操作。以下是对队列的详细介绍
一、基本概念
队列的定义队列是一种只允许在表的一端队尾进行插入操作在另一端队头进行删除操作的线性表。队头Front队列中允许删除的一端又称为队首。队尾Rear队列中允许插入的一端。空队列不包含任何元素的队列。
二、队列的主要操作
队列的主要操作包括入队Enqueue、出队Dequeue、查看队头元素Peek/Front和判断队列是否为空IsEmpty等。
入队Enqueue在队列的队尾插入一个新元素。出队Dequeue从队列的队头删除一个元素并返回该元素的值。查看队头元素Peek/Front返回队列队头元素的值但不删除该元素。判断队列是否为空IsEmpty如果队列中没有任何元素则返回true否则返回false。
三、队列的分类存储结构
队列根据实现方式的不同可以分为多种类型如顺序队列、循环队列、链式队列等。 顺序队列 使用数组实现的队列队头和队尾指针分别指向队列的首尾元素。顺序队列在插入和删除操作时可能会出现“假溢出”现象即队列未满但因指针限制无法继续插入元素的情况。
初始化
//initialize
#define MaxSize 50
typedef struct
{int rear,front;//rear指向队尾元素的下一个值front指向队头元素Elemtype data[MaxSize];
}SqQueue;循环队列 为了解决顺序队列的“假溢出”问题引入了循环队列。在循环队列中当队尾指针到达数组末尾时会自动回到数组的开始位置形成一个环状结构。循环队列需要牺牲一个存储单元来区分队列空和队列满的状态。
初始frontrear0
队首指针进1frontfront1%MaxSize
队尾指针进1rearrear1%MaxSize
队长rear-frontMax Size%MaxSize
队空判断条件
循环队列为空的判断条件相对简单即队头指针front和队尾指针rear相等。这是因为当队列为空时没有元素被插入所以队头和队尾都指向数组的起始位置或某个约定的初始位置。
队空判断条件front rear
队满判断条件
循环队列为满的判断条件则较为复杂。由于队尾指针在达到数组末尾后会回到数组开头因此当队尾指针再次指向队头指针时队列可能已满也可能为空。为了区分这两种情况通常采用以下几种方法之一来判断队列是否满 牺牲一个元素空间 这是最常见的方法。在循环队列中约定当(rear 1) % MaxSize front时认为队列已满。这里MaxSize是队列所使用数组的大小%是取模运算符。这种方法通过牺牲数组中的一个元素空间来区分队列满和队列空的状态。当(rear 1) % MaxSize front时虽然从逻辑上看队尾指针和队头指针相邻但实际上队列中还有一个空位置没有被使用因此认为队列已满。 队满判断条件牺牲一个元素空间(rear 1) % MaxSize front 队空判断条件front rear 队长(rear-frontMaxSize)%MaxSize 增设计数器或标志位size) 另一种方法是增设一个计数器记录队列中元素的数量或标志位记录队列的当前状态如是否进行过插入或删除操作。然而这种方法需要额外的存储空间并且增加了操作的复杂性。队空size0; 队满sizemaxSize; 改变front和rear的定义域 还有一种较为特殊的方法是通过改变front和rear的定义域来区分队列满和队列空的状态。例如可以约定front的初始值为数组的最大索引加1或某个大于数组最大索引的值而rear的初始值为0。这样当front等于rear时队列为空而当rear再次等于front时在循环过程中队列满。但这种方法在实际应用中较为少见因为它改变了front和rear的常规用法。
综上所述循环队列队空和队满的判断条件主要取决于所采用的具体实现方法。其中“牺牲一个元素空间”的方法因其简单性和高效性而被广泛采用。
图解 代码
//initialize
void InitQueue(SqQueue Q){Q.frontQ.rear0;
}
//判断是否为空
bool isEempty(SqQueue Q){if(Q.rearQ.front)return true;elsereturn false;}
//入队
bool EnQueue(SqQueue Q,Elemtype x){if ((Q.rear1)%MaxSizeQ.front)return false; Q.data[Q.rear]x;Q.rear(Q.rear1)%MaxSize;return true;}
//出队
bool DeQueue(SqQueue Q,Elemtype x){if(Q.frontQ.rear)return false;xQ.data[Q.front];Q.front(Q.front1)%MaxSize;return true;
} 链式队列 使用链表实现的队列每个节点包含数据域和指向下一个节点的指针。链式队列在插入和删除操作时不需要移动元素具有较好的灵活性。
代码
//
typedef struct{Elemtype data;struct LinkNode *next;
}LinkNode;
typedef struct
{LinkNode *rear,*front;
}LinkQueue;//initialize
void InitQueue(LinkQueue Q){Q.frontQ.rear(LinkNode*)malloc(sizeof(LinkNode));//建立头结点Q.front-nextNULL;
}bool IsEmpty(LinkQueue Q){if(Q.frontQ.rear)return true;elsereturn false;
}void EnQueue(LinkQueue Q,ElemType e){LinkNode *s(LinkNode *)malloc(sizeof(LinkNode));s-datae;s-nextNULL;Q.rear-nexts;Q.rears;
}void DeQueue(LinkQueue Q,ElemType e){if(Q.frontQ.rear)return false;LinkNode *sQ.front-next;es-data;Q.front-nexts-next;if(Q.rears)//队列中只有一个结点Q.frontQ.rear;//删除后变空free(s);return true;
}
双端队列
1能由输入受限的双端队列得到但不能由输出受限的双端队列得到的是4,1,3,2。
2能由输出受限的双端队列得到但不能由输入受限的双端队列得到的是4,2,1,3。
3既不能由输入受限的双端队列得到又不能由输出受限的双端队列得到的是4,2,3,1。
四、队列的应用场景
队列在实际应用中有着广泛的应用如
任务调度在多任务系统中可以使用队列来存储待执行的任务系统按照队列中的顺序依次执行任务。消息传递在分布式系统中队列可以用作消息传递的媒介发送方将消息发送到队列中接收方从队列中取出消息并进行处理。缓存淘汰在缓存系统中可以使用队列的先进先出特性来淘汰最早进入缓存的数据项。并发控制在多线程或多进程环境中队列可以用于控制对共享资源的访问顺序防止数据竞争和死锁等问题。
队列在计算机系统中的应用
队列在计算机系统中的应用非常广泛以下仅从两个方面来阐述第一个方面是解决主机与外部设备之间速度不匹配的问题第二个方面是解决由多用户引起的资源竞争问题。 缓冲区的逻辑结构2009) 对于第一个方面仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印输出数据的速度比打印数据的速度要快得多因为速度不匹配若直接把输出的数据送给打印机打印则显然是不行的。解决的方法是设置一个打印数据缓冲区主机把要打印输出的数据依次写入这个缓冲区写满后就暂停输出转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确又使主机提高了效率。由此可见打印数据缓冲区中所存储的数据就是一个队列。 多队列出队入队操作的应用2016) 对于第二个方面 CPU 即中央处理器它包括运算器和控制器资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上有多个用户需要 CPU 各自运行自己的程序它们分别通过各自的终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序把它们排成一个队列每次把 CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后令其出队再把 CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求又使CPU能够正常运行。
五、总结
队列是一种重要的数据结构它遵循先进先出的原则进行元素的操作。队列的实现方式多样包括顺序队列、循环队列和链式队列等。队列在实际应用中有着广泛的应用场景如任务调度、消息传递、缓存淘汰和并发控制等。通过合理使用队列可以提高系统的性能和稳定性。
