AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】队列定义及其常用的基本操作（C/C++）

2023-01-13 179
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 队列定义及其常用的基本操作（C/C++）

●图示（以顺序队列为例）

df79472b03aac42eb8d89f1dae32d989_704240c506684fafa73c5f06bffc4383.png


●队列类型定义

●顺序队列

1.顺序队列存储结构的定义

typedef struct {
  qelemtype* base;
  int front;  //头指针
  int rear;   //尾指针
}SqQueue;

实例如下：

typedef struct {
  string name;
}qelemtype;
typedef struct {
  qelemtype* base;
  int front;
  int rear;
}SqQueue;

●链式队列

1.链式队列存储结构的定义

typedef struct Qnode {
  QElemType data;  //数据域
  struct Qnode* next; //指向下一结点的指针域
}Qnode, * QueneP;
typedef struct {
  QueneP front;  //头指针
  QueneP rear;   //尾指针
}LinkQueue;

实例如下：

typedef struct {
  string name;  
}QElemType;
typedef struct Qnode {
  QElemType data;  //数据域
  struct Qnode* next; //指向下一结点的指针域
}Qnode, * QueneP;
typedef struct {
  QueneP front;  //头指针
  QueneP rear;   //尾指针
}LinkQueue;

●常用的基本操作

●顺序队列

1.队列的初始化

void Initqueue(SqQueue& Q)
{
  Q.base = new qelemtype[MAXQSIZE];
  if (!Q.base)
  exit;
  Q.front = Q.rear = 0;
}

2. 求队列的长度

int QueueLength(SqQueue& Q)
{
  return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}

3. 队列入队

int EnQueue(SqQueue& Q, qelemtype e) {
  if ((Q.rear + 1) % MAXQSIZE == Q.front)
  {
  return 0;  //判断队满 
  }
  Q.base[Q.rear] = e; //新元素加入队尾 
  Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针加1
  return 1;
}

4. 队列出队

int DeQueue(SqQueue& Q, qelemtype& e) {
  if (Q.front == Q.rear)
  {
  return 0; //判断队空 
  }
  e = Q.base[Q.front];  //保存队头元素 
  Q.front = (Q.front + 1) % MAXQSIZE;   //队头指针加1 
  return 1;
}

5. 取队头元素

qelemtype GetHead(SqQueue &Q) {
  if (Q.front != Q.rear)
  return Q.base[Q.front];
}

6.清空队列

void clearQueue(SqQueue& Q)
{
  Q.front = 0;
  Q.rear = 0;
}

●链式队列

1.链队列初始化


int InitQueue(LinkQueue& Q) {
  Q.front = Q.rear = new Qnode;
  if (!Q.front)
  {
  exit(0);
  }
  Q.front->next = NULL;
  return 1;
}

2. 链队列入队

int EnQueue(LinkQueue& Q, QElemType e) {
  Qnode* p;
  p = new Qnode;
  if (!p) exit(OVERFLOW);
  p->data = e;
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
  return 1;
}

3. 链队列出队

int DeQueue(LinkQueue& Q, QElemType e) 
{
  Qnode* p;
  if (Q.front == Q.rear)
  {
  return 0;
  }
  p = Q.front->next;
  e = p->data;
  Q.front->next = p->next;
  if (Q.rear == p) Q.rear = Q.front;
  delete p;
  return 1;
}

4.求链队列的队头元素

void GetHead(LinkQueue Q) 
{
  QElemType e;
  e = Q.front->next->data;
  cout << e.name << endl;
}

●简单案例

1.顺序队列（这里实现用顺序队列依次入队5个学生，并查看此时队列人数，在进行出队操作，再查看此时队列人数。若进行其他操作，对代码进行简单修改即可）

