数据结构实验4---队列的实现
·
一、实验目的
（1） 理解循环队列的基本概念及逻辑结构。
（2） 掌握循环队列的存取方式。
（3） 能够编写循环队列的入队、出队、判断队满、队空算法。
二、实验内容（根据实验内容可以适当增加主函数和一些辅助算法）
1.基础题：实现循环队列的初始化、判队空、判队满、进队、出队操作。
2.进阶题：汽车轮渡算法
某汽车轮渡口，过江渡船每次能载 10 辆车过江，过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船；客车先于货车上渡船，且每上 4 辆客车，才允许上一辆货车；若等待的客车不足 4 辆，则以货车代替；若无货车等待，允许客车都上船。试设计算法模拟以上渡口管理，可分以下层次：
（1） 实现 10 辆车过江。
（2） 实现 10 辆以上车过江。
3.附加题：用栈实现队列逆置
利用栈先进后出和队列先进先出的操作特点，将队列中元素依次出队后依次入栈，结束后再将堆栈中元素依次出栈再依次入队，这样操作之后队列中元素就成功逆置。步骤如下：
（1）将元素输入队列中；
（2）以队列的先进先出方式出队各元素并依次插入到栈中；
（3）采用栈的后进先出模式出栈各元素并重新入队，从而实现队列中元素的逆置。
三、实验步骤
第1关-基础题：
#include <iostream>
using namespace std;
#define QMaxlen 100 //队列最大存储容量
typedef int QElemtype;
typedef struct
{
QElemtype* base; //队列存储空间的基地址
int front; //队首指针
int rear; //队尾指针
}SqQueue;
//创建一个空的循环队列Q
int InitQueue(SqQueue& Q)
{
Q.base = new QElemtype;
if (!Q.base)
return 0;
Q.front = Q.rear = 0;
return 1;
}
//循环队列入队函数
int InQueue(SqQueue& Q, QElemtype e)
{
if ((Q.rear + 1) % QMaxlen == Q.front)
return 0;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % QMaxlen;
return 1;
}
//循环队列出队函数
int DeQueue(SqQueue& Q, QElemtype& e)
{
if (Q.rear == Q.front)
return 0;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % QMaxlen;
return 1;
}
//输出循环队列中数据元素,数据元素以空格隔开
void Print_Queue(SqQueue& Q)
{
int i;
for (i = Q.front; i != Q.rear; i = (i + 1) % QMaxlen)
printf("%d ", Q.base[i]);
}
int main()
{
SqQueue q;
QElemtype x;
int i, m;
//队列初始化
InitQueue(q);
//输入队列长度
cin >> m;
//循环输入队列元素
for (i = 1; i <= m; i++)
{
cin >> x;
InQueue(q, x);
}
cout << "队列数据:";
Print_Queue(q);
cout << endl;
DeQueue(q, x);
//输出出队元素
cout << "出队元素:" << x << endl;
cout << "出队后，队列元素:";
Print_Queue(q);
return 1;
}
第2关-进阶题：
#include<iostream>
using namespace std;
#define OVERFLOW 0
#define MAXSIZE 100 //队列的最大值
typedef struct {
char* base;
int front;
int rear;
}SqQueue;
//初始化一个队列
void InitSqQueue(SqQueue &Q) {
Q.base = (char*)malloc(sizeof(char)*MAXSIZE);
if (!Q.base)
{
cout<<"存储分配失败";
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
}
//打印队列
void PrintQueue(SqQueue Q)
{
if (Q.rear == Q.front)
{
cout<<"队空";
exit(OVERFLOW);
return;
}
int flag = Q.front;
while (Q.rear != flag)
{
cout<<Q.base[flag]<<' ';
flag=(flag+1)%MAXSIZE;
}
cout<<endl;
}
//入队
void EnQueue(SqQueue &Q, char elem)
{
if ((Q.rear + 1) % MAXSIZE == Q.front)
{
cout<<"队满";
exit(OVERFLOW);
}
Q.base[Q.rear] = elem; //新元素插入队尾
Q.rear = (Q.rear + 1) % MAXSIZE; //队尾指针加1
}
//出队
void OutQueue(SqQueue &Q, char &e)
{
if (Q.front == Q.rear)
{
cout<<"队空";
exit(OVERFLOW);
return;
}
e = Q.base[Q.front]; //将队头元素赋值给e
Q.front = (Q.front + 1) % MAXSIZE; //队头指针加1
}
//求队列元素个数
int CountQueue(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//判断队列是否为空
int EmptyQueue(SqQueue Q)
{
if (Q.front == Q.rear)
return 1;
else
return 0;
}
//（1）实现10辆车过江
//（2）实现10辆以上车过江
//10辆车过江
void FerryCars10(SqQueue &Q, SqQueue &Q1, SqQueue &Q2, SqQueue &Q3)
{
int i = 0, j = CountQueue(Q);//i记录连续上车客车数，j记录船上车数
while (j < 10)
{
if (i < 4 && !EmptyQueue(Q1))
{ //如果船上客车小于4并且客车队列不为空，则上客车
char e = 0;
OutQueue(Q1, e);
EnQueue(Q, e);
i++; j++;
}
else if (i == 4 && !EmptyQueue(Q2))
{
//当船上客车等于4且货车队列不为空，则上一辆货车
char e = 0;
OutQueue(Q2, e);
EnQueue(Q, e);
j++;
i = 0;
}
else
{
while (i < 4 && !EmptyQueue(Q2))
{
char e = 0;
OutQueue(Q2, e);
EnQueue(Q, e);
i++; j++;
}
i = 0;
}
if (EmptyQueue(Q1) && EmptyQueue(Q2))
{
j = 11;
}
}
}
//10辆车过江函数调用
void FerryCars10_Menu()
{
SqQueue Q,Q1,Q2,Q3;
InitSqQueue(Q); InitSqQueue(Q1);
InitSqQueue(Q2); InitSqQueue(Q3);
int count = 0;
//请输入来车序列
while (count<10)
{
int choose;
cin>>choose;
if (choose == 1)
{
EnQueue(Q1, 'A');
count++;
}
else if (choose == 2)
{
EnQueue(Q2, 'B');
count++;
}
else if (choose == 0)
break;
else
continue;
}
//客车队列
PrintQueue(Q1);
//货车队列
PrintQueue(Q2);
FerryCars10(Q, Q1, Q2,Q3);
while (!EmptyQueue(Q))
{
char elem;
OutQueue(Q, elem);
EnQueue(Q3, elem); //渡船满后或者无客车货车时将渡船上的车入队Q3
}
//渡船队列
PrintQueue(Q3);
}
//10辆以上的车过江函数
void FerryCars_over10(SqQueue &Q, SqQueue& Q1, SqQueue& Q2,SqQueue& Q3)
{
while (!EmptyQueue(Q1) && !EmptyQueue(Q2))
{
FerryCars10(Q,Q1,Q2,Q3);
while (!EmptyQueue(Q))
{
char elem;
OutQueue(Q,elem);
EnQueue(Q3,elem); //渡船满后或者无客车货车时将渡船上的车入队Q3
}
}
}
//10辆以上的车过江函数调用
void FerryCars_over10_Menu()
{
SqQueue Q, Q1, Q2, Q3;
InitSqQueue(Q); InitSqQueue(Q1);
InitSqQueue(Q2); InitSqQueue(Q3);
//输入1表示客车，输入2表示货车，输入0表示结束
int choose=3;
//请输入来车序列
while (choose != 0)
{
cin>>choose;
if (choose == 1)
{
EnQueue(Q1, 'A');
}
else if (choose == 2)
{
EnQueue(Q2, 'B');
}
else if (choose == 0)
{
break;
}
}
//客车队列
PrintQueue(Q1);
//货车队列
PrintQueue(Q2);
FerryCars_over10(Q, Q1, Q2, Q3);
//渡江队列
PrintQueue(Q3);
}
int main()
{
int n;
//输入1表示10辆车渡江，输入2表示10辆车以上渡江
cin>>n;
if(n==1)
FerryCars10_Menu();
if(n==2)
FerryCars_over10_Menu();
return 1;
}
第3关-附加题：
#include<iostream>
using namespace std;
typedef struct Node {
int data;
struct Node* next;
}node; //队列结点
//定义一个链队列
typedef struct LinkQueue {
node* front; //队首结点
node* rear; //队尾结点
}LQ;
//初始化空链队列
LQ InitLQ(LQ LQ) {
LQ.front = (node*)malloc(sizeof(node));
LQ.front->data = -1;
LQ.front->next = NULL;
LQ.rear = LQ.front; //队首结点和队尾结点是同一个结点
return LQ;
}
//进栈
node* PushStack(node* LS ,int elem) { //LS是栈顶结点
node* new_node = (node*)malloc(sizeof(node)); //创建一个结点
if (new_node == NULL) {
cout<<"创建链栈结点失败";
exit(0);
}
else {
new_node->data = elem;
new_node->next = LS;
//给新结点指针域赋值，新结点指向当前栈顶结点
LS = new_node; //新结点成为新的栈顶结点
}
return LS;
}
//入队列
LQ PushQueue(LQ &LQ,int e) {
node* new_node = (node*)malloc(sizeof(node));//生成新结点
if (new_node == NULL) {
cout<<"创建结点失败";
exit(0);
}
new_node->data = e;
new_node->next = NULL;
LQ.rear->next = new_node; //在队尾结点处插入新结点
LQ.rear = new_node;//队尾结点后移
return LQ;
}
//出栈并进队列
LQ PopStack(LQ LQ,node* LS) {
while (LS != NULL) {
node* tmp = LS;
LS = tmp->next;
LQ=PushQueue(LQ,tmp->data);
free(tmp);
}
return LQ;
}
//出队列并进栈
node* PopQueue(LQ &LQ,node* LS) {
while (LQ.front != LQ.rear) {
//从入队第一个元素开始打印
LS = PushStack(LS, LQ.front->next->data); //出队元素进栈
node* tmp = LQ.front;
LQ.front = LQ.front->next;
free(tmp);
}
return LS;
}
//打印队列全部元素
void ShowLQ(LQ LQ) {
node* tmp = LQ.front->next;
while (tmp != NULL) {
cout<<tmp->data<<' ';
tmp = tmp->next;
}
cout<<endl;
}
int main()
{
LQ myLQ;
int n,e;
node* mystack = NULL;
myLQ = InitLQ(myLQ);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>e;
myLQ=PushQueue(myLQ,e);
}
cout<<"原队列:";
ShowLQ(myLQ);
mystack=PopQueue(myLQ,mystack);
myLQ=PopStack(myLQ,mystack);
cout<<"逆置后队列:";
ShowLQ(myLQ);
return 1;
}
四、实验结果
第一关：
第二关：
第三关：
五、实验小结
通过本次实验加深了对循环队列基本算法的熟悉和应用，在实验过程中，我不仅复习了循环队列的基本概念，如循环队列的判空和判满条件，还通过动手编程实现了循环队列的入队、出队和遍历等操作。在实验过程中，我还发现自己在算法实现和代码优化方面存在不足，应该多加强基本操作的练习，才能更好的掌握循环队列的使用。
本次循环队列的实验让我受益匪浅。我不仅加深了对循环队列的理解，还提高了编程能力和解决问题的能力。未来，我将多加强算法实现和代码优化的练习，同时关注循环队列在实际应用中的最新进展，以更好地掌握循环队列的使用。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)