devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【队列】c++使用数组实现队列_c++数组实现队列

作者：正经夜光杯 | 2024-06-25 14:04:34

赞

踩

c++数组实现队列

数组队列

目录

数组队列

基本概念

代码实现

1 数组队列的类

2 判断队列是否满

3 判断队列是否为空

4 向队列中添加元素

5 从队列中取出元素

6 获取队列元素个数

7 显示队列所有元素

8 显示队列头元素

9 数组队列全部代码

10 测试代码

结果与分析

1 操作结果

2 分析与待改进

基本概念

  1. 队列是一个有序列表，可以用数组或是链表来实现。
  2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
  3. 使用数组来实现队列的示意图

             数组队列 

代码实现

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下：

  1. 队列的最大容量 maxSize 。
  2. 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变。=
  3. 为了显示队列元素，用length记录队列的元素个数。
  4. 用数组arr来记录存储数据。

除此只外，数组模拟队列需要定义几个重要的方法，即成员函数：

  1. 出队列操作getQueue
  2. 显示队列的情况showQueue
  3. 查看队列头元素headQueue
  4. 退出系统exit
  5. 判断队列是否已满
  6. 判断队列是否为空

下面是各部分具体的实现过程。

1 数组队列的类

  1. class queue{
  2. private:
  3. 	//声明基本参数
  4. 	int maxSize;// 表示数组的最大容量
  5. 	int front;//队列头
  6. 	int rear;//队列尾
  7. 	int *arr;//用于存放数据，模拟队列
  8. 	int length;//用于记录元素个数
  9. public:
  10. //队列构造函数，确定数组大小，为数组分配内存
  11. //初始化队列首尾元素
  12. queue(int arrMaxSize){
  13. 		maxSize = arrMaxSize;
  14. 		arr = new int[maxSize];
  15. 		length = 0;
  16. 		front = -1;//指向队列头部，分析出front是指向队列头的前一个位置.
  17. 		rear = -1;//指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
  18. 	};
  19. //析构函数 释放内存
  20. ~queue() {
  21. 		delete arr;
  22. 	}
  23. //判断队列是否满
  24. 	bool isFull();
  25. //判断队列是否为空
  26. 	bool isEmpty();
  27. //向队列中添加元素
  28. 	void addQueue(int n);
  29. //从队列中取出元素
  30. 	int getQueue();
  31. //获取队列元素个数
  32. 	int getLength();
  33. //显示队列所有元素
  34. 	void showQueue();
  35. //显示队列头元素
  36. 	int headQueue();
  37. }

2 判断队列是否满

队尾指针指向数组最大位置时，表明队列已满。

  1. 	/// <summary>
  2. 	/// 判断队列是否满
  3. 	/// </summary>
  4. 	/// <returns></returns>
  5. 	bool isFull() {
  6. 		return rear == maxSize - 1;
  7. 	}

3 判断队列是否为空

队首指针和队尾指针指向同一位置时，表示队列已空。

  1. 	/// <summary>
  2. 	/// 判断队列是否为空
  3. 	/// </summary>
  4. 	/// <returns></returns>
  5. 	bool isEmpty() {
  6. 		return rear == front;
  7. 	}

4 向队列中添加元素

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

  1. 将尾指针往后移：rear+1 , 当 front ==rear ,队列为空
  2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1，队列已满
  1.     /// <summary>
  2. 	/// 向队列中添加元素
  3. 	/// </summary>
  4. 	/// <param name="n"></param>
  5. 	void addQueue(int n) {
  6. 		if (isFull()) {
  7. 			cout << "队列满，不能加入数据~" << endl;
  8. 			return;
  9. 		}
  10. 		rear++;
  11. 		arr[rear] = n;
  12. 		length++;
  13. 	}
  14.

5 从队列中取出元素

将队首指针后移一位，然后取出当前位置的元素值。

  1. 	/// <summary>
  2. 	/// 获取队列元素
  3. 	/// </summary>
  4. 	/// <returns></returns>
  5. 	int getQueue() {
  6. 		if (isEmpty()) {
  7. 			throw "队列空，不能取数据";
  8. 		}
  9. 		front++;
  10. 		length--;
  11. 		int value = arr[front];
  12. 		return value;
  13. 	}

6 获取队列元素个数

  1. 	/// <summary>
  2. 	/// 获取队列长度值
  3. 	/// </summary>
  4. 	/// <returns></returns>
  5. 	int getLength() {
  6. 		return length;
  7. 	}

7 显示队列所有元素

从队首开始，遍历length个队列元素，并打印出来。

  1. 	/// <summary>
  2. 	/// 显示当前队列
  3. 	/// </summary>
  4. 	void showQueue() {
  5. 		if (isEmpty()) {
  6. 			cout << "队列空的，没有数据~~" << endl;
  7. 			return;
  8. 		}
  9. 		for (int i = front + 1; i < front + 1 + getLength(); i++) {
  10. 			cout << "arr["<<i<<"] = " << arr[i] << endl;
  11. 		}
  12. 	}