#include<iostream>
#include<string>
#define MAXQSIZE 100   
using namespace std;
//数据准备
typedef struct {
  string name;
}qelemtype;
typedef struct {
  qelemtype* base;
  int front;
  int rear;
}SqQueue;
//队列的初始化
void Initqueue(SqQueue& Q)
{
  Q.base = new qelemtype[MAXQSIZE];
  if (!Q.base)
  exit;
  Q.front = Q.rear = 0;
}
//求队列的长度
int QueueLength(SqQueue& Q)
{
  return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
//队列入队
int EnQueue(SqQueue& Q, qelemtype e) {
  if ((Q.rear + 1) % MAXQSIZE == Q.front)
  {
  return 0;  //判断队满 
  }
  Q.base[Q.rear] = e; //新元素加入队尾 
  Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针加1
  return 1;
}
//队列出队
int DeQueue(SqQueue& Q, qelemtype& e) {
  if (Q.front == Q.rear)
  {
  return 0; //判断队空 
  }
  e = Q.base[Q.front];  //保存队头元素 
  Q.front = (Q.front + 1) % MAXQSIZE;   //队头指针加1 
  return 1;
}
//取队头元素
qelemtype GetHead(SqQueue &Q) {
  if (Q.front != Q.rear)
  return Q.base[Q.front];
}
//清空队列
void clearQueue(SqQueue& Q)
{
  Q.front = 0;
  Q.rear = 0;
}
void showfunc()
{
  cout << "1.队列的初始化" << endl;
  cout << "2.求队列的长度" << endl;
  cout << "3.队列入队" << endl;
  cout << "4.队列出队" << endl;
  cout << "5.取队头元素" << endl;
  cout << "6.清空队列" << endl;
}
void text()
{
  SqQueue Q;
  qelemtype q;
  while (1)
  {
  showfunc();
  cout << "#要执行的操作#" << endl;
  int n;
  cin >> n;
  switch (n) 
  {
  case 1:
    Initqueue(Q);
    cout << "初始化成功" << endl;
    break;
  case 2:
    int len;
    len=QueueLength(Q);
    cout << "此时队列长度为" << len << endl;
    break;
  case 3:
    cout << "请输入要入队的学生人数" << endl;
    int num;
    cin >> num;
    for (int i = 1; i <= num; i++)
    {
    cin >> q.name;
    EnQueue(Q, q);
    }
    cout << "入队成功" << endl;
    break;
  case 4:
    DeQueue(Q, q);
    cout << "出队成功" << endl;
    break;
  }
  system("pause");
  system("cls");
  }
}
int main()
{
  text();
}


2.链式队列 （这里实现用链式队列依次入队5个学生，并查看此时队头；进行二次出队操作后，再查看此时队头；若进行其他操作，对代码进行简单修改即可）

#include<iostream>
#include<string>
#define maxqsize 100
using namespace std;
//数据准备
typedef struct {
  string name;  
}QElemType;
typedef struct Qnode {
  QElemType data;  //数据域
  struct Qnode* next; //指向下一结点的指针域
}Qnode, * QueneP;
typedef struct {
  QueneP front;  //头指针
  QueneP rear;   //尾指针
}LinkQueue;
//链队列初始化s
int InitQueue(LinkQueue& Q) {
  Q.front = Q.rear = new Qnode;
  if (!Q.front)
  {
  exit(0);
  }
  Q.front->next = NULL;
  return 1;
}
//链队列入队
int EnQueue(LinkQueue& Q, QElemType e) {
  Qnode* p;
  p = new Qnode;
  if (!p) exit(OVERFLOW);
  p->data = e;
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
  return 1;
}
//链队列出队
int DeQueue(LinkQueue& Q, QElemType e) 
{
  Qnode* p;
  if (Q.front == Q.rear)
  {
  return 0;
  }
  p = Q.front->next;
  e = p->data;
  Q.front->next = p->next;
  if (Q.rear == p) Q.rear = Q.front;
  delete p;
  return 1;
}
//求链队列的队头元素
void GetHead(LinkQueue Q)
{
  QElemType e;
  e = Q.front->next->data;
  cout << e.name << endl;
}
void text()
{
  LinkQueue Q;
  QElemType d;
  InitQueue(Q);
  cout << "#初始化成功#" << endl;
  cout << "请输入入队人数:" << endl;
  int num;
  cin >> num;
  for (int i = 1; i <= num; i++)
  {
  cin >> d.name;
  EnQueue(Q,d);
  }
  cout << "#入队成功#" << endl;
  cout << "此刻队头元素为:" << endl;
  GetHead(Q);
  DeQueue(Q, d);
  cout << "#出队成功#" << endl;
  cout << "此刻队头元素为:"  << endl;
  GetHead(Q);
  DeQueue(Q, d);
  cout << "#出队成功#" << endl;
  cout << "此刻队头元素为:" << endl;
  GetHead(Q);
}
int main()
{
  text();
}

9ec9d9754927a9bd7d80a61cfd29b71c_625d5ecbf9004ca5a59c87daffe01c23.png

文章标签：
C++
存储
关键词：
数据结构队列
C++队列
C++定义
数据结构c++
数据结构定义
清风君
目录
相关文章
ephemerals__
|
28天前
|
存储 编译器 Linux
【c++】类和对象（上）（类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针）
本文介绍了C++中的类和对象，包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用，以及如何使用访问限定符控制成员的访问权限。此外，还讨论了对象的内存分配规则和this指针的使用场景，帮助读者深入理解面向对象编程的核心概念。
ephemerals__
66 4
最好zzz
|
1月前
|
缓存 安全 C++
C++无锁队列：解锁多线程编程新境界
【10月更文挑战第27天】
最好zzz
40 7
潇洒洒
|
1月前
|
消息中间件 存储 安全
深入探索C++无锁队列：多线程编程的高效利器
【10月更文挑战第19天】
潇洒洒
98 6
chian-ocean
|
17天前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器，包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构，以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板，展示了如何模拟实现这些容器适配器，重点讲解了优先队列的内部机制，如堆的构建与维护方法。
chian-ocean
28 0
徐霞客320
|
2月前
|
存储 编译器 C语言
C++入门2——类与对象1（类的定义和this指针）
C++入门2——类与对象1（类的定义和this指针）
徐霞客320
39 2
徐霞客320
|
2月前
|
C++
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
C++番外篇——对于继承中子类与父类对象同时定义其析构顺序的探究
徐霞客320
55 1
nanshaws
|
2月前
|
NoSQL Redis C++
Redis的实现五：二叉堆的数据结构和TTL、c，c++的实现
这篇文章详细探讨了二叉堆的数据结构及其在C和C++中的实现，特别强调了二叉堆在Redis中实现TTL（生存时间）功能的重要性，并通过代码示例展示了如何在Redis中使用二叉堆来管理键的过期时间。
nanshaws
42 0
小徐在进步
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
636 6
游客qeoynko2nmbgk
|
3月前
|
C++
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
HTML+JavaScript构建一个将C/C++定义的ANSI字符串转换为MASM32定义的DWUniCode字符串的工具
游客qeoynko2nmbgk
35 0
yantuguiguziPGJ
|
3月前
MITK中的数据结构和常量定义
本文介绍了MITK中的数据结构、反射机制、常量定义、DataNode类和类宏定义，包括多图映射、反射接口、事件宏和属性列表等高级特性。
yantuguiguziPGJ
21 0