玩转循环队列：数据结构与算法的实践操作
最编程
2024-01-31 16:05:32
...
//循环队列的入队和出队算法设计
#include<iostream>
#include<Windows.h>
#define MaxSize 6 //定义本循环队列的最大容量
using namespace std;
typedef struct _LQueue { //循环队列
int sq[MaxSize];
int front; //循环队列的前指针
int rear; //循环队列的尾指针
}LqList;
//初始化循环队列
bool InitLqList(LqList *duilie) {
if (!duilie) return false;
duilie->front = duilie->rear = 0;
return true;
}
//插入元素到循环队列
bool InserLq(LqList* duilie, int &Element) {
if (!duilie) return false;
if ((duilie->rear + 1) % MaxSize == duilie->front) {
cout << "该队列元素已满! ";
} else {
duilie->sq[duilie->rear] = Element;
duilie->rear =( duilie->rear + 1)%MaxSize;
}
return true;
}
//打印队列
void PrintLq(LqList *duilie) {
if (!duilie) return;
cout << "本循环队列的元素依次是: ";
int i = duilie->front;
while (i != duilie->rear) {
cout <<" "<< duilie->sq[i];
i = (i + 1) % MaxSize;
}
return;
}
//获取循环队列的首元素,元素不出队
bool GetLqFirst(LqList *duilie, int &Element) {
if (!duilie) return false;
Element = duilie->sq[duilie->front];
return true;
}
//出队
bool outLq(LqList *duilie,int &Element){
if (!duilie) return false;
if (duilie->front == duilie->rear) {
cout << "该队列是空队列! ";
return false;
} else {
Element = duilie->sq[duilie->front];
duilie->front = (duilie->front + 1) % MaxSize;
}
return true;
}
//获取循环队列元素个数
void Getlen(LqList *duilie) {
cout << "循环队列的元素个数是: " << (duilie->rear - duilie->front + MaxSize) % MaxSize;
return;
}
int main(void) {
LqList *duilie =new LqList;
if (InitLqList(duilie)) {
cout << "初始化循环队列成功! " << endl;
} else {
cout << "初始化循环队列失败! " << endl;
}
//循环队列入队
int num; //用户想要入队或者出队的个数
cout << "请输入你想要入队的个数(本程序设置的循环队列最大容量为5): ";
cin >> num;
//直到用户输入正确的入队个数为止
while (1) {
if (num > MaxSize) {
cout << "输入的数量超过了本队列的最大容量,请重新输入入队的个数: " << endl;
cout << "请输入你想要入队的个数: ";
cin >> num;
} else {
break;
}
}
int Element = 0;
for (int i = 0; i < num; i++) {
cout << "请输入你想要插入的元素: ";
cin >> Element;
if (InserLq(duilie,Element)) {
cout << "插入元素 " << Element << " 成功! " << endl;
} else {
cout << "插入元素失败! " << endl;
}
}
//打印循环队列里的元素
PrintLq(duilie);
//获取循环队列的首元素,元素不出列
if (GetLqFirst(duilie,Element)) {
cout << "循环队列的首元素是: " << Element << endl;
} else {
cout << "获取循环队列首元素失败! " << endl;
}
//循环队列出队
cout << "请输入你想要出队的个数: ";
cin >> num;
cout << endl;
//直到用户输入正确的出队个数为止
while (1) {
if (num > (duilie->rear - duilie->front + MaxSize) % MaxSize) {
cout << "输入的数量超过了本队列的最大容量,请重新输入出队的个数: " << endl;
cout << "请输入你想要出队的个数: ";
cin >> num;
} else {
break;
}
}
for (int i = 0; i < num; i++) {
if (outLq(duilie, Element)) {
cout << "循环队列元素出队成功! 出队元素是: " << Element << endl;
} else {
cout << "循环队列元素出队失败! " << endl;
}
}
PrintLq(duilie);
Getlen(duilie);
cout << "在入队一个元素吧,这可是循环队列哟!" << endl;
cout << "请输入你想要插入的元素: ";
cin >> Element;
if (InserLq(duilie, Element)) {
cout << "插入元素 " << Element << " 成功! " << endl;
} else {
cout << "插入元素失败! " << endl;
}
PrintLq(duilie);
system("pause");
return 0;
}
上一篇： 初学者必看！轻松掌握循环队列
下一篇： 轻松理解循环队列的内部工作原理
推荐阅读
-
epoll简介及触发模式（accept、read、send）-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单，一共就三个函数：1. int epoll_create(int size);创建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数，给出最大监听的fd+1的值。需要注意的是，当创建好epoll句柄后，它就是会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在使用完epoll后，必须调用close关闭，否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数，它不同与select是在监听事件时告诉内核要监听什么类型的事件，而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值，第二个参数表示动作，用三个宏来表示：EPOLL_CTL_ADD：注册新的fd到epfd中；EPOLL_CTL_MOD：修改已经注册的fd的监听事件；EPOLL_CTL_DEL：从epfd中删除一个fd；第三个参数是需要监听的fd，第四个参数是告诉内核需要监听什么事，struct epoll_event结构如下：struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合：EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）； EPOLLIN事件：EPOLLIN事件则只有当对端有数据写入时才会触发，所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧？如果同步socket，而且要求读完所有数据，那么最终就会在堵死在阻塞里。 EPOLLOUT：表示对应的文件描述符可以写； EPOLLOUT事件：EPOLLOUT事件只有在连接时触发一次，表示可写，其他时候想要触发，那要先准备好下面条件：1.某次write，写满了发送缓冲区，返回错误码为EAGAIN。2.对端读取了一些数据，又重新可写了，此时会触发EPOLLOUT。简单地说：EPOLLOUT事件只有在不可写到可写的转变时刻，才会触发一次，所以叫边缘触发，这叫法没错的！其实，如果真的想强制触发一次，也是有办法的，直接调用epoll_ctl重新设置一下event就可以了，event跟原来的设置一模一样都行（但必须包含EPOLLOUT），关键是重新设置，就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件，也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；EPOLLERR：表示对应的文件描述符发生错误；EPOLLHUP：表示对应的文件描述符被挂断；EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生，类似于select调用。参数events用来从内核得到事件的集合，maxevents告之内核这个events有多大，这个maxevents的值不能大于创建epoll_create时的size，参数timeout是超时时间（毫秒，0会立即返回，-1将不确定，也有说法说是永久阻塞）。该函数返回需要处理的事件数目，如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中，得到ET和LT的具体描述如下EPOLL事件有两种模型：Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子：1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2)，并且它会返回RFD，说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式：如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志，那么在第5步调用epoll_wait(2)之后将有可能会挂起，因为剩余的数据还存在于文件的输入缓冲区内，而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候，调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中，会有一个事件产生在RFD句柄上，因为在第2步执行了一个写操作，然后，事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据，因此我们在第5步调用 epoll_wait(2)完成后，是否挂起是不确定的。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口，在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起，等待。但这并不是说每次read时都需要循环读，直到读到产生一个EAGAIN才认为此次事件处理完成，当read返回的读到的数据长度小于请求的数据长度时，就可以确定此时缓冲中已没有数据了，也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的，以LT方式调用epoll接口的时候，它就相当于一个速度比较快的poll(2)，并且无论后面的数据是否被使用，因此他们具有同样的职能。因为即使使用ET模式的epoll，在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志，在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后，使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式，并且同时支持block和no-block socket.在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作，内核还是会继续通知你的，所以，这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表．ET(edge-triggered)是高速工作方式，只支持no-block socket。在这种模式下，当描述符从未就绪变为就绪时，内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述符发送更多的就绪通知，直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如，你在发送，接收或者接收请求，或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误）。但是请注意，如果一直不对这个fd作IO操作(从而导致它再次变成未就绪)，内核不会发送更多的通知(only once),不过在TCP协议中，ET模式的加速效用仍需要更多的benchmark确认（这句话不理解）。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection，epoll的效率并不会比select/poll高很多，但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接)，就会发现epoll的效率大大高于select/poll。（未测试）另外，当使用epoll的ET模型来工作时，当产生了一个EPOLLIN事件后，读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小，那么很有可能是缓冲区还有数据未读完，也意味着该次事件还没有处理完，所以还需要再次读取： 这里只是说明思路（参考《UNIX网络编程》） while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有，假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发，当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回，返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时，写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
Java 数据结构与算法实践] 系列 007：Java 队列 01 - 队列概述 - 2.2.单端或双端
-
Java 数据结构与算法实践] 系列 013：Java 队列 07 - 双端队列 Deque-3.用作堆栈的队列
-
windows下进程间通信的（13种方法）-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术，并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换，由于这些进程处于同一软件和硬件环境下，利用操作系统提供的的编程接口，用户可以方便地在程序中实现这种通信；应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换，由于应用程序分别运行在不同计算机系统中，它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处，也各有自己的特色。即使是同一类型的通信也有多种的实现方法，以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术，本文将就以下几个方面对这两种通信进行深入的讨论：问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间，如果都不存在公共变量，则称该组进程为不相交的。在不相交的进程组中，每个进程都独立于其它进程，它的运行环境与顺序程序一样，而且它的运行环境也不为别的进程所改变。运行的结果是确定的，不会发生与时间相关的错误。 ---- 但是，在实际中，并发进程的各个进程之间并不是完全互相独立的，它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式： ---- （1） 间接相互制约：共享CPU ---- （2） 直接相互制约：竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源，各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程，它们之间必须交换数据，以达到协作完成任务的目的，交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现，进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口，由程序员在程序中实现。UNIX在这个方面可以说最具特色，它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制（IPC）。因此，我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中，文件（File）、信号（Signal）、无名管道（Unnamed Pipes）、有名管道（FIFOs）是传统IPC功能；新的IPC功能包括消息队列（Message queues）、共享存储段（Shared memory segment）和信号灯（Semapores）。 ---- （1） 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值，因此不能用于信息交换，仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键（如ctrl-c、del等）等都会产生一个信号，操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal，调用形式是： ---- signal(signalno,action) ---- 其中，signalno是规定信号编号的值，action指明当特定的信号发生时所执行的动作。 ---- （2） 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区，它由系统安全控制，并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理，并严格按顺序操作，例如不能对管道进行搜索，管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信，并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数，如： pipe——打开一个可以读写的管道； close——关闭相应的管道； read——从管道中读取字符； write——向管道中写入字符； ---- 有名管道的操作和无名管道类似，不同的地方在于使用有名管道的进程不需要具有共同的祖先，其它进程，只要知道该管道的名字，就可以访问它。管道非常适合进程之间快速交换信息。 ---- （3） 消息队列（MQ） ---- 消息队列是内存中独立于生成它的进程的一段存储区，一旦创建消息队列，任何进程，只要具有正确的的访问权限，都可以访问消息队列，消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类，这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在，直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用，如： ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构，并返回一个唯一的正整数msqid（MQ的标识符）； ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息； ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息； ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作； ---- （4） 共享存储段（SM） ---- 共享存储段是主存的一部分，它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联，对每个进程来说，共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有： ---- int shmget(key,size,flag)——创建大小为size的SM段，其相应的数据结构名为key，并返回共享内存区的标识符shmid； ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段； ---- int shmdr(address)——从进程地址空间删除SM段； ---- int shmctl (shmid,cmd,buf)——对SM的控制操作； ---- SM的大小只受主存限制，SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- （5） 信号灯 ---- 在UNIX中，信号灯是一组进程共享的数据结构，当几个进程竞争同一资源时（文件、共享内存或消息队列等），它们的操作便由信号灯来同步，以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源，所有请求该资源的其它进程都将被挂起，一旦该资源得到释放，系统才允许其它进程访问该资源。信号灯通常配对使用，以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是：操作系统提供实现机制和编程接口，由用户在程序中实现，保证进程间可以进行快速的信息交换和大量数据的共享。但是，上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样，不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口，程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字（Socket）编程。但是，相对普通程序员来说，它们涉及的技术比较深，编程也比较复杂，实现起来困难较大。 ---- 于是，一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部，即底层的通讯工作和相应的维护管理工作由该软件内部来实现，用户只需要将通信任务提交给该软件去完成，而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式，程序员参与的程度较深，而MQSeries消息队列则属于比较高级的方式，即中间件方式，程序员参与的程度较浅。 ---- 4．1 远程过程调用（RPC）
-
玩转数据结构与算法：图的邻居连接方式探索 - 邻接表与邻接矩阵详解
-
玩转数据结构与算法：从零开始理解图(一)- 图的建立与遍历方法：邻接矩阵法
-
详解常见图像滤波算法的实践操作与原理解析
-
玩转数据结构：探索顺序队列、循环队列和链队列的奥秘
-
九种数据结构之双端队列与循环队列的比较
-
玩转数据结构与算法：探索环形队列的魅力