8 显示队列头元素

队首指针不动，显示指针后一位置的元素值。注意，显示队首元素，并不是出队，元素仍然存储在队列中。

  1. /// <summary>
  2. /// 显示队首元素
  3. /// </summary>
  4. /// <returns></returns>
  5. int headQueue() {
  6. 		// 判断
  7. 		if (isEmpty()) {
  8. 			throw "队列空的，没有数据~~";
  9. 		}
  10. 		return arr[front + 1];
  11. 	}

9 数组队列全部代码

如果你懒得逐一复制上面的代码块，这里是实现队列类的全部代码！！！

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. class queue{
  5. private:
  6. 	//声明基本参数
  7. 	int maxSize;
  8. 	int front;
  9. 	int rear;
  10. 	int *arr;
  11. 	int length;
  12. public:
  13. 	/// <summary>
  14. 	///构造函数，初始化队列
  15. 	/// </summary>
  16. 	/// <param name="arrMaxSize"></param>
  17. 	queue(int arrMaxSize) {
  18. 		maxSize = arrMaxSize;
  19. 		arr = new int[maxSize];
  20. 		length = 0;
  21. 		front = -1;
  22. 		rear = -1;
  23. 	}
  24.  
  25. 	/// <summary>
  26. 	/// 析构函数，释放内存
  27. 	/// </summary>
  28. 	~queue() {
  29. 		delete arr;
  30. 	}
  31.  
  32. 	/// <summary>
  33. 	/// 判断队列是否满
  34. 	/// </summary>
  35. 	/// <returns></returns>
  36. 	bool isFull() {
  37. 		return rear == maxSize - 1;
  38. 	}
  39.  
  40. 	/// <summary>
  41. 	/// 判断队列是否为空
  42. 	/// </summary>
  43. 	/// <returns></returns>
  44. 	bool isEmpty() {
  45. 		return rear == front;
  46. 	}
  47.  
  48. 	/// <summary>
  49. 	/// 向队列中添加元素
  50. 	/// </summary>
  51. 	/// <param name="n"></param>
  52. 	void addQueue(int n) {
  53. 		if (isFull()) {
  54. 			cout << "队列满，不能加入数据~" << endl;
  55. 			return;
  56. 		}
  57. 		rear++;
  58. 		arr[rear] = n;
  59. 		length++;
  60. 	}
  61.  
  62. 	/// <summary>
  63. 	/// 获取队列元素
  64. 	/// </summary>
  65. 	/// <returns></returns>
  66. 	int getQueue() {
  67. 		if (isEmpty()) {
  68. 			throw "队列空，不能取数据";
  69. 		}
  70. 		front++;
  71. 		length--;
  72. 		int value = arr[front];
  73. 		return value;
  74. 	}
  75.  
  76. 	/// <summary>
  77. 	/// 获取队列长度值
  78. 	/// </summary>
  79. 	/// <returns></returns>
  80. 	int getLength() {
  81. 		return length;
  82. 	}
  83.  
  84. 	/// <summary>
  85. 	/// 显示当前队列
  86. 	/// </summary>
  87. 	void showQueue() {
  88. 		if (isEmpty()) {
  89. 			cout << "队列空的，没有数据~~" << endl;
  90. 			return;
  91. 		}
  92. 		for (int i = front + 1; i < front + 1 + getLength(); i++) {
  93. 			cout << "arr["<<i<<"] = " << arr[i] << endl;
  94. 		}
  95. 	}
  96.  
  97. 	/// <summary>
  98. 	/// 显示队首元素
  99. 	/// </summary>
  100. 	/// <returns></returns>
  101. 	int headQueue() {
  102. 		// 判断
  103. 		if (isEmpty()) {
  104. 			throw "队列空的，没有数据~~";
  105. 		}
  106. 		return arr[front + 1];
  107. 	}
  108. };
  109.  
  110.

10 测试代码

