| 操作 |
时间复杂度(T(n)) |
空间复杂度（S(n)） |
| 求长度 |
O(1) |
O(1) |
| 判断是否为空 |
O(1) |
O(1) |
| 得到队首元素 |
O(1) |
O(1) |
| 插入元素 |
O(1) |
O(1) |
| 删除元素 |
O(1) |
O(1) |
| 清空队列 |
O(1) |
O(1) |
| 判断是否已满 |
O(1) |
O(1) |
/* 数据结构分析与学习专栏
* Copyright (c) 2015, 山东大学计算机科学与技术专业学生
* All rights reserved.
* 作 者： 高祥
* 完成日期： 2015 年 4 月 6 日
* 版 本 号：013
*任务描述：针对链式队列，实现8个基本操作
* 1：建立队列 ；
* 2：输出队列 ；
* 3：求队列的长度 ；
* 4：判断队列是否为空 ；
* 5：得到队列的队首元素；
* 6：向队列中插入元素（插在队尾） ；
* 7：删除队列的元素（删除队首元素）；
* 8： 清空队列；
*主要函数：
* 1. InitQueue(Queue &Q);//初始化队列
* 2. CreateQueue(Queue &Q);//创建队列
* 3. Output(Queue Q);//输出队列元素
* 4. int QueueLength(Queue Q);//求队列的长度
* 5. IsEmpty(Queue Q);//判断队列是否为空
* 6. IsFull(Queue Q);//判断队列是否已满
* 7. GetHead(Queue Q);//得到队列首元素
* 8. EnQueue(Queue &Q,ElemType elem);//插入元素
* 9.DeQueue(Queue &Q);//删除元素
* 10. ClearQueue(Queue &Q);//清空队列
*/
#include<iostream>
#include<cstdlib>
using namespace std;
#define OK 1
#define FALSE 0
#define MAXSIZE 10
typedef int ElemType;
typedef int Status;
typedef struct
{
ElemType *base;//存储元素空间的指针
int first;//头指针：始终指向非空队列的首元素位置
int last;//尾指针：始终指向非空队列的最后一个元素的下一个位置
} Queue;
Status InitQueue(Queue &Q);//初始化队列
void CreateQueue(Queue &Q);//创建队列
void Output(Queue Q);//输出队列元素
int QueueLength(Queue Q);//求队列的长度
Status IsEmpty(Queue Q);//判断队列是否为空
Status IsFull(Queue Q);//判断队列是否已满
void GetHead(Queue Q);//得到队列首元素
Status EnQueue(Queue &Q,ElemTypeelem);//插入元素
void DeQueue(Queue &Q);//删除元素
void ClearQueue(Queue &Q);//清空队列
void Interaction();
int main()
{
Queue Q;
Interaction();
int operate;
while(cin>>operate)
{
switch(operate)
{
case 0:
return 0;
case 1:
CreateQueue(Q);
break;
case 2:
Output(Q);
break;
case 3:
cout<<"队列的长度为："<<QueueLength(Q)<<endl;
break;
case 4:
if(IsEmpty(Q))
{
cout<<"队列为空。\n";
}
else
{
cout<<"队列不为空。\n";
}
break;
case 5:
GetHead(Q);
break;
case 6:
cout<<"请输入要插入的元素：";
ElemType elem;
cin>>elem;
if(EnQueue(Q,elem))
{
cout<<"新队列为：";
Output(Q);
}
break;
case 7:
DeQueue(Q);
break;
case 8:
ClearQueue(Q);
break;
default:
cout<<"请输入正确的操作数字！\n";
break;
}
}
return 0;
}
Status InitQueue(Queue &Q)//初始化队列
{
Q.base=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));
//分配MAXSIZE个存储元素的空间，实际用于存储的有MAXSIZE-1个空间，
//少用的一个空间用于表示”队列头指针在队列尾指针的下一位置（环状上）“时队列为满
if(!Q.base)
{
cout<<"内存非配失败。\n";
return FALSE;
}
Q.first=Q.last=0;//初始化队列为空
return OK;
}
void CreateQueue(Queue &Q)//创建队列
{
if(InitQueue(Q))
{
INPUT:
cout<<"请输入队列元素的个数：";
int queuesize;
cin>>queuesize;
if(queuesize>MAXSIZE-1)
{
cout<<"超出最大容量，请重新输入。\n";
goto INPUT;
}
cout<<"请输入"<<queuesize<<"个元素：";
while(queuesize--)
{
ElemType elem;
cin>>elem;
EnQueue(Q,elem);//借用插入元素函数
}
cout<<"创建的队列为：";
Output(Q);
}
}
void Output(Queue Q)//输出队列元素
{
if(!IsEmpty(Q))
{
int cur=Q.first;
while(cur!=Q.last)
{
cout<<Q.base[cur]<<" ";
cur=(cur+1)%MAXSIZE;//注意细节
}
cout<<endl;
return;
}
cout<<"队列为空，无法输出。\n";
}
int QueueLength(Queue Q)//求队列的长度
{
//分情况讨论：
if(Q.last>=Q.first)
{
return Q.last-Q.first;
}
return Q.last+MAXSIZE-Q.first;
//首先此时（Q.last<Q.first）下标0必定在两个下标之间；
//Q.last：表示从下标0开始至队列结束的元素个数；
//MAXSIZE-Q.first：表示队列开始至下标0之前的元素个数
}
Status IsEmpty(Queue Q)//判断队列是否为空
{
if(Q.first==Q.last)//头尾指针相等时
{
return OK;
}
return FALSE;
}
Status IsFull(Queue Q)//判断队列是否已满
{
if((Q.last+1)%MAXSIZE==Q.first)//队列头指针在队列尾指针的下一位置（环状上）
{
return OK;
}
return FALSE;
}
void GetHead(Queue Q)//得到队列首元素
{
if(!IsEmpty(Q))
{
cout<<"队首元素是："<<Q.base[Q.first]<<endl;
return;
}
cout<<"队列为空。\n";
}
Status EnQueue(Queue &Q,ElemTypeelem)//插入元素
{
if(!IsFull(Q))//队列未满时
{
Q.base[Q.last]=elem;
Q.last=(Q.last+1)%MAXSIZE;
return OK;
}
cout<<"队列已满，无法插入元素。\n";
return FALSE;
}
void DeQueue(Queue &Q)//删除元素
{
if(!IsEmpty(Q))
{
Q.first=(Q.first+1)%MAXSIZE;
cout<<"删除元素后的队列为：";
Output(Q);
return;
}
cout<<"队列为空，无法删除元素。\n";
}
void ClearQueue(Queue &Q)//清空队列
{
Q.first=Q.last;
cout<<"队列清空成功。\n";
}
void Interaction()
{
cout<<"请输入对应操作的序号：\n";
cout<<"0：退出程序；\n";
cout<<"1：建立队列；\n";
cout<<"2：输出队列；\n";
cout<<"3：求队列的长度；\n";
cout<<"4：判断队列是否为空；\n";
cout<<"5：得到队列的队首元素；\n";
cout<<"6：向队列中插入元素（插在队尾）；\n";
cout<<"7：删除队列的元素（删除队首元素）；\n";
cout<<"8：清空队列；\n";
cout<<"该队列最大容量为："<<MAXSIZE-1<<"个元素。\n";
}