数据结构探险（一）——队列

2023-12-28 19:58
文章标签 数据结构 队列 探险

本文主要是介绍数据结构探险（一）——队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • FIFO
  • 普通队列
  • 循环队列

c++实现循环队列

#ifndef MYQUEUE_H
#define MYQUEUE_H
/****************************************/
/*环形队列C++实现*/
/****************************************/class MyQueue
{
public:MyQueue(int queueCapacity);  //InitQueue(&Q)virtual ~MyQueue();         //DestroyQueue(&Q)void ClearQueue();     //ClearQueue(&Q)bool QueueEmpty() const;  //QueueEmpty(Q)bool QueueFull() const;int QueueLength() const;  //QueueLength(Q)bool EnQueue(int element);  //EnQueue(&Q,element)bool DeQueue(int &element);  //DeQueue(&Q,&element)void QueueTraverse();      //QueueTraverse(Q,visit())B
private:int *m_pQueue;//队列数组指针int m_iQueueLen;//队列元素个数int m_iQueueCapacity;//队列数组容量int m_iHead;int m_iTail;};#endif

#include<stdio.h>
#include<stdlib.h>
#include"MyQueue.h"
#include<iostream>using namespace std;MyQueue::MyQueue(int queueCapacity)
{m_iQueueCapacity =queueCapacity;m_pQueue = new int[m_iQueueCapacity];ClearQueue();
}MyQueue::~MyQueue()
{delete []m_pQueue;m_pQueue=NULL;
}void MyQueue::ClearQueue()
{m_iHead=0;m_iTail=0;m_iQueueLen=0;
}bool MyQueue::QueueEmpty() const
{if(m_iQueueLen==0)return true;elsereturn false;//return m_iQueueLen==0?true:false;
}int MyQueue::QueueLength() const
{return m_iQueueLen;
}bool MyQueue::QueueFull() const
{if(m_iQueueCapacity==m_iQueueLen)return true;else return false;
}bool MyQueue::EnQueue(int element)
{if(QueueFull()){return false;}else{m_pQueue[m_iTail]=element;m_iTail++;m_iTail=m_iTail%m_iQueueCapacity;m_iQueueLen++;return true;}
}bool MyQueue::DeQueue(int &element)//element必须是引用才可以带回值
{if(QueueEmpty()){return false;}else{element=m_pQueue[m_iHead];m_iHead++;m_iHead=m_iHead%m_iQueueCapacity;m_iQueueLen--;return true;}}void MyQueue::QueueTraverse()
{for(int i=m_iHead;i<m_iQueueLen;i++)//从队列头遍历{cout<<m_pQueue[i%m_iQueueCapacity]<<endl;}
}
#include<stdio.h>
#include<stdlib.h>
#include"MyQueue.h"
#include"MyQueue.cpp"/****************************/
/* 实现环形队列 */
/****************************/
using namespace std;int main(void)
{MyQueue *p =new MyQueue(4);p->EnQueue(10);p->EnQueue(12);p->EnQueue(16);p->EnQueue(18);p->EnQueue(20);p->QueueTraverse();int e=0;p->DeQueue(e);cout<<endl;cout<<e<<endl;delete p;p=NULL;system("pause");return 0;
}

在这里插入图片描述

当存入的数据不是int，而是其他复杂数据类型时

#ifndef CUSTOMER_H
#define CUSTOMER_H#include<iostream>
using namespace std;/************************************************/
/*customer类定义*/
/**********************************************/
class Customer
{
public:Customer(string name="",int age=0);void printfInfo() const;
private:string m_strName;int m_iAge;
};#endif
Customer::Customer(string name,int age)
{m_strName=name;m_iAge=age;
}void Customer::printfInfo() const
{cout<<"name:"<<m_strName<<endl;cout<<"age:"<<m_iAge<<endl;
}#ifndef MYQUEUE_H
#define MYQUEUE_H
/****************************************/
/*环形队列C++实现*/
/****************************************/class MyQueue
{
public:MyQueue(int queueCapacity);  //InitQueue(&Q)virtual ~MyQueue();         //DestroyQueue(&Q)void ClearQueue();     //ClearQueue(&Q)bool QueueEmpty() const;  //QueueEmpty(Q)bool QueueFull() const;int QueueLength() const;  //QueueLength(Q)bool EnQueue(Customer element);  //EnQueue(&Q,element)bool DeQueue(Customer &element);  //DeQueue(&Q,&element)void QueueTraverse();      //QueueTraverse(Q,visit())B
private:Customer *m_pQueue;//队列数组指针int m_iQueueLen;//队列元素个数int m_iQueueCapacity;//队列数组容量int m_iHead;int m_iTail;};#endifusing namespace std;MyQueue::MyQueue(int queueCapacity)
{m_iQueueCapacity =queueCapacity;m_pQueue = new Customer[m_iQueueCapacity];ClearQueue();
}MyQueue::~MyQueue()
{delete []m_pQueue;m_pQueue=NULL;
}void MyQueue::ClearQueue()
{m_iHead=0;m_iTail=0;m_iQueueLen=0;
}bool MyQueue::QueueEmpty() const
{if(m_iQueueLen==0)return true;elsereturn false;//return m_iQueueLen==0?true:false;
}int MyQueue::QueueLength() const
{return m_iQueueLen;
}bool MyQueue::QueueFull() const
{if(m_iQueueCapacity==m_iQueueLen)return true;elsereturn false;
}bool MyQueue::EnQueue(Customer element)
{if(QueueFull()){return false;}else{m_pQueue[m_iTail]=element;m_iTail++;m_iTail=m_iTail%m_iQueueCapacity;m_iQueueLen++;return true;}
}bool MyQueue::DeQueue(Customer &element)//element必须是引用才可以带回值
{if(QueueEmpty()){return false;}else{element=m_pQueue[m_iHead];m_iHead++;m_iHead=m_iHead%m_iQueueCapacity;m_iQueueLen--;return true;}}void MyQueue::QueueTraverse()
{for(int i=m_iHead;i<m_iHead+m_iQueueLen;i++)//从队列头遍历{m_pQueue[i%m_iQueueCapacity].printfInfo();cout<<"前面还有"<<(i-m_iHead)<<"人"<<endl;cout<<endl;}cout<<endl;
}
int main(void)
{MyQueue *p = new MyQueue(4);//使用myQueue 指定个数Customer c1("zhangsan",20);Customer c2("liis",30);Customer c3("cdcs",50);p->EnQueue(c1);p->EnQueue(c2);p->EnQueue(c3);p->QueueTraverse();cout<<"------------------"<<endl;Customer c4("",0);p->DeQueue(c4);c4.printfInfo();cout<<"-------------------"<<endl;p->QueueTraverse();}

在这里插入图片描述

【注】：遇到的一些问题
c++默认构造器问题
在这里插入图片描述

在这里插入图片描述

修改成这样，为其制定默认值
在这里插入图片描述
即ok

这篇关于数据结构探险（一）——队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/547112。

相关文章

hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
Java并发编程之——BlockingQueue（队列）

Java并发编程之——BlockingQueue（队列）

一、什么是BlockingQueue BlockingQueue即阻塞队列，从阻塞这个词可以看出，在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种： 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被阻塞，除非有另一个线程做了出队列操作；同样，当一个线程试图对一个空
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2