这里是测试队列类的全部代码。运行程序，屏幕将打印一个简单的菜单，提示你接下来要如何操作，快去打开电脑体验一下吧！！！

  1. #include "queue.h"
  2. int main() {
  3. 	queue *q = new queue(3);
  4. 	char key = ' '; //接收用户输入
  5. 	bool loop = true;
  6. 	//输出一个菜单
  7. 	while (loop) {
  8. 		cout << "s(show): 显示队列" << endl;
  9. 		cout << "e(exit): 退出程序" << endl;
  10. 		cout << "a(add): 添加数据到队列" << endl;
  11. 		cout << "g(get): 从队列取出数据" << endl;
  12. 		cout << "h(head): 查看队列头的数据" << endl;
  13. 		cin >> key;//接收一个字符
  14. 		switch (key) {
  15. 			case 's':
  16. 				q->showQueue();
  17. 				break;
  18. 			case 'a':
  19. 				cout << "输入一个数" << endl;
  20. 				int value;
  21. 				cin >> value;
  22. 				q->addQueue(value);
  23. 				break;
  24. 			case 'g': //取出数据
  25. 				try {
  26. 					int res = q->getQueue();
  27. 					cout << "取出的数据是" << res << endl;
  28. 				}
  29. 				catch (exception e) {
  30. 					// TODO: handle exception
  31. 					cout << e.what() << endl;
  32. 				}
  33. 				break;
  34. 			case 'h': //查看队列头的数据
  35. 				try {
  36. 					int res = q->headQueue();
  37. 					cout << "队列头的数据是" << res << endl;
  38. 				}
  39. 				catch (exception e) {
  40. 					// TODO: handle exception
  41. 					cout << e.what() << endl;
  42. 				}
  43. 				break;
  44. 			case 'e': //退出
  45. 				loop = false;
  46. 				break;
  47. 			default:
  48. 				break;
  49. 			}
  50. 	}
  51. 	cout << "程序退出~~" << endl;
  52. 	return 0;
  53. }

结果与分析

1 操作结果

  1. s(show): 显示队列
  2. e(exit): 退出程序
  3. a(add): 添加数据到队列
  4. g(get): 从队列取出数据
  5. h(head): 查看队列头的数据
  6. a
  7. 输入一个数
  8. 10
  9. s(show): 显示队列
  10. e(exit): 退出程序
  11. a(add): 添加数据到队列
  12. g(get): 从队列取出数据
  13. h(head): 查看队列头的数据
  14. a
  15. 输入一个数
  16. 11
  17. s(show): 显示队列
  18. e(exit): 退出程序
  19. a(add): 添加数据到队列
  20. g(get): 从队列取出数据
  21. h(head): 查看队列头的数据
  22. a
  23. 输入一个数
  24. 12
  25. s(show): 显示队列
  26. e(exit): 退出程序
  27. a(add): 添加数据到队列
  28. g(get): 从队列取出数据
  29. h(head): 查看队列头的数据
  30. a
  31. 输入一个数
  32. 13
  33. 队列满，不能加入数据~
  34. s(show): 显示队列
  35. e(exit): 退出程序
  36. a(add): 添加数据到队列
  37. g(get): 从队列取出数据
  38. h(head): 查看队列头的数据
  39. s
  40. arr[0] = 10
  41. arr[1] = 11
  42. arr[2] = 12
  43. s(show): 显示队列
  44. e(exit): 退出程序
  45. a(add): 添加数据到队列
  46. g(get): 从队列取出数据
  47. h(head): 查看队列头的数据
  48. g
  49. 取出的数据是10
  50. s(show): 显示队列
  51. e(exit): 退出程序
  52. a(add): 添加数据到队列
  53. g(get): 从队列取出数据
  54. h(head): 查看队列头的数据
  55. s
  56. arr[1] = 11
  57. arr[2] = 12
  58. s(show): 显示队列
  59. e(exit): 退出程序
  60. a(add): 添加数据到队列
  61. g(get): 从队列取出数据
  62. h(head): 查看队列头的数据
  63. g
  64. 取出的数据是11
  65. s(show): 显示队列
  66. e(exit): 退出程序
  67. a(add): 添加数据到队列
  68. g(get): 从队列取出数据
  69. h(head): 查看队列头的数据
  70. s
  71. arr[2] = 12
  72. s(show): 显示队列
  73. e(exit): 退出程序
  74. a(add): 添加数据到队列
  75. g(get): 从队列取出数据
  76. h(head): 查看队列头的数据
  77. h
  78. 队列头的数据是12
  79. s(show): 显示队列
  80. e(exit): 退出程序
  81. a(add): 添加数据到队列
  82. g(get): 从队列取出数据
  83. h(head): 查看队列头的数据
  84. g
  85. 取出的数据是12
  86. s(show): 显示队列
  87. e(exit): 退出程序
  88. a(add): 添加数据到队列
  89. g(get): 从队列取出数据
  90. h(head): 查看队列头的数据
  91. s
  92. 队列空的，没有数据~~
  93. s(show): 显示队列
  94. e(exit): 退出程序
  95. a(add): 添加数据到队列
  96. g(get): 从队列取出数据
  97. h(head): 查看队列头的数据

2 分析与待改进

如果你按照流程体验到这里，你一定发现虽然实现了队列相应的功能，这种方法存在一个很大的缺点，队列只能使用一次！！！
总结如下，并且给出解决的思路（具体解决查找“数组环形队列”章节）：

  1. 目前数组使用一次就不能用， 没有达到复用的效果 。
  2. 将这个数组使用算法改进成一个环形的队列（取模：%）。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/756414
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号